實驗報告-平衡二叉樹

1、實習(xí)報告一、需求分析1、問題描述 利用平衡二叉樹實現(xiàn)一個動態(tài)查找表。（1）實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。（2）初始時，平衡二叉樹為空樹，操作界面給出查找、插入和刪除三種操作供選擇。每種操作均要提示輸入關(guān)鍵字。在查找時，如果查找的關(guān)鍵字不存在，則把其插入到平衡二叉樹中。每次插入或刪除一個結(jié)點后，應(yīng)更新平衡二叉樹的顯示。（3）每次操作的關(guān)鍵字都要從文件中讀取，并且關(guān)鍵字的集合限定為短整型數(shù)字1，2，3，關(guān)鍵字出現(xiàn)的順序沒有限制，允許出現(xiàn)重復(fù)的關(guān)鍵字，并對其進行相應(yīng)的提示。（4）平衡二叉樹的顯示采用圖形界面畫出圖形。 2、系統(tǒng)功能 打開數(shù)據(jù)文件，用文件中的關(guān)鍵字來演示平衡二叉樹操作

2、的過程。 3、程序中執(zhí)行的命令包括： （1）(L)oad from data file /在平衡的二叉樹中插入關(guān)鍵字； （2）(A)ppend new record /在平衡的二叉樹中查找關(guān)鍵字； （3）(U)pate special record /顯示調(diào)整過的平衡二叉樹； （4）(D)elete special record /刪除平衡二叉樹中的關(guān)鍵字； （5）(Q)uit /結(jié)束。 4、測試數(shù)據(jù)： 平衡二叉樹為：圖 1 插入關(guān)鍵字10之前的平衡二叉樹插入關(guān)鍵字：10； 調(diào)整后：圖 2 插入關(guān)鍵字10之后的平衡二叉樹 刪除關(guān)鍵字：14； 調(diào)整后： 圖 3 刪除關(guān)鍵字14后的平衡二叉樹 查找

