廣工數(shù)據(jù)結(jié)構(gòu)實驗報告--平衡二叉樹

1、實驗報告課程名稱 數(shù)據(jù)結(jié)構(gòu)實驗 學(xué) 院 計算機(jī)學(xué)院 專業(yè)班級 計科9班 學(xué) 號 學(xué)生姓名 指導(dǎo)教師 蘇慶 2015 年 7 月 6 日1. 題目:平衡二叉樹 ADT BBSTree 數(shù)據(jù)對象：D ai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 <ai-1, ai>|ai-1, aiD, i=2,.,n 基本操作：BBSTree MakeBBSTree( )操作結(jié)果：創(chuàng)建好一棵樹返回：將創(chuàng)建好的樹返回Status InsertAVL(BBSTree &T, RcdType e, Status &taller)初始條件：樹T已存在，e存在，t

2、aller為真操作結(jié)果：將e插入到T中返回：成功TRUE，失敗FALSEStatus DeleteAVL(BBSTree &t, RcdType e, Status &shorter) 初始條件：樹T已存在，e存在，shorter為真操作結(jié)果：將e從T中刪除返回：成功TRUE，失敗FALSEBBSTree SearchAVL(BBSTree T, RcdType e)初始條件：樹T已存在，e存在操作結(jié)果：從T中找到e返回：以e為根節(jié)點的樹void L_Rotate(BBSTree &p)初始條件：樹p存在操作結(jié)果：對p左旋操作void R_Rotate(BBSTree

3、&p)初始條件：樹p存在操作結(jié)果：對p右旋操作void LeftBalance(BBSTree &T)初始條件：樹T存在操作結(jié)果：對T左平衡操作void RightBalance(BBSTree &T)初始條件：樹T存在操作結(jié)果：對T右平衡操作void ExchangeSubTree(BBSTree &T)初始條件：樹T存在操作結(jié)果：對T所有左右孩子交換int BBSTreeDepth(BBSTree T)初始條件：樹T已存在操作結(jié)果：求樹T的深度返回：樹的深度BBSTree Combine2Tree(BBSTree T1, BBSTree T2)初始條件：樹T

