数据结构 平衡二叉树的操作演示_平衡二叉树操作演示

数据结构 平衡二叉树的操作演示由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“平衡二叉树操作演示”。

平衡二叉树操作的演示

1.需求分析

本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能：

（1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。

（2）平衡二叉树的显示采用凹入表现形式。（3）合并两棵平衡二叉树。

（4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。

如下图：

2．概要设计

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤：

（1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；

（2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

（3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。流程图

3.详细设计

二叉树类型定义： typedefint Status;typedefintElemType;typedefstructBSTNode{

ElemType data;

int bf;

structBSTNode *lchild ,*rchild;} BSTNode,* BSTree;

Status SearchBST(BSTreeT,ElemType e)//查找 void R_Rotate(BSTree&p)//右旋 void L_Rotate(BSTree&p)//左旋

void LeftBalance(BSTree&T)//插入平衡调整 void RightBalance(BSTree&T)//插入平衡调整

Status InsertAVL(BSTree&T,ElemTypee,int&taller)//插入 void DELeftBalance(BSTree&T)//删除平衡调整 void DERightBalance(BSTree&T)//删除平衡调整 Status Delete(BSTree&T,int&shorter)//删除操作

Status DeleteAVL(BSTree&T,ElemTypee,int&shorter)//删除操作 void merge(BSTree&T1,BSTree &T2)//合并操作

void splitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2)//分裂操作 void PrintBSTree(BSTree&T,intlev)//凹入表显示

附录

源代码：

#include #include //#define TRUE 1 //#define FALSE 0 //#define OK 1 //#define ERROR 0 #define LH +1 #define EH 0 #define RH-1 //二叉类型树的类型定义 typedefint Status;typedefintElemType;typedefstructBSTNode{ ElemType data;int bf;//结点的平衡因子

structBSTNode *lchild ,*rchild;//左、右孩子指针 } BSTNode,* BSTree;/* 查找算法 */ Status SearchBST(BSTreeT,ElemType e){ if(!T){ return 0;//查找失败 } else if(e == T->data){ return 1;//查找成功 } else if(e data){ returnSearchBST(T->lchild,e);} else{ returnSearchBST(T->rchild,e);} }

//右旋

voidR_Rotate(BSTree&p){ BSTreelc;//处理之前的左子树根结点

lc = p->lchild;//lc指向的*p的左子树根结点

p->lchild = lc->rchild;//lc的右子树挂接为*P的左子树 lc->rchild = p;p = lc;//p指向新的根结点

} //左旋

