平衡二叉树算法实现

#includestdio.h#includemalloc.h#includestdlib.h#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)(b))#defineLH+1//左高#defineEH0//等高#defineRH-1//右高#defineNULL0/////////////////////////////定义结构体///////////////////////////typedefstructBSTNode{intdata;intbf;//结点的平衡因子structBSTNode*lchild,*rchild;//左、右孩子指针}BSTNode,*BSTree;///////////////////////////函数声明///////////////////////////voidR_Rotate(BSTree&p);//对以*p为根的二叉排序树作右旋处理voidL_Rotate(BSTree&p);//对以*p为根的二叉排序树作左旋处理voidLeftBalance(BSTree&T);//对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理voidRightBalance(BSTree&T);//对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理boolInsertAVL(BSTree&T,inte,bool&taller);//插入结点eboolSearchBST(BSTree&T,intkey);//查找元素key是否在树Ｔ中voidPrintBST(BSTreeT,intm);//按树状打印输出二叉树的元素voidCreatBST(BSTree&T);//创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)voidLeftBalance_div(BSTree&p,int&shorter);//删除结点时左平衡旋转处理voidRightBalance_div(BSTree&p,int&shorter);//删除结点时右平衡旋转处理voidDelete(BSTreeq,BSTree&r,int&shorter);//删除结点intDeleteAVL(BSTree&p,intx,int&shorter);//平衡二叉树的删除操作/////////////////////////////////////////////////////////////////////voidmain(){intinput,search,m;booltaller=false;intshorter=0;BSTreeT,T1,T2;T=(BSTree)malloc(sizeof(BSTNode));T=T1=T2=NULL;while(1){system(cls);printf(******************************************\n);printf(╱◥██◣*1.创建\t2.查找\t3.插入\t4.删除\t5.退出*\n);printf(｜田｜田田│******************************************\n);printf(╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬平衡二叉树晓奇制作V1.0\n);printf(请输入您所需的操作功能:\t);scanf(%d,&input);getchar();switch(input){case1:CreatBST(T);break;case2:printf(请输入你要查找的关键字);scanf(%d,&search);getchar();if(SearchBST(T,search))printf(该二叉树中存在关键字%d，查找成功!\n,search);elseprintf(查找失败!\n);break;case3:printf(请输入你要插入的关键字);scanf(%d,&search);getchar();InsertAVL(T,search,taller);m=0;PrintBST(T,m);break;case4:printf(请输入你要删除的关键字);scanf(%d,&search);getchar();DeleteAVL(T,search,shorter);m=0;PrintBST(T,m);break;case5:printf(\t\tbyebye!\n);break;default:printf(输入错误，请重新选择。);break;}if(input==5)break;printf(\t\t按任意键继续...);getchar();}}//对以*p为根的二叉排序树作右旋处理voidR_Rotate(BSTree&p){BSTreelc;lc=p-lchild;//lc指向的*p左子树根结点p-lchild=lc-rchild;//rc的右子树挂接为*p的左子树lc-rchild=p;p=lc;//p指向新的结点}//对以*p为根的二叉排序树作左旋处理voidL_Rotate(BSTree&p){BSTreerc;rc=p-rchild;//rc指向的*p右子树根结点p-rchild=rc-lchild;//rc的左子树挂接为*p的右子树rc-lchild=p;p=rc;//p指向新的结点}//对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理voidLeftBalance(BSTree&T){BSTreelc,rd;lc=T-lchild;//lc指向*T的左子树根结点switch(lc-bf)//检查*T的左子树的平衡度，并作相应平衡处理{caseLH://新结点插入在*T的左孩子的左子树上，要作单右旋处理T-bf=lc-bf=EH;R_Rotate(T);break;caseRH://新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc-rchild;//rd指向*T的左孩子的右子树根switch(rd-bf)//修改*T及其左孩子的平衡因子{caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;}rd-bf=EH;L_Rotate(T-lchild);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T作右旋平衡处理}}//对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理voidRightBalance(BSTree&T){BSTreerc,ld;rc=T-rchild;//rc指向*T的左子树根结点switch(rc-bf)//检查*T的右子树的平衡度，并作相应平衡处理{caseRH://新结点插入在*T的右孩子的右子树上，要作单左旋处理T-bf=rc-bf=EH;L_Rotate(T);break;caseLH://新结点插入在*T的右孩子的左子树上，要作双旋处理ld=rc-lchild;//ld指向*T的右孩子的左子树根switch(ld-bf)//修改*T及其右孩子的平衡因子{caseLH:T-bf=EH;rc-bf=RH;break;caseEH:T-bf=rc-bf=EH;break;caseRH:T-bf=LH;rc-bf=EH;break;}ld-bf=EH;R_Rotate(T-rchild);//对*T的右子树作左旋平衡处理L_Rotate(T);//对*T作左旋平衡处理}}//插入结点e,若Ｔ中存在和e相同关键字的结点，则插入一个数据元素为e的新结点，并返回１，否则返回０boolInsertAVL(BSTree&T,inte,bool&taller){if(!T)//插入新结点，树“长高”，置taller为true{T=(BSTree)malloc(sizeof(BSTNode));T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;}else{if(EQ(e,T-data))//树中已存在和有相同关键字的结点{taller=false;printf(已存在相同关键字的结点\n);return0;}//则不再插入if(LT(e,T-data))//应继续在*T的左子树中进行搜索{if(!InsertAVL(T-lchild,e,taller))return0;//未插入if(taller)//已插入到*T的左子树中且左子树“长高”switch(T-bf)//检查*T的平衡度{caseLH://原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller=false;break;caseEH://原本左子树、右子等高，现因左子树增高而使树增高T-bf=LH;taller=true;break;caseRH://原本右子树比左子树高，现左、右子树等高T-bf=EH;taller=false;break;}//switch(T-bf)}//ifelse//应继续在*T的右子树中进行搜索{if(!InsertAVL(T-rchild,e,taller))return0;//未插入if(taller)//已插入到*T的右子树中且右子树“长高”switch(T-bf)//检查*T的平衡度{caseLH://原本左子树比右子树高，现左、右子树等高T-bf=EH;taller=false;break;caseEH://原本左子树、右子等高，现因右子树增高而使树增高T-bf=RH;taller=true;break;caseRH://原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=false;break;}//switch(T-bf)}//else}//elsereturn1;}//InsertAVL//查找元素key是否在树Ｔ中boolSearchBST(BSTree&T,intkey){if(!T)returnfalse;elseif(EQ(key,T-data))returntrue;elseif(LT(key,T-data))returnSearchBST(T-lchild,key);elsereturnSearchBST(T-rchild,key);}//按树状打印输出二叉树的元素,m表示结点所在层次,初次调用时m=ovoidPrintBST(BSTreeT,intm){inti;if(T-rchild)PrintBST(T-rchild,m+1);for(i=1;i=m;i++)printf();//打印i个空格以表示出层次printf(%d\n,T-data);//打印T元素,换行if(T-lchild)PrintBST(T-lchild,m+1);}//创建平衡二叉树，（注意：以输入－１为二叉树建立的结束）voidCreatBST(BSTree&T){inte,m;booltaller=false;T=NULL;printf(\n请输入关键字(以-1结束建立平衡二叉树):);scanf(%d,&e);getchar();while(e!=-1){InsertAVL(T,e,taller);printf(\n请输入关键字(以-1结束建立平衡二叉树):);scanf(%d,&e);getchar();taller=false;}m=0;printf(平衡二叉树创建结束,横向打印出树状结构：\n);if(T)PrintBST(T,m);elseprintf(这是一棵空树.\n);}//删除结点时左平衡旋转处理voidLeftBalance_div(BSTree&p,int&shorter){BSTreep1,p2;if(p-bf==1)//p结点的左子树高，删除结点后p的bf减1,树变矮{p-bf=0;shorter=1;}