3、關(guān)鍵字：11； 輸出： The data is here!圖 3 查找關(guān)鍵字11后的平衡二叉樹二、概要設(shè)計 本次實驗?zāi)康氖菫榱藢崿F(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。動態(tài)查找表可有不同的表示方法，在此次實驗中主要是以平衡二叉樹的結(jié)構(gòu)來表示實現(xiàn)的，所以需要兩個抽象數(shù)據(jù)類型：動態(tài)查找表和二叉樹。1、 動態(tài)查找表的抽象數(shù)據(jù)類型定義為：ADT DynamicSearchTable數(shù)據(jù)對象 D ：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系 R ：數(shù)據(jù)元素同屬于一個集合。 基本操作 P ： InitDSTable(&ST); 操作結(jié)果：構(gòu)造

4、一個空的動態(tài)查找表DT。 DestroyDSTable(&DT); 初始條件：動態(tài)查找表DT存在。 操作結(jié)果：銷毀動態(tài)查找表DT。 SearchDSTable(DT,key); 初始條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給丁值。 操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。 InsertDSTable(&DT,e); 初始條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素。 操作結(jié)果：若DT中不存在其關(guān)鍵字等于e，key的數(shù)據(jù)元素，則插入e到DT； DeleteDSTable(&DT,key); 初始條件：動態(tài)查找表DT存在，

5、key為和關(guān)鍵字類型相同的給定值。 操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。ADT DynamicSearchTable2、 二叉樹抽象數(shù)據(jù)類型的定義為：ADT BinaryTree數(shù)據(jù)對象 D ：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R ： 若D=，則R=，稱BinaryTree為空的二叉樹； 若D，則R=H，H是如下二元關(guān)系：（1） 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2） 若Droot，則存在Droot=D1，Dr，且D1Dr=;（3） 若D1，則D1中存在唯一的元素x1，H，且存在D1上的關(guān)系H1H；若Dr，則Dr中存在唯一的元

6、素xr，H，且存在Dr上的關(guān)系HrH；H=，H1，Hr；（4） （D1，H1）是一棵符合本定義的二叉樹，稱為根的左子樹，（Dr，Hr）是符合本定義的二叉樹，稱為根的右子樹。基本操作 P：InitBiTree(&T);操作結(jié)果：構(gòu)造空的二叉樹T；DestroyBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree(&T,definition);初始條件：definition給出T的定義。操作結(jié)果：按definition構(gòu)造二叉樹T。BiTreeEmpty(T);初始條件：二叉樹T存在。操作結(jié)果：若T為空二叉樹，則返回TRUE，否則FALSE。LeftChi

7、ld(T,e);初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：返回e的左孩子。若e無左孩子，則返回“空”。RightChild(T,e);初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：返回e的右孩子。若e無右孩子，則返回“空”。InsertAVL(T,e,taller);初始條件：二叉樹T存在，e為要插入的結(jié)點，taller反映T長高與否。操作結(jié)果：若在平衡二叉樹中不存在和e相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為e的結(jié)點，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則旋轉(zhuǎn)處理。RightProcess(T);初始條件：二叉樹T存在。操作結(jié)果：對以T為根的二叉樹做右旋轉(zhuǎn)處理

8、，處理之后T指向新的樹根結(jié)點。LeftProcess(T);初始條件：二叉樹T存在。操作結(jié)果：對以T為根的二叉樹做左旋轉(zhuǎn)處理，處理之后T指向新的樹根結(jié)點3、 本程序包括四個模塊：（1）主程序模塊： void main() for(;) switch()接受命令；處理命令； （2）二叉樹單元模塊： 實現(xiàn)二叉樹的抽象數(shù)據(jù)類型。（3）動態(tài)查找表單元模塊： 實現(xiàn)動態(tài)查找表的抽象數(shù)據(jù)類型。（4）結(jié)點結(jié)構(gòu)模塊： 實現(xiàn)平衡二叉樹的查找、插入和刪除操作。 各模塊之間的關(guān)系：主程序模塊二叉樹單元模塊：動態(tài)查找表單元模塊結(jié)點結(jié)構(gòu)模塊圖 4 各模塊之間的關(guān)系三、詳細(xì)設(shè)計1、元素類型、結(jié)點類型和指針類型； typed

9、ef int InfoTypetypedef struct node /*記錄類型*/ InfoType data; /*其他數(shù)據(jù)域*/ Struct node lchild, rchild; /*左右孩子指針*/BSTNode,*BSTree;status MakeNode(BSTNode &p,ElemType e) /* 分配由p指向的數(shù)據(jù)元素為e、后繼為空的結(jié)點,并返回 TRUE,擴若分配失敗,則返回FALSE*/p=(BSTNode*)malloc(sizeof(BSTNode);if(!p) return FALSE;p-data=e;p-next =NULL;return TRU

10、E;void FreeNode(BSTNode &p)/* 釋放 p 所指結(jié)點*/2、 根據(jù)動態(tài)查找表的基本操作特點：表結(jié)構(gòu)本身是在查找過程中動態(tài)產(chǎn)生的，即對于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。在此次試驗中主要是利用平衡二叉樹來實現(xiàn)動態(tài)查找表。平衡二叉排序樹定義為： typedef int InfoType typedef int KeyType; /*元素類型*/ typedef struct nodeKeyType key; /*關(guān)鍵字項*/ int bf; /*平衡因子*/ InfoType data; /*其他數(shù)據(jù)域*/

11、Struct node lchild, rchild; /*左右孩子指針*/ BSTNode,*BSTree; int taller; /*taller=0,平衡二叉數(shù)沒有長高不需要調(diào)整；taller=1,二叉數(shù)長高,需要驗證是否還是平衡二叉數(shù),如果不是,則需要進行調(diào)整.*/ 平衡二叉樹的基本操作定義如下： int InsertAVL(BSTNode *b,KeyType e,int *m); /如果在平衡二叉排序樹b中不存在e有相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為e的新結(jié)點，并返回1，否則返回0.如果因插入而使二叉排序樹失去平衡，則做平衡處理，指針m反應(yīng)b長高與否。 void LeftPr

12、ocess(BSTree *p,int *m); /在插入結(jié)點時對以指針p所指結(jié)點為根的二叉樹做左平衡旋轉(zhuǎn)處理。 void RightProcess(BSTree *p,int *m); /在插入結(jié)點時對以指針p所指結(jié)點為根的二叉樹做右平衡旋轉(zhuǎn)處理。 int DeleteAVL(BSTree *p,KeyType x,int *m);/ /在以p為根的平衡二叉樹中刪除關(guān)鍵字為e的結(jié)點，如果因刪除而使平衡二叉樹失去平衡，則做平衡處理，指針m反應(yīng)b樹長高與否。 void LeftProcess1(BSTree *p,int *m); /由DeleteAVL()函數(shù)調(diào)用，在刪除結(jié)點時進行左處理。 v

13、oid RightProcess1(BSTree *p,int *m); /由DeleteAVL()函數(shù)調(diào)用，在刪除結(jié)點時進行右處理。 void Delete2(BSTree q,BSTree *r,int *m); /由DeleteAVL（）調(diào)用，用于處理被刪除結(jié)點都不為空的情況。 void DrawTree(BSTree b); /對以b為根的平衡二叉樹，以括號的形式顯示出來。 void OutputTree(BSTree b,int fx,int fy,int prex,int prey); /用圖形把平衡二叉樹顯示出來。3、 本程序?qū)崿F(xiàn)的是演示平衡二叉樹的操作過程，包括插入和刪除操作，

14、以下是它們算法的設(shè)計。（1） 插入數(shù)據(jù)操作，如果數(shù)據(jù)存在，輸出提示信息，如果不存在，則把此數(shù)據(jù)插入到入平衡二叉樹中，并做相應(yīng)的調(diào)整，使之還為平衡二叉樹。以下是對插入操作的設(shè)計。 int InsertAVL(BSTree *b,KeyType e,int *m)/*若在平衡的二叉排序樹中b中不存在和e有相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為e的新結(jié)點，并返回0。若因插入而使二叉排序樹失去平衡，則做平衡旋轉(zhuǎn)處理，taller的值反應(yīng)長高與否。*/ if(*b=NULL) /*原為空樹，插入新結(jié)點，樹長高，置taller=*m=1*/ (*b)=(BSTNode*)malloc(sizeof(BST

15、Node); (*b)-key=e; (*b)-lchild=(*b)-rchild=NULL; (*b)-bf=0; *m=1; else if(e=(*b)-key) /*樹中已存在和e有相同關(guān)鍵字的結(jié)點，則不再進行插入*/ *m=0; /*置taller=*m=0,樹沒有長高，不須進行調(diào)整*/ printf(n The data is here!n); /*輸出提示信息*/ return 0; if(ekey) /*繼續(xù)在*b的左子樹中進行搜索*/ if(InsertAVL(&(*b)-lchild),e,&taller)=0) return 0; /*存在和e有相同關(guān)鍵字的元素，則不需

16、要插入*/ if(taller=1) /*已插入在*b的左子樹中且左子樹長高*/ LeftProcess(&(*b),&taller); else /*已插入在*b的右子樹中且左子樹長高*/ if(InsertAVL(&(*b)-rchild),e,&taller)=0) return 0; /*存在和e有相同關(guān)鍵字的元素則不需要插入*/ if(taller=1) /*已插入在*b的右子樹中且右子樹長高*/ RightProcess(&(*b),&taller); return 1; void LeftProcess(BSTree *p,int *m)/*對以指針p所指結(jié)點為根的二叉樹做左平衡

17、旋轉(zhuǎn)處理，算法結(jié)束后，指針 p指向新的根結(jié)點*/ BSTNode *p1,*p2; if(*p)-bf=0) /*原本左右子樹等高，現(xiàn)因左子樹增高而使樹增高*/ (*p)-bf=1; *m=1； else if(*p)-bf=-1) /*原本右子樹比左子樹高，現(xiàn)左右子樹等高*/ (*p)-bf=0; *m=0; /*樹沒有長高*/ else /*原本左子樹比右子樹高，需做左子樹的平衡處理*/ p1=(*p)-lchild; /*p1指向*p的左子樹根結(jié)點*/ if(p1-bf=1) /*新結(jié)點插入在*p的左孩子的右子樹上，要做LL調(diào)整*/ (*p)-lchild=p1-rchild; /*p的

18、左孩子為p1的右孩子*/ p1-rchild=(*p); /*p1的右孩子為p*/ (*p)-bf=p1-bf=0; /*p和p1的平衡因子都變?yōu)?*/ *p=p1; /*p1取代以前p的位置*/ else if(p1-bf=-1) /*如果新結(jié)點插在*b的左子樹根結(jié)點的右子樹上，需做LR調(diào)整*/ p2=p1-rchild; /*p2指向p1的右子樹根結(jié)點*/ p1-rchild=p2-lchild; /*p1的右孩子為p2的左孩子*/ p2-lchild=p1; /*p2的左孩子為p1*/ (*p)-lchild=p2-rchild; /*p的左孩子為p2的右孩子*/ p2-rchild=*

