平衡二叉树操作的演示

#include <stdio.h> #include <malloc.h> #include "bstree.h" //右旋转处理函数 void R_Rotate( BSTree &p) { BSTree lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } //左旋转处理函数 void L_Rotate(BSTree &p) { BSTree rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; } #define LH 1 #define EH 0 #define RH -1 //创建平衡二叉树函数 int CreatAVL(BSTree &T,bool &taller) { ElemType e; int insert; if(T) //判断平衡二叉树是否为空，若不空则将该树释放 { DestroyAVL(T); T=NULL; } printf("\n■请输入要构造的平衡二叉树: "); fflush(stdin); e=getchar(); while(e!='\n') //循环调用插入函数来构造平衡二叉树 { InsertAVL(T,e,taller,insert); e=getchar(); } return 1; } //插入函数 int InsertAVL(BSTree &T,ElemType e,bool &taller,int &insert) { 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)) //树中已存在和e相同的节点 { insert = 0; //将标志变量置0 taller=false; //不再进行插入操作 return 0; } if(LT(e,T->data)) //左子树插入操作 { if(!InsertAVL(T->lchild,e,taller,insert)) return 0; if(taller) //如果有进行插入操作则进行平衡树的平衡处理 switch(T->bf) { case LH:LeftBalance(T); taller=false; break; case EH:T->bf=LH; taller=true; break; case RH:T->bf=EH; taller=false; break; } } else //右子树的插入操作 { if(!InsertAVL(T->rchild,e,taller,insert)) return 0; if(taller) //如果有进行插入操作则进行平衡树的平衡处理 switch(T->bf) { case LH:T->bf=EH; taller=false; break; case EH:T->bf=RH; taller=true; break; case RH:RightBalance(T); taller=false; break; } } } return 1; } //插入操作时左平衡旋转处理函数 void LeftBalance(BSTree &T) { BSTree lc,rd; lc=T->lchild; switch(lc->bf) //检查T的左子树的平衡度，并作相应的平衡处理 { case LH:T->bf=lc->bf=EH; R_Rotate(T); break; case RH:rd=lc->rchild; switch(rd->bf) { case LH:T->bf=RH; lc->bf=EH; break; case EH:T->bf=lc->bf=EH; break; case RH:T->bf=EH; lc->bf=LH; break; } rd->bf=EH; L_Rotate(T->lchild); R_Rotate(T); } } //插入操作时右平衡旋转处理函数 void RightBalance(BSTree &T) { BSTree rc,ld; rc=T->rchild; switch(rc->bf) //检查T的右子树的平衡度，并作相应的平衡处理 { case RH:T->bf=rc->bf=EH; L_Rotate(T); break; case LH:ld=rc->lchild; switch(ld->bf) { case LH:T->bf=EH; rc->bf=RH; break; case EH:T->bf=rc->bf=EH; break; case RH:T->bf=LH; rc->bf=EH; break; } ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); } } //销毁平衡二叉树操作函数 int DestroyAVL(BSTree &T) { if(!T) return 0; DestroyAVL(T->lchild); //递归调用该函数销毁整棵平衡二叉树 DestroyAVL(T->rchild); free(T); return 0; } //查找关键字函数 int SearchAVL(BSTree &T,ElemType e,int &find) { if(!T) return 0; if(EQ(e,T->data)) { find = 1; //若查找到该关键字则将find置1 return 0; } else if(LT(e,T->data)) SearchAVL(T->lchild,e,find); else SearchAVL(T->rchild,e,find); return 0; } //删除关键字函数 int DeleteAVL(BSTree &T,ElemType e,bool &taller,int &del) { ElemType temp; BSTree p; if(!T) { del = 0; //若到叶子节点了还未找到则将del置0 return 0; } else { if(EQ(e,T->data)) { taller=true; //关键字存在时进行删除操作，将taller置为true if(T->lchild == NULL && T->rchild == NULL) //若为叶子节点则删除节点 { free(T); T = NULL; } else if(T->lchild) //若左子树不空，则将T->data与左子树的最右的孩子交换 { p = T->lchild; while(p->rchild != NULL) p = p->rchild; temp = T->data; T->data = p->data; p->data = temp; if(!DeleteAVL(T->lchild,e,taller,del)) //递归调用左子树 return 0; if(taller) //若树不平衡则进行平衡处理 switch(T->bf) { case LH:T->bf=EH; taller=true; break; case EH:T->bf=RH; taller=false; break; case RH:RightBalance2(T,taller); break; } } else //若左空，右子树不空，则将T->data与右子树的最左的孩子交换 { p = T->rchild; while(p->lchild != NULL) p = p->lchild; temp = T->data; T->data = p->data; p->data = temp; if(!DeleteAVL(T->rchild,e,taller,del)) //递归调用左子树 return 0; if(taller) //若树不平衡则进行平衡处理 switch(T->bf) { case LH:LeftBalance2(T,taller); taller=true; break; case EH:T->bf=LH; taller=false; break; case RH:T->bf=EH; taller=true; break; } } return 1; } if(LT(e,T->data)) { if(!DeleteAVL(T->lchild,e,taller,del)) //当e小于T->data时递归调用其左子树 return 0; if(taller) //若树不平衡则进行平衡处理 switch(T->bf) { case LH:T->bf=EH; taller=true; break; case EH:T->bf=RH; taller=false; break; case RH:RightBalance2(T,taller); break; } } else { if(!DeleteAVL(T->rchild,e,taller,del)) //当e大于T->data时递归调用其左子树 return 0; if(taller) //若树不平衡则进行平衡处理 switch(T->bf) { case LH:LeftBalance2(T,taller); break; case EH:T->bf=LH; taller=false; break; case RH:T->bf=EH; taller=true; break; } } } return 1; } //删除关键字时的右平衡旋转处理函数 void RightBalance2(BSTree &T,bool &taller) { BSTree rc,ld; rc=T->rchild; switch(rc->bf) //检查T的左子树的平衡度，并作相应的平衡处理 { case RH:T->bf=rc->bf=EH; L_Rotate(T); taller = true; break; case EH:T->bf=RH; rc->bf=LH; L_Rotate(T); taller = false; break; case LH:ld=rc->lchild; switch(ld->bf) { case LH:T->bf=EH; rc->bf=RH; break; case EH:T->bf=rc->bf=EH; break; case RH:T->bf=LH; rc->bf=EH; break; } ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); taller = true; break; } } //删除关键字时的左平衡旋转处理函数 void LeftBalance2(BSTree &T,bool &taller) { BSTree lc,rd; lc=T->lchild; switch(lc->bf) //检查T的右子树的平衡度，并作相应的平衡处理 { case LH:T->bf=lc->bf=EH; R_Rotate(T); taller = true; break; case EH:T->bf=LH; lc->bf=RH; R_Rotate(T); taller = false; break; case RH:rd=lc->rchild; switch(rd->bf) { case LH:T->bf=RH; lc->bf=EH; break; case EH:T->bf=lc->bf=EH; break; case RH:T->bf=EH; lc->bf=LH; break; } rd->bf=EH; L_Rotate(T->lchild); R_Rotate(T); taller = true; break; } } //合并两棵平衡二叉树的操作函数 int MergeAVL(BSTree &T1,BSTree &T2,bool &taller,int &insert) { if(!T2) return 0; MergeAVL(T1,T2->lchild,taller,insert); //用左右孩子上的递归操作实现合并操作 InsertAVL(T1,T2->data,taller,insert); MergeAVL(T1,T2->rchild,taller,insert); InsertAVL(T1,T2->data,taller,insert); return 1; } //输出平衡二叉树的函数 void PrintAVL(BSTree &T,int n) { int i; if(T) { PrintAVL(T->rchild,n+1); //递归输出 for(i=0;i<n;++i) printf(" "); printf("%c\n",T->data); PrintAVL(T->lchild,n+1); } }