數(shù)據(jù)結(jié)構(gòu)-平衡二叉樹的操作演示

1、平衡二叉樹操作的演示1. 需求分析本程序是利用平衡二叉樹，實現(xiàn)動態(tài)查找表的基本功能：創(chuàng)建表，查找、插入、刪除。具體功能：（1） 初始，平衡二叉樹為空樹，操作界面給出創(chuàng)建、查找、插入、刪除、合并、分裂六種操作供選擇。每種操作均提示輸入關(guān)鍵字。每次插入或刪除一個結(jié)點后，更新平衡二叉樹的顯示。（2） 平衡二叉樹的顯示采用凹入表現(xiàn)形式。 （3） 合并兩棵平衡二叉樹。 （4） 把一棵二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關(guān)鍵字都小于或等于x，另一棵樹中的任一關(guān)鍵字都大于x。如下圖：2概要設(shè)計平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的

2、平衡性，若是則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟：（1） 每當(dāng)插入一個新結(jié)點，從該結(jié)點開始向上計算各結(jié)點的平衡因子，即計算該結(jié)點的祖先結(jié)點的平衡因子，若該結(jié)點的祖先結(jié)點的平衡因子的絕對值不超過1，則平衡二叉樹沒有失去平衡，繼續(xù)插入結(jié)點；（2） 若插入結(jié)點的某祖先結(jié)點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結(jié)點；（3） 判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點個關(guān)系，確定是那種類型的調(diào)整；（4） 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)

3、用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或RL型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；（5） 計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后平衡二叉樹中是否存在平衡因子大于1的結(jié)點。流程圖3. 詳細(xì)設(shè)計二叉樹類型定義：typedef int Status;typedef int ElemType;typedef struct BSTNode       ElemT

4、ype data;       int bf;       struct BSTNode *lchild ,*rchild; BSTNode,* BSTree; Status SearchBST(BSTree T,ElemType e)/查找void R_Rotate(BSTree &p)/右旋void L_Rotate(BSTree &p)/左旋void LeftBalance(BSTree &T)/插入平衡調(diào)整void RightBala

5、nce(BSTree &T)/插入平衡調(diào)整Status InsertAVL(BSTree &T,ElemType e,int &taller)/插入void DELeftBalance(BSTree &T)/刪除平衡調(diào)整void DERightBalance(BSTree &T)/刪除平衡調(diào)整Status Delete(BSTree &T,int &shorter)/刪除操作Status DeleteAVL(BSTree &T,ElemType e,int &shorter)/刪除操作void merge(BSTree &

6、amp;T1,BSTree &T2)/合并操作void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2)/分裂操作void PrintBSTree(BSTree &T,int lev)/凹入表顯示附錄源代碼：#include<stdio.h>#include<stdlib.h>/#define TRUE 1/#define FALSE 0/#define OK 1/#define ERROR 0#define LH +1#define EH 0#define RH -1/二叉類型

7、樹的類型定義typedef int Status;typedef int ElemType;typedef struct BSTNodeElemType data;int bf;/結(jié)點的平衡因子struct BSTNode *lchild ,*rchild;/左、右孩子指針 BSTNode,* BSTree;/*查找算法*/Status SearchBST(BSTree T,ElemType e)if(!T)return 0; /查找失敗else if(e = T->data )return 1; /查找成功else if (e < T->data)return Search

8、BST(T->lchild,e);elsereturn SearchBST(T->rchild,e);/右旋void R_Rotate(BSTree &p)BSTree lc; /處理之前的左子樹根結(jié)點lc = p->lchild; /lc指向的*p的左子樹根結(jié)點p->lchild = lc->rchild; /lc的右子樹掛接為*P的左子樹lc->rchild = p;p = lc; /p指向新的根結(jié)點/左旋void L_Rotate(BSTree &p)BSTree rc;rc = p->rchild; /rc指向的*p的右子樹根結(jié)

9、點p->rchild = rc->lchild; /rc的左子樹掛接為*p的右子樹rc->lchild = p;p = rc; /p指向新的根結(jié)點/對以指針T所指結(jié)點為根結(jié)點的二叉樹作左平衡旋轉(zhuǎn)處理，/本算法結(jié)束時指針T指向新的根結(jié)點void LeftBalance(BSTree &T)BSTree lc,rd;lc=T->lchild;/lc指向*T的左子樹根結(jié)點switch(lc->bf) /檢查*T的左子樹的平衡度，并做相應(yīng)的平衡處理case LH: /新結(jié)點插入在*T的左孩子的左子樹，要做單右旋處理T->bf = lc->bf=EH;R

10、_Rotate(T);break;case RH: /新結(jié)點插入在*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);