19、p; /*p2的右孩子為p*/ if(p2-bf=0) /*新結(jié)點插在p2處做葉子結(jié)點的情況*/ (*p)-bf=p1-bf=0; else if(p2-bf=1) /*新結(jié)點插在p2的左子樹上的情況*/ p1-bf=0; (*p)-bf=-1; else /*新結(jié)點插在p2的右子樹上的情況*/ p1-bf=1; (*p)-bf=0; *p=p2; (*p)-bf=0; /*仍將p指向新的根結(jié)點，并置其平衡因子為0*/ *m=0; /*返回值為*m=taller，在 InsertAVL（）遞歸調(diào)用時，依次判斷每個結(jié)點的平衡因子是否在（-1，1）之間*/ void RightProcess(BS

20、Tree *p,int *m) /*對以指針p所指結(jié)點為根的二叉樹做左平衡旋轉(zhuǎn)處理，算法結(jié)束后，指針 p指向新的根結(jié)點*/ BSTNode *p1,*p2; if(*p)-bf=0) /*原本左右子樹等高，現(xiàn)因右子樹增高而使樹增高*/ (*p)-bf=-1; *m=1; else if(*p)-bf=1) /*原本左子樹比右子樹高，現(xiàn)左右子樹等高*/ (*p)-bf=0; *m=0; else /*原本右子樹比左子樹高，需做右子樹的平衡處理*/ p1=(*p)-rchild; /*p1指向*p的右子樹根結(jié)點*/ if(p1-bf=-1) /*如果新結(jié)點插在*b的左子樹根結(jié)點的右子樹上，需做RR

21、調(diào)整*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; else if(p1-bf=1) /*新結(jié)點插入在*p的右孩子的左子樹上，要做RL調(diào)整*/ p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; (*p)-rchild=p2-lchild; p2-lchild=*p; if(p2-bf=0) /*新結(jié)點插在p2處做葉子結(jié)點的情況*/ (*p)-bf=p1-bf=0; else if(p2-bf=-1) /*新結(jié)點插在p2的右子樹上的情況*/ p1-bf=0; (*p)-

