[原创]AVL树一代~
已经基本实现AVL树插入和查找功能~还差个删除节点(这个以后慢慢弄)~~记得上次发过一次AVL树~不过那是照着参考代码敲的~
这次和上次不同~虽然有参考过各方面的代码~但大部分内容是原创的~可以看看~~~
感觉高度方面和一些严谨的平衡树差了一些~如果要对比一下可以参考~~
https://bbs.bccn.net/thread-475229-1-1.html
那个贴的代码是我参考网上的~
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<assert.h>
typedef int ElemType;
typedef struct Tree
{
ElemType Data;
int height; //记录树的高度
struct Tree* l;
struct Tree* r;
}Tree,*PTree;
void Creat_Node(void** p,size_t size); //创建一个节点
void Free_Node(void** p); //删除一个节点
int Tree_Insert(PTree* t,ElemType data,int (*Comp)(const void* p1,const void* p2)); //创建二叉树(成功插入返回1,否则返回0)
void Tree_Free(PTree* t); //释放树
void Tree_Pre_Order_Print(const PTree t,int (*Visit)(const PTree t)); //前序遍历树
void Tree_In_Order_Print(const PTree t,int (*Visit)(const PTree t)); //中序遍历树
int Tree_Get_Max(const PTree t); //获取树的最大深度
int Tree_Get_Height(const PTree t); //获取树的深度
void Tree_Single_Rotate_With_Right(PTree* t); //右旋操作
void Tree_Single_Rotate_With_Left(PTree* t); //左旋操作
void Tree_ByAVL_Single_Rotate_With_Right(PTree* t); //对于AVL树的右旋操作
void Tree_ByAVL_Single_Rotate_With_Left(PTree* t); //对于AVL树的左旋操作
void Tree_ByAVL_Double_Rotate_With_Left(PTree* t); //对于AVL树的双旋操作,先左后右
void Tree_ByAVL_Double_Rotate_With_Right(PTree* t); //对于AVL树的双旋操作,先右后左
void Tree_Balance(PTree* t,const int l,const ElemType data,int (*Comp)(const void* p1,const void* p2)); //调整平衡
void Tree_ByAVL_Adjust_Right_Height(PTree* t); //调整右高度
void Tree_ByAVL_Adjust_Left_Height(PTree* t); //调整左高度
PTree Tree_Find_Node(PTree t,ElemType data,int (*Comp)(const void* p1,const void* p2)); //非递归查找信息
int Tree_Visit(const PTree t); //输出函数
int Tree_Comp(const void* p1,const void* p2); //比较函数
int main()
{
PTree t=NULL;
int i=0;
int k=0;
srand((unsigned)time(NULL));
for (i=0;i<100;++i)
Tree_Insert(&t,rand()%1000,Tree_Comp);
puts("中序遍历:");
Tree_In_Order_Print(t,Tree_Visit);
puts("");
puts("二叉树最大深度是:");
printf("%d\n",Tree_Get_Max(t));
puts("请输入要查找的数据,EOF结束输入:");
while (scanf("%d",&k)==1) //这里默认查找为int 型,如果要更改数据类型这里输入格式要改改
{
PTree pt=NULL;
if ((pt=Tree_Find_Node(t,k,Tree_Comp))!=NULL)
puts("找到该数据!");
else
puts("没有找到该数据!");
}
Tree_Free(&t);
return 0;
}
void Creat_Node(void** p,size_t size) //创建一个节点
{
if (*p!=NULL)
return ;
*p=malloc(size);
assert(*p);
memset(*p,0,size);
}
void Free_Node(void** p) //删除一个节点
{
if (*p==NULL)
return ;
free(*p);
*p=NULL;
}
Tree_Insert(PTree* t,ElemType data,int (*Comp)(const void* p1,const void* p2))
{
int k=0;
int s=0;
int l=0;
if (*t==NULL)
{
Creat_Node(t,sizeof(Tree));
(*t)->Data=data;
(*t)->height=1;
return 1;
}
k=Comp(&(*t)->Data,&data);
if (k==1)
s=Tree_Insert(&(*t)->l,data,Comp);
else if (k==-1)
s=Tree_Insert(&(*t)->r,data,Comp);
if (s&&((*t)->height==Tree_Get_Height((*t)->l)||(*t)->height==Tree_Get_Height((*t)->r))) //调整二叉树高度
{
++(*t)->height;
l=Tree_Get_Height((*t)->l)-Tree_Get_Height((*t)->r);
}
if (s&&(l==2||l==-2))
Tree_Balance(t,l,data,Comp);
return s;
}
int Tree_Get_Max(const PTree t) //获取树的最大深度
{
int l=0;
int r=0;
if (t==NULL)
return 0;
l=Tree_Get_Max(t->l)+1;
r=Tree_Get_Max(t->r)+1;
return l>r?l:r;
}
int Tree_Get_Height(const PTree t) //获取树的深度
{
if (t==NULL)
return 0;
return t->height;
}
void Tree_Single_Rotate_With_Right(PTree* t) //右旋操作
{
PTree pt=(*t)->l;
(*t)->l=pt->r;
pt->r=*t;
*t=pt;
}
void Tree_Single_Rotate_With_Left(PTree* t) //左旋操作
{
PTree pt=(*t)->r;
(*t)->r=pt->l;
pt->l=*t;
*t=pt;
}
void Tree_ByAVL_Adjust_Right_Height(PTree* t) //调整右高度
{
int lh=Tree_Get_Height((*t)->r->l);
int rh=Tree_Get_Height((*t)->r->r);
(*t)->r->height=lh>rh?lh+1:rh+1;
(*t)->height=Tree_Get_Height((*t)->r)+1;
}
void Tree_ByAVL_Adjust_Left_Height(PTree* t) //调整左高度
{
int lh=Tree_Get_Height((*t)->l->l);
int rh=Tree_Get_Height((*t)->l->r);
(*t)->l->height=lh>rh?lh+1:rh+1;
(*t)->height=Tree_Get_Height((*t)->l)+1;
}
void Tree_ByAVL_Single_Rotate_With_Right(PTree* t) //对于AVL树的右旋操作
{
Tree_Single_Rotate_With_Right(t);
Tree_ByAVL_Adjust_Right_Height(t);
}
void Tree_ByAVL_Single_Rotate_With_Left(PTree* t) //对于AVL树的左旋操作
{
Tree_Single_Rotate_With_Left(t);
Tree_ByAVL_Adjust_Left_Height(t);
}
void Tree_ByAVL_Double_Rotate_With_Left(PTree* t) //对于AVL树的双旋操作,先左后右
{
Tree_Single_Rotate_With_Left(&(*t)->l);
Tree_ByAVL_Adjust_Left_Height(&(*t)->l);
Tree_Single_Rotate_With_Right(t);
Tree_ByAVL_Adjust_Right_Height(t);
}
void Tree_ByAVL_Double_Rotate_With_Right(PTree* t) //对于AVL树的双旋操作,先右后左
{
Tree_Single_Rotate_With_Right(&(*t)->r);
Tree_ByAVL_Adjust_Right_Height(&(*t)->r);
Tree_Single_Rotate_With_Left(t);
Tree_ByAVL_Adjust_Left_Height(t);
}
void Tree_Balance(PTree* t,const int l,const ElemType data,int (*Comp)(const void* p1,const void* p2)) //调整平衡
{
if (l==2&&Comp(&(*t)->l->Data,&data)==1)
Tree_ByAVL_Single_Rotate_With_Right(t);
else if (l==2&&Comp(&(*t)->l->Data,&data)==-1)
Tree_ByAVL_Double_Rotate_With_Left(t);
else if (Comp(&(*t)->r->Data,&data)==-1)
Tree_ByAVL_Single_Rotate_With_Left(t);
else
Tree_ByAVL_Double_Rotate_With_Right(t);
}
int Tree_IsBalance(const PTree t) //判断二叉树平衡情况
{
return Tree_Get_Max(t);
}
void Tree_Pre_Order_Print(const PTree t,int (*Visit)(const PTree t)) //前序遍历树
{
if (t==NULL)
return ;
Tree_Visit(t);
Tree_Pre_Order_Print(t->l,Visit);
Tree_Pre_Order_Print(t->r,Visit);
}
void Tree_In_Order_Print(const PTree t,int (*Visit)(const PTree t)) //中序遍历树
{
if (t==NULL)
return ;
Tree_In_Order_Print(t->l,Visit);
Tree_Visit(t);
Tree_In_Order_Print(t->r,Visit);
}
void Tree_Free(PTree* t) //释放树
{
if (*t==NULL)
return ;
Tree_Free(&(*t)->l);
Tree_Free(&(*t)->r);
Free_Node((void** )t);
}
int Tree_Visit(const PTree t) //输出函数
{
if (t==NULL)
return 0;
printf("%-8d",t->Data);
return 1;
}
PTree Tree_Find_Node(PTree t,ElemType data,int (*Comp)(const void* p1,const void* p2)) //非递归查找信息
{
int k=0;
while (t!=NULL&&(k=Comp(&t->Data,&data)))
if (k==1)
t=t->l;
else
t=t->r;
return t;
}
int Tree_Comp(const void* p1,const void* p2) //比较函数
{
ElemType a=*(ElemType*)p1;
ElemType b=*(ElemType*)p2;
if (a>b)
return 1;
if (a<b)
return -1;
return 0;
}
[此贴子已经被作者于2017-6-12 20:47编辑过]
~~~~~
~我没啥输出调用没发现~现在已经改正~~
