[原创]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编辑过]