11、 /對*T作右旋平衡處理/右平衡旋轉(zhuǎn)處理void RightBalance(BSTree &T)BSTree rc,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

12、=LH;break;ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);/插入結(jié)點Status InsertAVL(BSTree &T,ElemType e,int &taller)/taller反應(yīng)T長高與否if(!T)/插入新結(jié)點，樹長高，置taller為trueT= (BSTree) malloc (sizeof(BSTNode);T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;elseif(e = T->data)tal

13、ler = 0;return 0;if(e < T->data)if(!InsertAVL(T->lchild,e,taller)/未插入return 0;if(taller)/已插入到*T的左子樹中且左子樹長高switch(T->bf)/檢查*T的平衡度，作相應(yīng)的平衡處理case LH:LeftBalance(T);taller = 0;break;case EH:T->bf = LH;taller = 1;break;case RH:T->bf = EH;taller = 0;break;elseif (!InsertAVL(T->rchild,e

14、,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)/刪除平衡調(diào)整BSTree lc,rd;lc=T->lchild;switch(lc->bf)case LH:T->bf =

15、 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);

16、void DERightBalance(BSTree &T) /刪除平衡調(diào)整BSTree rc,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-

17、>bf=EH;break;case RH: T->bf = EH; rc->bf=LH;break;ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);void SDelete(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

18、 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;elseq->lchild = s->lchild;shorter = 1;/刪除結(jié)點Status Delete(BSTree &T,int &shorter)BSTree q;if(!T->rchild)q = T;T = T->lchild;free(q);s

19、horter = 1;else if(!T->lchild)q = T;T= T->rchild;free(q);shorter = 1;elseSDelete(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 &am

20、p;T,ElemType e,int &shorter)int sign = 0;if (!T)return sign;elseif(e = T->data)sign = Delete(T,shorter);return sign;else if(e < T->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;cas

21、e RH:DERightBalance(T);shorter = 0;break;return sign;elsesign = 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 tall

22、er = 0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);/分裂void split(BSTree T,ElemType e,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);elseInsertAVL(T1,T->da

23、ta,taller);split(T->rchild,e,T1,T2);/分裂void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2)BSTree t1 = NULL,t2 = NULL;split(T,e,t1,t2);T1 = t1;T2 = t2;return;/構(gòu)建void CreatBSTree(BSTree &T)int num,i,e,taller = 0;printf("輸入結(jié)點個數(shù):");scanf("%d",&num);printf(&

24、quot;請順序輸入結(jié)點值n");for(i = 0 ;i < num;i+)printf("第%d個結(jié)點的值",i+1);scanf("%d",&e);InsertAVL(T,e,taller) ;printf("構(gòu)建成功，輸入任意字符返回n");getchar();getchar();/凹入表形式顯示方法void PrintBSTree(BSTree &T,int lev)int i;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i = 0;

25、i < lev;i+)printf(" ");printf("%dn",T->data);if(T->lchild)PrintBSTree(T->lchild,lev+1);void Start(BSTree &T1,BSTree &T2)int cho,taller,e,k;taller = 0;k = 0;while(1)system("cls");printf(" 平衡二叉樹操作的演示 nn");printf("*n");printf("

26、平衡二叉樹顯示區(qū) n");printf("T1樹n");if(!T1 )printf("n 當(dāng)前為空樹n");elsePrintBSTree(T1,1);printf("T2樹n");if(!T2 )printf("n 當(dāng)前為空樹n");elsePrintBSTree(T2,1);printf("n*n");printf("T1操作：1.創(chuàng)建 2.插入 3.查找 4.刪除 10.分裂n");printf("T2操作：5.創(chuàng)建 6.插入 7.查找 8.刪除

27、11.分裂n");printf(" 9.合并 T1,T2 0.退出n");printf("*n");printf("輸入你要進行的操作：");scanf("%d",&cho);switch(cho)case 1:CreatBSTree(T1);break;case 2:printf("請輸入要插入關(guān)鍵字的值");scanf("%d",&e);InsertAVL(T1,e,taller) ;break;case 3:printf("請輸入要查

28、找關(guān)鍵字的值");scanf("%d",&e);if(SearchBST(T1,e)printf("查找成功！n");elseprintf("查找失??！n");printf("按任意鍵返回87");getchar();getchar();break;case 4:printf("請輸入要刪除關(guān)鍵字的值");scanf("%d",&e);if(DeleteAVL(T1,e,k)printf("刪除成功！n");elseprintf("刪除失??！n");printf("按任意鍵返回");getchar();getchar();break;case 5:CreatBSTree(T2);break;case 6:printf("請輸入要插入關(guān)鍵字