22、bf=1; else /*新結(jié)點插在p2的左子樹上的情況*/ p1-bf=-1; (*p)-bf=0; *p=p2; (*p)-bf=0; /*仍將p指向新的根結(jié)點，并置其平衡因子為0*/ *m=0; （2）以下是對刪除算法的設(shè)計和實現(xiàn)。假設(shè)要刪除關(guān)鍵字為x的結(jié)點，如果x 不在葉子結(jié)點上，則用它左子數(shù)中的最大值或最小值取代x；如此反復(fù)取代，直到刪除動作傳遞到某個葉子接點。刪除葉子結(jié)點時，若需要進行平衡變換，可采用插入的平衡變換的反變換（如：左子樹變矮對應(yīng)于右子樹長高）； int DeleteAVL(BSTree *p,KeyType x,int *m)/*在AVL樹中刪除關(guān)鍵字為 x的結(jié)點。*

23、/ int k; BSTNode *q; if(*p)=NULL) return 0; else if(xkey) k=DeleteAVL(&(*p)-lchild),x,&taller); if(taller=1) LeftProcess1(&(*p),&taller); return k; else if(x(*p)-key) k=DeleteAVL(&(*p)-rchild),x,&taller); if(taller=1) RightProcess1(&(*p),&taller); return k; else /*找到了關(guān)鍵字為x的結(jié)點，由p指向它。*/ q=(*p); if(*p)

24、-rchild=NULL) /*被刪結(jié)點右子樹為空。*/ (*p)=(*p)-lchild; free(q); *m=1; else if(*p)-lchild=NULL) /*被刪結(jié)點左子樹為空。*/ *p=(*p)-rchild; free(q); *m=1; else /*被刪結(jié)點左右子樹都不為空。*/ Delete2(q,&(q-lchild),&taller); if(taller=1) LeftProcess1(&q,&taller); (*p)=q; return 1; void LeftProcess1(BSTree *p,int *m)/*在刪除結(jié)點時進行左處理。*/BSTN

