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
}
新闻标题:avl树java代码 java avg
网页路径:http://scyanting.com/article/dojhhgh.html