4、1和T2已存在操作結(jié)果：將T1和T2合并返回：合并后的樹Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x)初始條件：樹Tt1，Tt2，Tt3已存在，x存在操作結(jié)果：將Tt1分裂成Tt2和Tt3返回：以e為根節(jié)點的樹Status PreOrder_RecTraverse(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行遞歸先序遍歷輸出返回：成功TRUE 失敗FALSEStatus InOrder_RecTraverse(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行遞歸中

5、序遍歷輸出返回：成功TRUE 失敗FALSEStatus LastOrder_RecTraverse(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行遞歸后序遍歷輸出返回：成功TRUE 失敗FALSEvoid PreOrderTravese_I(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行非遞歸先序遍歷輸出void InOrderTraverse_I(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行非遞歸中序遍歷輸出void LastOrderTravese_I(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行非遞歸后序遍歷輸出void Le

6、velOrederTraverse_Print(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T進(jìn)行非遞歸層次遍歷輸出void BraNotationPrint(BBSTree T)初始條件：樹T已存在操作結(jié)果：對樹T用括號表示法輸出ADT BBSTree2. 存儲結(jié)構(gòu)定義#include<stdio.h>#include<malloc.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 /左高 #define EH 0 /等高 #d

7、efine RH -1 /右高 typedef int RcdType;typedef int Status;/*平衡二叉樹結(jié)構(gòu)體*/typedef struct BBSTNode RcdType data; int bf; BBSTNode *lchild, *rchild;BBSTNode,*BBSTree;3. 算法設(shè)計/*求平衡二叉樹的深度*/int BBSTreeDepth(BBSTree T) int depthLeft, depthRight; if(NULL=T) return 0; else depthLeft = BBSTreeDepth(T->lchild); de

8、pthRight = BBSTreeDepth(T->rchild); return 1+(depthLeft > depthRight ? depthLeft : depthRight); /*交換二叉樹所有結(jié)點的左右子樹*/void ExchangeSubTree(BBSTree &T) BBSTree temp; if(NULL!=T) ExchangeSubTree(T->lchild); /使用遞歸交換左子樹 ExchangeSubTree(T->rchild); /使用遞歸交換右子樹 if(T->lchild!=NULL)|(T->rch

9、ild!=NULL) /如果T的子樹有一個不 為空，則交換左右子樹 temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; /*左旋調(diào)整*/void L_Rotate(BBSTree &p) BBSTree rc = p->rchild; p->rchild = rc->lchild; rc->lchild = p; p = rc;/*右旋調(diào)整*/void R_Rotate(BBSTree &p) BBSTree lc = p->lchild; p->lch

10、ild = lc->rchild; lc->rchild = p; p = lc;/*左平衡處理操作*/void LeftBalance(BBSTree &T) BBSTree lc, rd; lc = T->lchild; switch(lc->bf) 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 E

11、H: 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); break; /*右平衡處理操作*/void RightBalance(BBSTree &T) BBSTree rd,lc; rd=T->rchild; switch(rd->bf) case RH: T->bf=rd->bf=EH; L_Rotate(T); break; case LH:

12、lc=rd->lchild; switch(lc->bf) case RH:T->bf=LH;rd->bf=EH;break; case EH:T->bf=rd->bf=EH;break; case LH:T->bf=EH;rd->bf=RH;break; lc->bf=EH; R_Rotate(T->rchild); L_Rotate(T); break; /*平衡二叉樹的插入操作*/Status InsertAVL(BBSTree &T, RcdType e, Status &taller) if(NULL=T)

13、T = (BBSTree)malloc(sizeof(BBSTNode); T->data = e; T->bf = EH; T->lchild = NULL; T->rchild = NULL; else if(e=T->data) /書中已存在和e相等的結(jié)點 taller = FALSE; return FALSE; else if(e<T->data) if(FALSE=InsertAVL(T->lchild, e, taller) return FALSE; if(TRUE=taller) switch(T->bf) case LH

14、: LeftBalance(T); taller = FALSE; break; case EH: T->bf = LH; taller = TRUE; break; case RH: T->bf = EH; taller = FALSE; break; else if(FALSE=InsertAVL(T->rchild, e, taller) return FALSE; if(TRUE=taller) switch(T->bf) case LH: T->bf = EH; taller = FALSE; break; case EH: T->bf = RH;

15、 taller = TRUE; break; case RH: RightBalance(T); taller = FALSE; break; return TRUE;/*平衡二叉樹的刪除操作*/Status DeleteAVL(BBSTree &t, RcdType e, Status &shorter) /當(dāng)被刪結(jié)點是有兩個孩子，且其前驅(qū)結(jié)點是左孩子時，tag=1 static int tag = 0; if(t = NULL) return FALSE; /如果不存在元素，返回失敗 else if(e=t->data) BBSTNode *q = NULL; /如果

16、該結(jié)點只有一個孩子，則將自子樹取代該結(jié)點 if(t->lchild = NULL) q = t; t = t->rchild; free(q); shorter = TRUE; else if(t->rchild = NULL) q = t; t = t->lchild; free(q); shorter = TRUE; /如果被刪結(jié)點有兩個孩子，則找到結(jié)點的前驅(qū)結(jié)點， /并將前驅(qū)結(jié)點的值賦給該結(jié)點，然后刪除前驅(qū)結(jié)點 else q = t->lchild; while(q->rchild) q = q->rchild; t->data = q-&

17、gt;data; if(t->lchild->data=q->data) tag = 1; DeleteAVL(t->lchild, q->data, shorter); if(tag=1) BBSTree r = t->rchild; if(NULL=r) t->bf = 0; else switch(r->bf) case EH: t->bf=-1;break; default: RightBalance(t);break; else if(e<t->data) /左子樹中繼續(xù)查找 if(!DeleteAVL(t->l

18、child, e, shorter) return FALSE; /刪除完結(jié)點之后，調(diào)整結(jié)點的平衡因子 if(shorter&&(tag=0) switch(t->bf) case LH: t->bf = EH; shorter = TRUE; break; case EH: t->bf = RH; shorter = FALSE; break; /如果本來就是右子樹較高，刪除之后就不平衡，需要做右平 衡操作 case RH: RightBalance(t); /右平衡處理 if(t->rchild->bf = EH) shorter = FALS

19、E; else shorter = TRUE; break; else if(e>t->data) /右子樹中繼續(xù)查找 if(!DeleteAVL(t->rchild, e, shorter) return FALSE; /刪除完結(jié)點之后，調(diào)整結(jié)點的平衡因子 if(shorter&&(tag=0) switch(t->bf) case LH: LeftBalance(t); /左平衡處理 if(t->lchild->bf = EH)/注意這里，畫圖思考一下 shorter = FALSE; else shorter = TRUE; break

20、; case EH: t->bf = LH; shorter = FALSE; break; case RH: t->bf = EH; shorter = TRUE; break; if(tag=1) int depthLeft = BBSTreeDepth(t->lchild); int depthRight = BBSTreeDepth(t->rchild); t->bf = depthLeft - depthRight; return TRUE; /*平衡二叉樹的查找操作*/BBSTree SearchAVL(BBSTree T, RcdType e) if

21、(T=NULL) return NULL; if(e=T->data) return T; else if(e>T->data) return SearchAVL(T->rchild, e); else return SearchAVL(T->lchild, e); /*獲取輸入存到數(shù)組a*/Array GetInputToArray() Array head, p, q; char k; head = p = q = NULL; int m; if(k!='n') scanf("%d",&m); p = (ArrayN

22、ode*)malloc(sizeof(ArrayNode); head = p; p->data = m; k = getchar(); while(k!='n') scanf("%d",&m); q = (ArrayNode*)malloc(sizeof(ArrayNode); q->data = m; p->next = q; p = p->next; k = getchar(); if(p!=NULL) p->next = NULL; return head; /返回存放數(shù)據(jù)的頭指針 /*根據(jù)輸入的字符串建一棵平衡

23、二叉樹*/BBSTree MakeBBSTree( ) int i=0; Status taller = TRUE; BBSTree T = NULL; Array a; a = GetInputToArray(); while(a!=NULL) taller = TRUE; InsertAVL(T, a->data, taller); a = a->next; return T;/*遞歸先序遍歷*/Status PreOrder_RecTraverse(BBSTree T) if(NULL=T) return OK; printf("%d ",T->da

24、ta); PreOrder_RecTraverse(T->lchild); PreOrder_RecTraverse(T->rchild);/*遞歸中序遍歷*/Status InOrder_RecTraverse(BBSTree T) if(T->lchild) InOrder_RecTraverse(T->lchild); printf("%d ",T->data); if(T->rchild) InOrder_RecTraverse(T->rchild);/*遞歸后序遍歷*/Status LastOrder_RecTravers

25、e(BBSTree T) if(T->lchild) LastOrder_RecTraverse(T->lchild); if(T->rchild) LastOrder_RecTraverse(T->rchild); printf("%d ",T->data);/*找到最左結(jié)點*/BBSTree GoFarLeft(BBSTree T, LStack &S) if(NULL=T) return NULL; while(T->lchild!=NULL) Push_LS(S, T); T = T->lchild; return

26、T;/*非遞歸中序遍歷*/void InOrderTraverse_I(BBSTree T) LStack S; InitStack_LS(S); BBSTree p = NULL; p = GoFarLeft(T, S); while(p!=NULL) printf("%d ",p->data); if(p->rchild!=NULL) p = GoFarLeft(p->rchild, S); else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p); else p = NULL; BBSTree VisitFarLeft

27、(BBSTree T, LStack &S) if(NULL=T) return NULL; /如果T為空，則返回空 printf("%d ",T->data); /先序，先讀取結(jié)點數(shù)據(jù) while(T->lchild!=NULL) Push_LS(S, T); /入棧 T = T->lchild; /遍歷下一個左子樹 printf("%d ", T->data); /下一個結(jié)點的讀取數(shù)據(jù) return T;/*非遞歸先序遍歷*/void PreOrderTravese_I(BBSTree T) LStack S; Ini

28、tStack_LS(S); BBSTree p; p = VisitFarLeft(T, S); /先將左邊的數(shù)據(jù)先序讀取 while(p!=NULL) if(p->rchild!=NULL) /如果最左下結(jié)點的右子樹不為空 p = VisitFarLeft(p->rchild, S); /執(zhí)行遍歷該結(jié)點的左子樹 else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p); /如果S不為空棧，出棧 else p = NULL; /如果為空棧，p賦予空 /*非遞歸后序遍歷*/void LastOrderTravese_I(BBSTree root) BBS

29、Tree p = root; BBSTree stack30; int num=0; BBSTree have_visited = NULL; while(NULL!=p|num>0) while(NULL!=p) stacknum+=p; p=p->lchild; p=stacknum-1; if(NULL=p->rchild|have_visited=p->rchild) printf("%d ",p->data); num-; have_visited=p; p=NULL; else p=p->rchild; printf(&quo

30、t;n");/*非遞歸層次遍歷輸出一棵二叉樹*/void LevelOrederTraverse_Print(BBSTree T) if(T=NULL) printf("The tree is empty!"); if(T!=NULL) LQueue Q; InitQueue_LQ(Q); BBSTree p = T; printf("%d ",p->data); EnQueue_LQ(Q,p); while(DeQueue_LQ(Q,p) if(p->lchild!=NULL) printf("%d ", p-

31、>lchild->data); EnQueue_LQ(Q, p->lchild); if(p->rchild!=NULL) printf("%d ", p->rchild->data); EnQueue_LQ(Q, p->rchild); /*括號表示法輸出平衡二叉樹*/void BraNotationPrint(BBSTree T) if(NULL=T) printf(" 空!"); else if(T!=NULL) if(T!=NULL) printf("%i",T->data);

32、if(T->lchild|T->rchild) printf("("); if(T->lchild|T->rchild) if(T->lchild) BraNotationPrint(T->lchild); else if(T->rchild) printf("#"); printf(","); if(T->rchild) BraNotationPrint(T->rchild); else if(T->lchild) printf("#"); printf

33、(")"); /*將一棵樹轉(zhuǎn)換為一個數(shù)組*/Array GetArrayFromTree(BBSTree T) Status firstTime = TRUE; Array head = NULL; ArrayNode *b = NULL; ArrayNode *q = NULL; if(T=NULL) printf("The tree is empty!"); if(T!=NULL) LQueue Q; InitQueue_LQ(Q); BBSTree p = T; q = (Array)malloc(sizeof(ArrayNode); q->

34、data = p->data; if(firstTime=TRUE) head = q; firstTime = FALSE; b = q; else b->next = q; b = b->next; EnQueue_LQ(Q,p); while(DeQueue_LQ(Q,p) if(p->lchild!=NULL) q = (Array)malloc(sizeof(ArrayNode); q->data = p->lchild->data; b->next = q; b = b->next; EnQueue_LQ(Q, p->lc

35、hild); if(p->rchild!=NULL) q = (Array)malloc(sizeof(ArrayNode); q->data = p->rchild->data; b->next = q; b = b->next; EnQueue_LQ(Q, p->rchild); if(b!=NULL) b->next = NULL; return head;/*將兩棵平衡二叉樹合并成一顆平衡二叉樹*/BBSTree Combine2Tree(BBSTree T1, BBSTree T2) Status taller = TRUE; Arra

36、y a = NULL; a = GetArrayFromTree(T2); while(a!=NULL) taller = TRUE; InsertAVL(T1, a->data, taller); a = a->next; return T1; /*將一棵平衡二叉樹分裂成兩棵平衡二叉樹*/*參數(shù)1：要進(jìn)行分裂的樹參數(shù)2：分裂出來的小于等于x的子樹參數(shù)3：分裂出來的 大于x的子樹 參數(shù)4：關(guān)鍵字x */Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x) Array a = NULL;

37、 Status taller; a = GetArrayFromTree(Tt1); if(Tt1=NULL) return FALSE; else while(a!=NULL) if(a->data<=x) taller = TRUE; InsertAVL(Tt2, a->data, taller); a = a->next; else taller = TRUE; InsertAVL(Tt3, a->data, taller); a = a->next; return TRUE;4. 測試(1) 建樹操作測試代碼: 測試數(shù)據(jù)：1 2 3 4 5 6測試結(jié)

38、果： (2) 插入操作測試代碼：測試數(shù)據(jù)：1 2 3 4 5 6 插入8測試結(jié)果：測試數(shù)據(jù)：1 2 3 4 5 6 插入4測試結(jié)果：(3) 刪除操作測試代碼：測試數(shù)據(jù)：1 2 3 4 5 6 刪除6測試結(jié)果：測試數(shù)據(jù)：1 2 3 4 5 6 刪除2測試結(jié)果：測試數(shù)據(jù)：1 2 3 4 5 6 刪除4測試結(jié)果：(4) 查找操作測試代碼：測試數(shù)據(jù)：1 2 3 4 5 6 查找5測試結(jié)果：(5) 輸出測試代碼：測試數(shù)據(jù)：1 2 3 4 5 6 測試結(jié)果：5. 思考與小結(jié)在完成平衡二叉樹實驗的過程中，所遇到的最大問題就是如何實現(xiàn)平衡二叉樹刪除結(jié)點的接口，因為課本沒有涉及到這個知識點，所以自己只能通過閱讀

39、其他書籍和通過參考網(wǎng)上的資料來對這個過程有了進(jìn)一步的理解。其次自己想了一個樹的括號表示法來將一棵樹打印出來，這對于一棵樹的表示是挺有用的?？偟膩碚f，平衡二叉樹這個知識點涉及到的算法大概就是添加結(jié)點，刪除結(jié)點，查找結(jié)點這三個方面，而其他的接口都是以這三個為基礎(chǔ)，實現(xiàn)進(jìn)一步的拓展。6. 源代碼 /* (1)根據(jù)輸入字符串創(chuàng)建一棵平衡二叉樹 BBSTree MakeBBSTree(); (2)平衡二叉樹插入元素操作 Status InsertAVL(BBSTree &T, RcdType e, Status &taller); (3)層次遍歷輸出二叉樹 void LevelOrede

40、rTraverse_Print(BBSTree T); (4)括號表示法輸出二叉樹 void BraNotationPrint(BBSTree T); (5)平衡二叉樹刪除元素操作 Status DeleteAVL(BBSTree &t, RcdType e, Status &shorter); (6)求平衡二叉樹的深度 int BBSTreeDepth(BBSTree T); (7)交換所有結(jié)點的左右子樹 void ExchangeSubTree(BBSTree &T) (8)遞歸先序遍歷 Status PreOrder_RecTraverse(BBSTree T)；

41、 (9)遞歸中序遍歷 Status InOrder_RecTraverse(BBSTree T);(10)遞歸后序遍歷 Status LastOrder_RecTraverse(BBSTree T);(11)非遞歸先序遍歷 void PreOrderTraverse_I(BBSTree T);(12)非遞歸中序遍歷 void InOrderTraverse_I(BBSTree T);(13)非遞歸后序遍歷 void LastOrderTraverse_I(BBSTree T); */#include<stdio.h>#include<malloc.h>#define O

42、VERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 /左高 #define EH 0 /等高 #define RH -1 /右高 typedef int RcdType;typedef int Status;/*存放輸入數(shù)據(jù)的數(shù)組結(jié)構(gòu)體*/typedef struct ArrayNode RcdType data; ArrayNode *next; ArrayNode, *Array;/*平衡二叉樹結(jié)構(gòu)體*/typedef struct BBSTNode RcdType data; in

43、t bf; BBSTNode *lchild, *rchild;BBSTNode,*BBSTree;/*鏈隊列結(jié)構(gòu)體*/typedef struct LQNode BBSTree elem; struct LQNode *next;LQNode, *QueuePtr;/*隊列結(jié)點結(jié)構(gòu)體*/typedef struct QueuePtr front; QueuePtr rear;LQueue;/*棧結(jié)點結(jié)構(gòu)體*/typedef struct LSNode BBSTree data; /數(shù)據(jù)域 struct LSNode *next; /指針域 LSNode, *LStack; /結(jié)點和鏈棧類型/*初始化一個鏈棧*/Status InitStack_LS(LStack &S)