voidL_Rotate(BSTree&p){ BSTreerc;rc = p->rchild;//rc指向的*p的右子树根结点

p->rchild = rc->lchild;//rc的左子树挂接为*p的右子树 rc->lchild = p;p = rc;//p指向新的根结点 } //对以指针T所指结点为根结点的二叉树作左平衡旋转处理，//本算法结束时指针T指向新的根结点 voidLeftBalance(BSTree&T){ BSTreelc,rd;lc=T->lchild;//lc指向*T的左子树根结点

switch(lc->bf){ //检查*T的左子树的平衡度，并做相应的平衡处理

case LH:

//新结点插入在*T的左孩子的左子树，要做单右旋处理 T->bf = lc->bf=EH;R_Rotate(T);break;case RH:

//新结点插入在*T的左孩子的右子树上，做双旋处理 rd=lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf){ //修改*T及其左孩子的平衡因子 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);//对*T的左子树作左旋平衡处理 R_Rotate(T);//对*T作右旋平衡处理 } } //右平衡旋转处理

voidRightBalance(BSTree&T){ BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} } //插入结点

Status InsertAVL(BSTree&T,ElemTypee,int&taller){//taller反应T长高与否 if(!T){//插入新结点，树长高，置taller为true T=(BSTree)malloc(sizeof(BSTNode));T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;} else{ if(e == T->data){ taller = 0;return 0;} if(e data){ if(!InsertAVL(T->lchild,e,taller))//未插入 return 0;if(taller)//已插入到*T的左子树中且左子树长高

switch(T->bf){//检查*T的平衡度，作相应的平衡处理 case LH: LeftBalance(T);taller = 0;break;case EH: T->bf = LH;taller = 1;break;case RH: T->bf = EH;taller = 0;break;} } else{ if(!InsertAVL(T->rchild,e,taller)){ return 0;} if(taller)//插入到*T的右子树且右子树增高 switch(T->bf){//检查*T的平衡度 case LH: T->bf = EH;taller = 0;break;case EH: T->bf = RH;taller = 1;break;case RH: RightBalance(T);taller = 0;break;} } } return 1;}

void DELeftBalance(BSTree&T){//删除平衡调整 BSTreelc,rd;lc=T->lchild;switch(lc->bf){ case LH: T->bf = EH;//lc->bf= EH;R_Rotate(T);break;case EH: T->bf = EH;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 DERightBalance(BSTree&T)//删除平衡调整 { BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case EH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} }

voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter){ if(s->rchild){ SDelete(T,s,s->rchild,shorter);if(shorter)switch(s->bf){ case EH: s->bf = LH;shorter = 0;break;case RH: s->bf = EH;shorter = 1;break;case LH: DELeftBalance(s);shorter = 0;break;} return;}

T->data = s->data;if(q!= T)q->rchild = s->lchild;else q->lchild = s->lchild;shorter = 1;} //删除结点

Status Delete(BSTree&T,int&shorter){ BSTree q;if(!T->rchild){ q = T;T = T->lchild;free(q);shorter = 1;} else if(!T->lchild){ q = T;T= T->rchild;free(q);shorter = 1;} else{ SDelete(T,T,T->lchild,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;} } return 1;}

Status DeleteAVL(BSTree&T,ElemTypee,int&shorter){ int sign = 0;if(!T){ return sign;} else{ if(e == T->data){ sign = Delete(T,shorter);return sign;}

else if(e data){ sign = DeleteAVL(T->lchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;}

return sign;} else{ sign = DeleteAVL(T->rchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = LH;shorter = 0;break;case RH: T->bf = EH;break;case LH: DELeftBalance(T);shorter = 0;break;} return sign;}

} } //合并

void merge(BSTree&T1,BSTree &T2){ int taller = 0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);} //分裂

void split(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ int taller = 0;if(!T)return;split(T->lchild,e,T1,T2);if(T->data > e)InsertAVL(T2,T->data,taller);else InsertAVL(T1,T->data,taller);split(T->rchild,e,T1,T2);} //分裂

voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ BSTree t1 = NULL,t2 = NULL;split(T,e,t1,t2);T1 = t1;T2 = t2;return;}

//构建

voidCreatBSTree(BSTree&T){ intnum,i,e,taller = 0;printf(“输入结点个数:”);scanf(“%d”,&num);printf(“请顺序输入结点值n”);for(i = 0;i

voidPrintBSTree(BSTree&T,intlev){ int i;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i = 0;i data);if(T->lchild)PrintBSTree(T->lchild,lev+1);} void Start(BSTree&T1,BSTree &T2){

intcho,taller,e,k;taller = 0;k = 0;while(1){ system(“cls”);printf(“ 平衡二叉树操作的演示 nn”);printf(“********************************n”);printf(“ 平衡二叉树显示区 n”);printf(“T1树n”);if(!T1)printf(“n 当前为空树n”);else{ PrintBSTree(T1,1);}

printf(“T2树n”);if(!T2)printf(“n 当前为空树n”);else PrintBSTree(T2,1);printf(“n******************************************************************************n”);printf(“T1操作：1.创建 2.插入 3.查找 4.删除 10.分裂n”);printf(“T2操作：5.创建 6.插入 7.查找 8.删除 11.分裂n”);printf(“ 9.合并 T1,T2 0.退出n”);printf(“******************************************************************************n”);printf(“输入你要进行的操作：”);scanf(“%d”,&cho);switch(cho){ case 1: CreatBSTree(T1);break;case 2: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T1,e,taller);break;case 3: printf(“请输入要查找关键字的值”);scanf(“%d”,&e);

if(SearchBST(T1,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回87”);getchar();getchar();break;case 4: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T1,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 5: CreatBSTree(T2);break;case 6: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T2,e,taller);break;case 7: printf(“请输入要查找关键字的值”);scanf(“%d”,&e);

if(SearchBST(T2,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 8: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T2,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 9: merge(T1,T2);T2 = NULL;printf(“合并成功，按任意键返回”);getchar();getchar();break;case 10: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T1,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 11: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T2,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 0: system(“cls”);exit(0);} } }

main(){ BSTree T1 = NULL;BSTree T2 = NULL;Start(T1,T2);}