25、ode *p1,*p2; if(*p)-bf=1) (*p)-bf=0; /*需做RR調(diào)整。*/ *m=1; else if(*p)-bf=0) (*p)-bf=-1; *m=0; else p1=(*p)-rchild; if(p1-bf=0) (*p)-rchild=p1-lchild; p1-lchild=*p; p1-bf=1;(*p)-bf=-1; *p=p1; *m=0; else if(p1-bf=-1) /*需做RR調(diào)整。*/ (*p)-rchild=p1-lchild; p1-lchild=*p; (*p)-bf=p1-bf=0; *p=p1; *m=1; else /*需做

26、RL調(diào)整。*/ p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; (*p)-rchild=p2-lchild; p2-lchild=*p; if(p2-bf=0) (*p)-bf=0; p1-bf=0; else if(p2-bf=-1) (*p)-bf=1; p1-bf=0; else (*p)-bf=0; p1-bf=-1; p2-bf=0; *p=p2; *m=1; void RightProcess1(BSTree *p,int *m)/*在刪除結(jié)點時進行右處理。*/BSTNode *p1,*p2; if(*p)-bf=-1) (*p)-

27、bf=0; *m=-1; else if(*p)-bf=0) (*p)-bf=1; *m=0; else p1=(*p)-lchild; if(p1-bf=0) /*需做LL調(diào)整。*/ (*p)-lchild=p1-rchild; p1-rchild=*p; p1-bf=-1;(*p)-bf=1; *p=p1; *m=0; else if(p1-bf=1) /*需做LL調(diào)整。*/ (*p)-lchild=p1-rchild; p1-rchild=*p; (*p)-bf=p1-bf=0; (*p)=p1; *m=1; else p2=p1-rchild; p1-rchild=p2-lchild;

28、 p2-lchild=p1; (*p)-lchild=p2-rchild; p2-rchild=*p; if(p2-bf=0) (*p)-bf=0; p1-bf=0; else if(p2-bf=1) (*p)-bf=-1; p1-bf=0; else /*需做LR調(diào)整。*/ (*p)-bf=0; p1-bf=1; p2-bf=0; *p=p2; *m=1; void Delete2(BSTree q,BSTree *r,int *m)/*由DeleteAVL( )調(diào)用，用于處理被刪除結(jié)點左右子樹均不為空的情況。*/if(*r)-rchild=NULL) q-key=(*r)-key; q=*

29、r; *r=(*r)-lchild; free(q); *m=1; else Delete2(q,&(*r)-rchild),&taller); if(taller=1) RightProcess1(&(*r),&taller); （3）以下是對二叉樹輸出的設(shè)計，包括以括號的形式輸出和以圖形的形式輸出。void DispBSTree(BSTree b)/*以括號的形式輸出*/ if(b!=NULL) printf(%d,b-key); if(b-lchild!=NULL|b-rchild!=NULL) printf(); DispBSTree(b-lchild); if(b-rchild!=N

30、ULL) printf(,); DispBSTree(b-rchild); printf(); void OutputTree(BSTree b,int fx,int fy,int prex,int prey)/*以圖形的形式輸出*/ char str30; if(b) b-x=fx; b-y=fy; sprintf(str,%d,b-key); setcolor(RED); outtextxy(fx-2,fy-2,str); setcolor(YELLOW); circle(fx,fy,15); line(prex,prey,fx,fy); OutputTree(b-lchild,fx-50

31、,fy+50,fx,fy); OutputTree(b-rchild,fx+50,fy+50,fx,fy); 4、 以下是對主函數(shù)部分的設(shè)計。void main() BSTree b=NULL; int i,k,j,n; FILE *fp; int m50; for(;) /*用for()循環(huán)語句控制每次選擇*/ /*菜單*/ printf(n=Menu=n); printf(n 1: Load from the file;n); printf(n 2: Append new record;n); printf(n 3: Upate special record;n); printf(n 4:

32、 Delete special record;n); printf(n 5: Quit;n); printf(n=n); printf(n Please input your choose: j=(1-5)?nn j=); scanf(%d,&j); /*輸入選擇*/ switch(j) case 1: /*從文件中讀出數(shù)據(jù)*/ if(fp=fopen(c:TC20nana.txt,rb)=NULL) printf(n Cannot open file,strike any key exit!n); getch(); exit(0); printf(n Please input the datas number: n= ); scanf(%d,&n); /*輸入需要操作元素的范圍（即個數(shù)）*/ for(i=1;i=n;i+) fscanf(fp,%d,(m+i); printf(n You can chose data from this range:n); printf(n); for(i=1;ilchild中找刪除的合適位置，遞歸調(diào)用DeleteAVL( )函數(shù)后要寫上LefeProcess1( )函數(shù)的操作。3、在設(shè)計用圖形顯示出平衡二叉樹時，要在TC2.0的編譯器中運行程序，因為只有TC2.0支持畫圖的功能。