avl树java代码 java avg

怎么做啊（java）

你可以把自己遇到的问题写出来，知道的网友就会帮你解答了，另外你还需要多学习一些Java的知识，这样才不至于解决不了问题。这里给你学习Java编程语言的一些小建议：

成都创新互联公司是一家集网站建设,原州企业网站建设,原州品牌网站建设,网站定制,原州网站建设报价,网络营销,网络优化,原州网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

1、多买几本Java的书籍，不要看电子书。

2、对Java基础数据类型有一个了解。

3、学会各种类型的操作方法。

4、了解函数和类的概念。

5、动手实践，找小项目练习。

6、零基础的同学在扣丁学堂看一些Java视频教程学习一下。

学习Java的关键是看你自己的学习能力和毅力，只要坚持就会有收货的。

java（算法与数据结构）tree

代码实现[一]部分

package ChapterEight;

class Tree {

class Node {

public long value;

public Node leftChild;

public Node rightChild;

public Node(long value) {

this.value = value;

leftChild = null;

rightChild = null;

}

}

public Node root;

public Tree() {

root = null;

}

// 向树中插入一个节点

public void insert(long value) {

Node newNode = new Node(value);

// 树是空的

if (root == null)

root = newNode;

else {

Node current = root;

Node parentNode;

while (true) {

parentNode = current;

if (value current.value) {

current = current.leftChild;

// 要插入的节点为左孩子节点

if (current == null) {

parentNode.leftChild = newNode;

return;

}

} else {

// 要插入的节点为右孩子节点

current = current.rightChild;

if (current == null) {

parentNode.rightChild = newNode;

return;

}

}

}

}

}

// 先续遍历树中的所有节点

public void preOrder(Node currentRoot) {

if (currentRoot != null) {

System.out.print(currentRoot.value + " ");

preOrder(currentRoot.leftChild);

preOrder(currentRoot.rightChild);

}

}

// 中续遍历树中的所有节点

public void inOrder(Node currentNode) {

if (currentNode != null) {

inOrder(currentNode.leftChild);

System.out.print(currentNode.value + " ");

inOrder(currentNode.rightChild);

}

}

// 后续遍历树中的所有节点

public void postOrder(Node currentNode) {

if (currentNode != null) {

postOrder(currentNode.leftChild);

postOrder(currentNode.rightChild);

System.out.print(currentNode.value + " ");

}

}

public void traverse(int traverseType) {

switch (traverseType) {

case 1:

preOrder(root);

break;

case 2:

inOrder(root);

break;

case 3:

postOrder(root);

break;

default:

break;

}

// 依据树节点的值删除树中的一个节点

public boolean delete(int value) {

// 遍历树过程中的当前节点

Node current = root;

// 要删除节点的父节点

Node parent = root;

// 记录树的节点为左孩子节点或右孩子节点

boolean isLeftChild = true;

while (current.value != value) {

parent = current;

// 要删除的节点在当前节点的左子树里

if (value current.value) {

isLeftChild = true;

current = current.leftChild;

}

// 要删除的节点在当前节点的右子树里

else {

isLeftChild = false;

current = current.rightChild;

}

// 在树中没有找到要删除的节点

if (current == null)

return false;

}

// 要删除的节点为叶子节点

if (current.leftChild == null current.rightChild == null) {

// 要删除的节点为根节点

if (current == root)

root = null;

// 要删除的节点为左孩子节点

else if (isLeftChild)

parent.leftChild = null;

// 要删除的节点为右孩子节点

else

parent.rightChild = null;

}

// 要删除的节点有左孩子节点，没有右孩子节点

else if (current.rightChild == null) {

// 要删除的节点为根节点

if (current == null)

root = current.leftChild;

// 要删除的节点为左孩子节点

else if (isLeftChild)

parent.leftChild = current.leftChild;

// 要删除的节点为右孩子节点

else

parent.rightChild = current.leftChild;

}

// 要删除的节点没有左孩子节点，有右孩子节点

else if (current.leftChild == null) {

// 要删除的节点为根节点

if (current == root)

root = root.rightChild;

// 要删除的节点为左孩子节点

else if (isLeftChild)

parent.leftChild = current.rightChild;

// 要删除的节点为右孩子节点

else

parent.rightChild = current.rightChild;

}

// 要删除的接节点既有左孩子节点又有右孩子节点

else {

Node successor = getSuccessor(current);

// 要删除的节点为根节点

if (current == root)

root = successor;

// 要删除的节点为左孩子节点

else if (isLeftChild)

parent.leftChild = successor;

// 要删除的节点为右孩子节点

else

parent.rightChild = successor;

}

return true;

}

// 找到要删除节点的替补节点

private Node getSuccessor(Node delNode) {

// 替补节点的父节点

Node successorParent = delNode;

// 删除节点的替补节点

Node successor = delNode;

Node current = delNode.rightChild;

while (current != null) {

// successorParent指向当前节点的上一个节点

successorParent = successor;

// successor变为当前节点

successor = current;

current = current.leftChild;

}

// 替补节点的右孩子节点不为空

if (successor != delNode.rightChild) {

successorParent.leftChild = successor.rightChild;

successor.rightChild = delNode.rightChild;

}

return successor;

}

}

public class TreeApp {

public static void main(String[] args) {

Tree tree = new Tree();

tree.insert(8);

tree.insert(50);

tree.insert(45);

tree.insert(21);

tree.insert(32);

tree.insert(18);

tree.insert(37);

tree.insert(64);

tree.insert(88);

tree.insert(5);

tree.insert(4);

tree.insert(7);

System.out.print("PreOrder : ");

tree.traverse(1);

System.out.println();

System.out.print("InOrder : ");

tree.traverse(2);

System.out.println();

System.out.print("PostOrder : ");

tree.traverse(3);

System.out.println();

System.out.println(tree.delete(7));

System.out.print("PreOrder : ");

tree.traverse(1);

System.out.println();

System.out.print("InOrder : ");

tree.traverse(2);

System.out.println();

System.out.print("PostOrder : ");

tree.traverse(3);

System.out.println();

}

}

跪求平衡二叉树pascal代码。怎么办？

"AVL树插入算法的基本步骤如下：

①在寻找新结点的插入位置的过程中，记下离该位置近来、且平衡因子不等于零的结点a（此结点即为可能出现的最小失衡子树的根）；

②修改自该结点至插入位置路径上全部结点的平衡因子（注意：树上其它结点的平衡因子均不受插入的影响）；

③判别实施插入操作之后，结点a的平衡因子的绝对值是不是大于1（即判别是不是失衡）。若是，进一步判别失衡类型并做相应调整；否则插入过程结束。

仍以二叉链表作为AVL树的存储结构。但每一个结点需增加1个域用于存储平衡因

子。类型定义如下：

type

avlpt=^anode;

anode=record

key:keytype;

bf:-1..1;

lchild,rchild:avlpt;

...

end;

在此存储结构上，AVL树的插入算法如下：

procedure

insert_avltree(K:keytype;var

t:avlpt);

//在以T为根指针的AVL树上插入键值等于K的新结点//

begin

new(s);s^.key:=K;s^.lchild:=nil;s^.lchild:=nil;//生成以K为键值的新结点//

if

t=nil

then

t:=s

//将新结点作为根结点插入空树//

else

begin

//4-10行：查找S^的插入位置，并记录a//

f:=nil;a:=t;p:=t;q:=nil;

while

pnil

do

[

if

p^.bf0

then

[a:=p;f:=p];

//a记录bf0的结点，其终值指向离插入位置近来的bf0的结点//

q:=p;

//s^将插到q^上//

if

s^.keyp^.key

then

p:=p^.lchild

else

p:=p^.rchild

];

if

s^.keyq^.key

then

q^.lchild:=s

else

q^.rchild:=s;

//插入s^//

if

s^.keya^.key

then

[

p:=a^.lchild;b:=p;

d:=1

]

//s^插在a^的左子树上，增量D为1//

else

[

p:=a^.rchild;b:=p;d:=-1

];//s^插在A^的右子树上，增量D为-1//

while

ps

do

//修改自a^的孩子至S^路径上各结点的平衡因子//

if

s^.keyp^.key

//若S^在p^的左子树上//

then

[

p^.bf:=1;p:=p^.lchild

]

//p^的平衡因子加工1—原来为O，由于p^是a^的子孙//

else

[p^.bf:=-1;p:=p^.lchild];

//p^的平衡因子减1—原来为0//

case

//判别是不是失衡//

a^.bf=0:

a^.bf:=d;

//找插入位置过程中未遇到bf0的结点，A指根树//

a^.bf+d=0:

a^.bf:=0

//插入不导致以a^为根的子树失衡//

else

//其它情形均失衡。差别失衡类型并调整//

[

if

d=1

then

case

b^.bf=1:LL-rotation;//LL型调整//

b^.bf=-1:LR-rotation//LR型调整，结束时令B指新子树的根//

end;

else

case

b^.bf=-1:RR-rotation;

b^.bf=1:RL-rotation

//结束时令b指新子树的根//

end;

case

//将新子树链接到原a^的双亲f^上//

f=nil:t:=b;//原a^为树根//

f^.lchild=a:f^.lchild:=b;

f^.rchild=a:f^.rchild:=b

end

]

end

end;

二叉排序树（包括AVL树）适合于组织较小的、内存中能容纳的查找表。若查找表大得必须存放在外部存储器上，再用二叉排序树来表示就不合适了。对外存文件的组织来说，需考虑采用其他的数据结构（如B树和B+树）。"

数据结构中树的问题

通用有序平衡二叉树接口描述

这套代码对用户屏蔽了复杂的二叉树的旋转操作，不区分用户的数据类型，任何数

据都可以用有序平衡二叉树来存放。我还对平衡二叉树进行了一点点扩展，在树结构里

面增加了保持线行递增（或递减）顺序的双向链表，方便使用者能够快速按序遍历所有

树节点。

这套代码需要用户直接参与的部分都用注册函数来实现，让使用者完全不需要了解

有序平衡二叉树的添加、删除或查找的过程，能够做到傻瓜式的使用。至于性能，我添

加过300万个树节点之后，树高只有22层，查找任意一个节点最多只需要22次匹配操作。

比HASH表快了很多。

这套代码还针对vxworks操作系统做了一点点扩展，其实就是判断一下当前操作系统

是否是vxworks，如果是的话就创建一个二进制信号量，如果不是就什么信号量也不创建。

目前此版本提供了如下通用接口：

1、数据结构定义

1.1、树的结构定义

typedef struct _AVL_TREE_HEADER

{

TREE_NODE *pTreeHeader;

#ifdef ORDER_LIST_WANTED

TREE_NODE *pListHeader;

TREE_NODE *pListTail;

#endif

unsigned int count; /*AVL树里的节点总数*/

int (*keyCompare)(TREE_NODE * , TREE_NODE *);

int (*free)(TREE_NODE *);

#if OS==3||OS==4 /*#if OS == VXWORKS || OS == VXWORKS_M*/

SEM_ID sem;

#endif

} tAVLTree;

1.2、树节点的结构定义

typedef struct _AVL_TREE_NODE

{

#ifdef ORDER_LIST_WANTED

struct _AVL_TREE_NODE *prev;

struct _AVL_TREE_NODE *next;

#endif

struct _AVL_TREE_NODE *tree_root;

struct _AVL_TREE_NODE *left_child;

struct _AVL_TREE_NODE *right_child;

int bf; /*平衡因子；当平衡因子的绝对值大于或等于2的时候就表示树不平衡(balance_factor)*/

}TREE_NODE;

2、通用函数接口定义

2.1、avlTreeCreate

函数原型：tAVLTree *avlTreeCreate(int *keyCompareFunc,int *freeFunc)

参数描述：keyCompareFunc - 节点大小比较函数的指针，此函数需要用户自己提供，

比较函数的返回值应该是-1、0、1，(*keyCompareFunc)函数有两个参数，

分别是两个树节点，如果第二个参数所指向的树节点的值比第一个的小，

那么比较函数就应该返回-1，如果相等就是返回0，否则就是1。具体的比

较规则由用户根据所存储的数据里面的关键字来指定（当然，关键字有可

能有多个）。

freeFunc - (*freeFunc)只有一个参数，就是需要释放内存的节点的指

针，填写这个注册函数的目的是为了实现avlTreeDestroy和avlTreeFlush

这两个函数。

返回值 ：成功 - 返回指向一个树的指针

失败 - NULL

函数描述：创建一棵空的平衡二叉树，如果是vxworks操作系统的话还创建一个跟树

相关的一个二进制信号量。初始化所有指针为空指针。

2.2、avlTreeDestroy

函数原型：int avlTreeDestroy(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 1

失败 - 0

函数描述：摧毁一颗平衡二叉树，释放所有树节点的内存，并且释放信号量（如果是

vxworks操作系统的话），释放pTree所指向的二叉树所占用的内存。

2.3、avlTreeFlush

函数原型：int avlTreeFlush(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 1

失败 - 0

函数描述：清空一颗平衡二叉树，释放所有树节点的内存，但是并不删除平衡二叉树

2.4、avlTreeAdd

函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pInsertNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pInsertNode - 待插入的节点的指针

返回值 ：成功 - 1

失败 - 0

函数描述：往平衡二叉树中添加一个成员节点

2.5、avlTreeDel

函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pDelNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pDelNode - 待插入的节点的指针

返回值 ：成功 - 1

失败 - 0

函数描述：从平衡二叉树中删除一个树节点

2.6、avlTreeFind

函数原型：TREE_NODE *avlTreeFind(tAVLTree *pTree,TREE_NODE *pKeyNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pKeyNode - 待查找的节点的关键字

返回值 ：成功 - 查找到的节点指针

失败 - NULL

函数描述：查找一个节点

2.7、avlTreeCount

函数原型：int avlTreeCount(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里的节点总数

失败 - 0

函数描述：获取当前树里面的所有成员节点总数

2.8、avlTreeFirst

函数原型：TREE_NODE *avlTreeFirst(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里面的最小的成员节点的指针

失败 - NULL，只有树是空的时候才会返回NULL

函数描述：获取当前平衡二叉树里面第一个成员节点，即最小的成员节点

2.9、avlTreeLast

函数原型：TREE_NODE *avlTreeLast(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里面的最大的成员节点的指针

失败 - NULL，只有树是空的时候才会返回NULL

函数描述：获取当前平衡二叉树里面最后一个成员节点，即最大的成员节点

2.10、avlTreeNext

函数原型：TREE_NODE *avlTreeNext(TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 下一个成员节点的指针

失败 - NULL

函数描述：获取当前节点的下一个节点

2.11、avlTreePrev

函数原型：TREE_NODE *avlTreePrev(TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 前一个成员节点的指针

失败 - NULL

函数描述：获取当前节点的前一个节点

2.12、AVL_TREE_LOCK

函数原型：void AVL_TREE_LOCK(tAVLTree *pTree,int timeout)

参数描述：pTree - 指向一棵平衡二叉树的指针

timeout - 等待时间

返回值 ：N/A

函数描述：此函数只有是vxworks系统才有效，目的是对树进行互斥操作，防止

多任务同时操作链表。

2.13、AVL_TREE_UNLOCK

函数原型：void AVL_TREE_UNLOCK(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：N/A

函数描述：此函数只有是vxworks系统才有效，目的是对树进行解除互斥操作

2.13、AVL_TREENODE_FREE

函数原型：void AVL_TREENODE_FREE(tAVLTree *pTree,TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pNode - 需要释放的节点的指针

返回值 ：N/A

函数描述：此函数释放内存的过程采用的是注册的释放函数，释放不仅仅

只有free函数，对于一些复杂的结构设计，可能需要释放多个

不同的内存。

3、应用举例

typedef struct _testStruct{

TREE_NODE node; /*树节点的结构一定要放在用户自定义结构的最前面，注意!*/

int keyA; /*关键字A*/

int keyB; /*关键字B*/

int keyC; /*关键字C，比方说此结构有3个关键字*/

int userData[200]; /*用户的实际数据区*/

}tTestStruct;

int keyCompareFunc(TREE_NODE *p , TREE_NODE *p1)

{

tTestStruct *T1=NULL,*T2=NULL;

T1=(tTestStruct *)p;

T2=(tTestStruct *)p1;

if(T1-keyA T2-keyA) return 1;

if(T1-keyA T2-keyA) return -1;

if(T1-keyB T2-keyB) return 1;

if(T1-keyB T2-keyB) return -1;

if(T1-keyC T2-keyC) return 1;

if(T1-keyC T2-keyC) return -1;

return 0;

}

int freeFunc(TREE_NODE *pNode)

{

free((void *)pNode);

return 1;

}

tAVLTree *pTree = NULL;

int main()

{

tTestStruct *pTest = NULL;

tTestStruct key;

int count = 0;

pTree = (tAVLTree *)avlTreeCreate

(

(void*)keyCompareFunc ,

(void *)freeFunc

);

if(!pTree)

{

printf("\r\n 创建平衡二叉树失败");

return 0;

}

/*添加一个节点*/

pTest = (tTestStruct *)malloc(sizeof(tTestStruct));

if(!pTest)

{

printf("\r\n 创建树节点失败");

return 0;

}

pTest-keyA = 1;

pTest-keyB = 2;

pTest-keyC = 3;

if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))

{

printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同");

return 1;

}

/*再添加一个节点*/

pTest = (tTestStruct *)malloc(sizeof(tTestStruct));

if(!pTest)

{

printf("\r\n 创建树节点又失败");

return 0;

}

pTest-keyA = 1;

pTest-keyB = 1;

pTest-keyC = 3; /*第二次添加的节点的关键字比较大家可以算一算*/

if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))

{

printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同");

return 1;

}

/*遍历有序平衡二叉树 -- 从小到大*/

pTest = (tTestStruct *)avlTreeFirst(pTree);

while(pTest)

{

/**************************

*这里你想干嘛干嘛

*处理pTest-userData?

***************************/

pTest = (tTestStruct *)avlTreeNext(pTree);

}

/*遍历有序平衡二叉树 -- 从大到小*/

pTest = (tTestStruct *)avlTreeLast(pTree);

while(pTest)

{

/**************************

*这里你想干嘛干嘛

*处理pTest-userData?

***************************/

pTest = (tTestStruct *)avlTreePrev(pTree);

}

/*查找某个节点*/

key-keyA = 1;

key-keyB = 1;

key-keyC = 3;

pTest = (tTestStruct *)avlTreeFind(pTree , (TREE_NODE *)key);

if(pTest)

printf("\r\n 这里应该可以查找到一条记录，就是第二个插入的节点");

/*删除一个节点，我们就将上面查找到的节点删除*/

if(!avlTreeCount(pTree , (TREE_NODE *)pTest))

{

printf("\r\n 如果删除失败，只能说明一个问题，树里面不存在这个节点");

return 0;

}

/*获取树的总的节点数*/

count = avlTreeCount(pTree);

printf("\r\n 我想现在count应该等于1，刚才我们删掉了一个节点");

/*清空整棵树*/

avlTreeFlush(pTree);

/*删除整棵树，其实现在只有一颗裸树了，因为树节点都被flush掉了*/

avlTreeDestroy(pTree);

pTree = NULL;

return 1

}