编程双平衡树的创建、插入、删除和查询
# include bits/stdc.h # define lh1//左高#define EH 0 //高#define RH -1 //右高//二叉平衡树using namespace std； int a[105]； typedef struct BTnode{ int data； int bf； BTnode *lchild，*rchild； } BTnode，*BTtree； intdepth(Bttreet ) if (！ t )返回0； else{intm=Depth(t-lchild )； intn=Depth(t-rchild )； if(Mn ) {return m 1； } else{return n 1； }}voidr_rotate(Bttree*t ) /右转) { BTtree L； L=(t )-lchild； (t )-lchild=L-rchild； L-Rchild=(*t )； *T=L； }voidl_rotate(Bttree*t ) /左转) { BTtree R； r=(t )-rchild； (t )-rchild=R-lchild； r-lchild=(*t )； *T=R； }voidleftBalance(Bttree*t ) { BTtree L，Lr； L=(t )-lchild； switch(L-BF ) caseLH://ll ) t )-bf=L-bf=EH； r_rotate(t； 黑； case RH://LR Lr=L-rchild； sitch(lr-BF ) { case LH://左高) t )-bf=RH； L-bf=EH； 黑； case EH://平衡(t )-bf=L-bf=EH； 黑； case RH://右高(t )-bf=EH； L-bf=LH； 黑； (} Lr-bf=EH； L_rotate () t )-lchild )； //左子树左旋处理r_rotate(t )； 向右处理break； case EH://特殊情况4、这种情况在添加时不会出现，只有在去除时才可能出现，转后总体树高仍为L-bf=RH； (t )-bf=LH； r_rotate(t； 黑； }voidrightbalance(Bttree*t ) { BTtree R，Rl； r=(t )-rchild； switch(r-BF ) caseRH://RR ) t )-bf=R-bf=EH； L_rotate(t； 黑； case LH://RL Rl=R-lchild； sitch(rl-BF ) caseLH: ) t )-bf=EH； R-bf=RH； 黑； caseeh:(t )-bf=R-bf=EH； 黑； caseRH:(t )-bf=LH； R-bf=EH； 黑； (} Rl-bf=EH； r_rotate () t )-rchild )； //右子树右旋转处理L_Rotate(T )； //左旋break； case EH://特殊情况4，这在添加时不出现，只可能在去除时出现，旋转后整体树高不变R-bf=LH； (t )-bf=RH； L_rotate(t； 黑； }}BTtree creatBTtree () { BTtree bt=NULL； 返回Bt； } voidinordertraversebttree (bttreet ) /中顺序扫描(if ) t ) )。
InOrderTraverseBTtree(T->lchild); printf("(%d,%d) ",T->bf,T->data); InOrderTraverseBTtree(T->rchild); } else { return; }}int InsertAVL(BTtree *T,int e,int *tall)//插入函数{ if(!*T) { *T=new BTnode; (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH; *tall=1; } else { if(e==(*T)->data) { *tall=0; return 0; } else if(e<(*T)->data)//左子树中寻找 { if(!InsertAVL(&(*T)->lchild,e,tall)) { return 0; } if(*tall) { switch((*T)->bf) { case LH://ll LeftBalance(T); *tall=0; break; case EH: (*T)->bf=LH; *tall=1; break; case RH: (*T)->bf=EH; *tall=0; break; } } } else//右子树中寻找 { if(!InsertAVL(&(*T)->rchild,e,tall)) { return 0; } if(*tall) { switch((*T)->bf) { case LH: (*T)->bf=EH; *tall=0; break; case EH: (*T)->bf=RH; *tall=1; break; case RH: RightBalance(T); *tall=0; break; } } } } return 1;}int SearchBST(BTtree T,int e,BTtree *f,BTtree *p)//寻找元素是否存在//T为当前根节点，e为要查找的元素，f为T的父节点，p为找到的元素节点或没找到时的根节点{ if(!T)//若树空 { *p=*f; return 0; } else if(T->data==e)//若找到该元素 { *p=T; return 1; } else if(e<T->data)//如果该元素比根节点值小 return SearchBST(T->lchild,e,&T,p); else//如果该元素比根节点值大 return SearchBST(T->rchild,e,&T,p);}int deleteAVL(BTtree &t,BTtree *f,int e,int *shorter){ if(t==NULL) { return 0; } else if(t->data==e) { BTtree q=NULL; if(t->lchild==NULL)//左子树为空 { q=t; t=t->rchild; free(q); *shorter=1; } else if(t->rchild==NULL)//右子树为空 { q=t; t=t->lchild; free(q); *shorter=1; } else//左右子树都存在 { BTtree s=t; q=t->lchild; while(q->rchild) { s=q; q=q->rchild; } t->data=q->data; deleteAVL(t->lchild,&t,q->data,shorter);//在左子树中递归删除前驱结点 } } else if(e<t->data)//左子树中继续查找 { if(!deleteAVL(t->lchild,&t,e,shorter)) { return 0; } if(*shorter) { switch(t->bf) { case LH://若原来LH，删除左节点，状态变为EH t->bf=EH; *shorter=1; break; case EH://若原来平衡，删除左节点，状态变为RH t->bf=RH; *shorter=0; break; case RH: if(t->rchild->bf==EH) *shorter=0; else *shorter=1;//若为此情况，树高减一 RightBalance(&t);//右平衡处理 break; } } } else//右子树中继续查找 { if(!deleteAVL(t->rchild,&t,e,shorter)) { return 0; } if(*shorter) { switch(t->bf) { case LH: if(t->lchild->bf==EH)//若为此情况，树高减一 *shorter=0; else *shorter=1; LeftBalance(&t);//左平衡处理 break; case EH://若原来平衡，删除右节点，状态变为LH t->bf=LH; *shorter=0; break; case RH://若原来RH，删除右节点，状态变为EH t->bf=EH; *shorter=1; break; } } } return 1;}int main(){ BTtree T,p,f; T=creatBTtree(); int x,n; int tall,shorter; n=0; printf("请输入你要创建二叉平衡树的数字，输入0表示结束输入："); while(~scanf("%d",&x)) { if(!x) break; a[++n]=x; } for(int i=1; i<=n; i++) { InsertAVL(&T,a[i],&tall); } printf("中序遍历该二叉平衡树的结果为："); InOrderTraverseBTtree(T); printf("n"); int num; printf("请输入你要插入的数字："); cin>>num; InsertAVL(&T,num,&tall); printf("插入该数字后中序遍历该二叉排序树的结果为："); InOrderTraverseBTtree(T); printf("n"); int xx,y; printf("请输入你要查询的数字："); cin>>xx; f=NULL; if(SearchBST(T,xx,&f,&p)) { printf("该数存在n"); } else { printf("该数不存在n"); } printf("请输入你要删除的数字："); cin>>y; f=NULL; if(!SearchBST(T,y,&f,&p)) { printf("该数不存在，无法进行删除操作！n"); } else { deleteAVL(T,&f,y,&shorter); printf("进行删除操作后中序遍历该二叉排序树的结果为："); InOrderTraverseBTtree(T); } printf("平衡二叉树的深度：%d",Depth(T)); printf("n"); return 0;}/*1 5 4 2 6 8 7 9 11 14 13 12 16 19 0*/