二叉排序樹與平衡二叉排序樹基本操作的實現(xiàn)

1、課程設計（論文）編 號： B04900083學 號： 201440410208 課 程 設 計教 學 院計算機學院課程名稱數(shù)據(jù)結(jié)構(gòu)與算法題 目二叉排序樹與平衡二叉排序樹基本操作的實現(xiàn)專 業(yè)計算機科學與技術班 級二班姓 名同組人員指導教師成俊2015年12月27日 課程設計任務書 2015 2016 學年 第 1 學期學生姓名： 專業(yè)班級： 計科二 指導教師： 成俊 工作部門： 計算機學院 一、課程設計題目: 二叉排序樹與平衡二叉排序樹基本操作二、課程設計內(nèi)容用二叉鏈表作存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)二叉排序樹上的基本操作：以回車('n')為輸入結(jié)束標志,輸入數(shù)列L,生成二叉排序樹T；對

2、二叉排序樹T作中序遍歷；計算二叉排序樹T的平均,輸出結(jié)果；輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷；否則輸出信息“無結(jié)點x”；判斷二叉排序樹T是否為平衡二叉樹；再用數(shù)列L,生成平衡二叉排序樹BT:當插入新元素之后,發(fā)現(xiàn)當前的二叉排序樹BT不是平衡二叉排序樹,則立即將它轉(zhuǎn)換成新的平衡二叉排序樹BT；計算平衡的二叉排序樹BT的平均查找長度，輸出結(jié)果。三、進度安排1分析問題，給出數(shù)學模型，選擇數(shù)據(jù)結(jié)構(gòu).2設計算法，給出算法描述3給出源程序清單4. 編輯、編譯、調(diào)試源程序5. 撰寫課程設計報告四、基本要求編寫AVL樹判別程序，并判別一個二叉排序樹是否為AVL樹。二叉排

3、序樹用其先序遍歷結(jié)果表示，如：5，2，1，3，7，8。實現(xiàn)AVL樹的ADT，包括其上的基本操作：結(jié)點的加入和刪除；另外包括將一般二叉排序樹轉(zhuǎn)變?yōu)锳VL樹的操作。實現(xiàn)提示主要考慮樹的旋轉(zhuǎn)操作。目錄一、課程設計題目: 二叉排序樹與平衡二叉排序樹基本操作1二、課程設計內(nèi)容1三、進度安排1四、基本要求1一、概述31.課程設計的目的32.課程設計的要求3二、總體方案設計4三、詳細設計61.課程設計總體思想62.模塊劃分73.流程圖8四、程序的調(diào)試與運行結(jié)果說明9五、課程設計總結(jié)14參考文獻14一、概述1.課程設計的目的1.充分理解和掌握二叉樹、平衡二叉樹的相關概念和知識。2.掌握排序二叉樹的生成、結(jié)點刪

4、除、插入等操作過程。3.并實現(xiàn)從鍵盤上輸入一系列數(shù)據(jù)（整型），建立一棵平衡二叉樹。4.任意插入或刪除一個結(jié)點后判斷是否為平衡二叉樹。5將非平衡二叉樹轉(zhuǎn)換成平衡二叉樹。6.按中序遍歷輸出這棵平衡二叉樹。2.課程設計的要求用二叉鏈表作存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)二叉排序樹上的基本操作：以回車('n')為輸入結(jié)束標志,輸入數(shù)列L,生成二叉排序樹T；對二叉排序樹T作中序遍歷；計算二叉排序樹T的平均查找長度,輸出結(jié)果；輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷；否則輸出信息“無結(jié)點x”；判斷二叉排序樹T是否為平衡二叉樹；再用數(shù)列L,生成平衡二叉排序樹BT:當插入

5、新元素之后,發(fā)現(xiàn)當前的二叉排序樹BT不是平衡二叉排序樹,則立即將它轉(zhuǎn)換成新的平衡二叉排序樹BT；計算平衡的二叉排序樹BT的平均查找長度，輸出結(jié)果。編寫AVL樹判別程序，并判別一個二叉排序樹是否為AVL樹。二叉排序樹用其先序遍歷結(jié)果表示，如：5，2，1，3，7，8。實現(xiàn)AVL樹的ADT，包括其上的基本操作：結(jié)點的加入和刪除；另外包括將一般二叉排序樹轉(zhuǎn)變?yōu)锳VL樹的操作。實現(xiàn)提示主要考慮樹的旋轉(zhuǎn)操作。二、總體方案設計1） 建立二叉排序樹，編寫二叉排序樹T作中序遍歷。2） 查找刪除二叉排序樹函數(shù)。3） 編寫判斷二叉排序樹T是否為平衡二叉樹函數(shù)，把非平衡二叉排序樹轉(zhuǎn)換成平衡二叉排序樹。4） 編寫計算二

6、叉樹BT的平均查找長度函數(shù)。我負責的是第一部分，二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1.若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；2.若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；3.它的左、右子樹也分別為二叉排序樹。以鏈表存儲結(jié)構(gòu)創(chuàng)建二叉排序樹，以回車('n')為輸入結(jié)束標志,輸入數(shù)列L,生成二叉排序樹T；對二叉排序樹T作中序遍歷。中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則(1)中序遍歷左子樹（L）；(2)訪問根結(jié)點（V）；(3)中序遍歷右子樹（R）。函數(shù)1：中序遍歷二叉樹中序遍歷二叉樹也采用遞歸函數(shù)的方式，

7、先訪問左子樹2i,然后訪問根結(jié)點i,最后訪問右子樹2i+1.先向左走到底再層層返回，直至所有的結(jié)點都被訪問完畢。（謝石林）函數(shù)2：平均查找長度計算二叉排序樹的平均查詢長度時，可采用類似中序遍歷的遞歸方式，用s記錄總查詢長度，j記錄每個結(jié)點的查詢長度，s值初值為0，采用累加的方式最總得到總查詢長度s，平均查詢長度等于s/i（i為樹中結(jié)點個數(shù)）。（吳進）函數(shù)3：查找刪除二叉排序樹函數(shù)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點,則刪該結(jié)點,并作中序遍歷(執(zhí)行函數(shù)1)；否則輸出信息“無x”。（張常勛）函數(shù)4：判斷二叉排序樹T是否為平衡二叉樹，若不是則用數(shù)列L，生成平衡排序二叉樹BT；最后調(diào)用函數(shù)6

8、 ，接著調(diào)用函數(shù)5.判斷二叉排序樹是否為平衡二叉樹的函數(shù)也是采用遞歸函數(shù)的方式，分別判定以樹中每個節(jié)點為根節(jié)點的子樹是否為平衡二叉樹。只要有一個子樹不為平衡二叉樹，則該樹便不是平衡二叉樹。函數(shù)5：在平衡二叉樹BT上插入新元素，若發(fā)現(xiàn)當前的二叉排序樹BT不是平衡二叉排序樹，則立即將它轉(zhuǎn) 換成新的平衡二叉排序樹BT。三、詳細設計1.課程設計總體思想1.生成二叉排序樹：建立二叉排序樹采用的是邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進行查找。查找是按照二叉排序樹的性質(zhì)進行的，通過比較要插入元素的關鍵字與當前結(jié)點關鍵字的大小來決定我們是遍歷當前結(jié)點的哪個子樹。如果小于當前結(jié)點關鍵字

9、，則遍歷它的左子樹；大于當前結(jié)點關鍵字，則遍歷它的右子樹；等于當前關鍵字，則此元素不插入原樹。我們按照這樣的規(guī)律，一直向下遍歷，知道它的子樹為空，則返回當前結(jié)點的上一個結(jié)點。然后利用插入函數(shù)將該元素插入原樹。2.中序遍歷：對二叉排序樹進行中序遍歷采用遞歸函數(shù)的方式。在根節(jié)點不為空的情況下，先訪問左子樹，在訪問根結(jié)點，最后訪問右子樹。3.平均查找長度：計算二叉排序樹的平均查找長度，仍采用類似中序遍歷的遞歸方式，用s記錄總查找長度，j記錄每個結(jié)點的查找長度，s置初值為0，采用累加的方式最終得到總查找長度s，平均查找長度就等于s/j（i為樹中結(jié)點的總個數(shù)）。4.刪除結(jié)點：刪除結(jié)點函數(shù)，采用邊查找變刪

10、除的方式。如果沒有查找到，則不對樹做任何的修改：如果查找到結(jié)點，則分四種情況分別進行討論：（1）該結(jié)點左右子樹均為空；（2）該結(jié)點僅左子樹為空；（3）該結(jié)點僅右子樹為空；（4）該結(jié)點左右子樹都不為空；5用數(shù)列L，生成平衡的二叉排序樹BT；當插入新元素之后，發(fā)現(xiàn)當前的二叉排序樹BT不是平衡二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡的二叉排序樹BT。我所負責的模塊函數(shù)定義如下 void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) /按中序遍歷詳細的程序代碼如下：typedef struct BSTNode /二叉排序樹類型 ElemTyp

11、e data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree; Status InitDSTable(BSTree &DT) /構(gòu)造一個空的動態(tài)BST查找表DT DT = NULL; return 1; void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) /按中序遍歷對DT的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次 if(DT) TraverseOrderDSTable (DT->lchild, Visit); Visit(DT->data); Tr

12、averseOrderDSTable (DT->rchild, Visit); 2.模塊劃分Main:主函數(shù)模塊，在主函數(shù)中調(diào)用其他函數(shù)：（1）Status InsertBST(BSTree &T, ElemType e) /創(chuàng)建二叉排序樹（2）void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) void TraverseOrderDSTable(AVLTree DT, void(*Visit)(ElemType) /中序遍歷二叉排序樹和平衡二叉排序樹 （3）void asl() /計算平均長度 （4）BSTre

13、e SearchBST(BSTree T, KeyType key) void SearchBST(BSTree &T, KeyType key, BSTree f, BSTree &p, Status &flag) void Delete(BSTree &p) Status DeleteBST(BSTree &T, KeyType key)/查找并刪除結(jié)點（5）Status InsertAVL(AVLTree &T, ElemType e, Status &taller) /創(chuàng)建平衡二叉排序樹 void RightBalance(AVL

14、Tree &T)/對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結(jié)點，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點 void LeftBalance(AVLTree &T) /對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結(jié)點，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點 AVLTree SearchAVL(AVLTree T, KeyType key)/衡二叉排序樹中進行查找。3.流程圖 四、程序的調(diào)試與運行結(jié)果說明主函數(shù)代碼：void main() int num, i, select, t, *depth, max, flag; KeyType j; Status k; El

15、emType *r, *tempr, tempbst, tempavl; BSTree bst, p; AVLTree avl, q; do printf("請輸入要輸入的數(shù)據(jù)的總數(shù)，總數(shù)要大于0:"); scanf("%d",&num); if(num <=0) printf("n輸入的總數(shù)要大于0，請重新輸入："); while(num <=0); gl_count = num; r = (ElemType*)malloc(gl_count*(sizeof(ElemType); printf("請輸入

16、生成二叉樹的整型數(shù)據(jù)，前后數(shù)據(jù)用空格隔開：n"); for(i=0; i<gl_count; i+) scanf("%d", &ri.key) ;ri.order = i+1; printf("n用戶輸入的數(shù)據(jù)及序號如下：n"); for(i=0; i< gl_count; i+)print(ri); if(i+1)%6 = 0) printf("n"); select = 0; flag = 0; InitDSTable(bst); for(i=0; i<gl_count; i+) InsertB

17、ST(bst, ri); printf("n按中序遍歷該二叉排序樹的結(jié)果如下：n"); TraverseOrderDSTable(bst, print); cout<<endl<<endl<<"以下是對二叉排序樹的基本操作:"<<endl <<"1.查找一個節(jié)點"<<endl <<"2.插入一個節(jié)點"<<endl <<"3.刪除一個節(jié)點"<<endl <<"

18、;4.判別二元查找樹是否為平衡二叉樹"<<endl <<"5.二叉樹轉(zhuǎn)換為平衡二叉樹"<<endl <<"6.退出系統(tǒng)"<<endl; do if(flag = 6); printf("n請輸入二叉排序樹基本操作的選項："); scanf("%d", &select); switch(select) case 1:printf("請輸入待查找的數(shù)據(jù)："); scanf("%d", &j);

19、p = SearchBST(bst, j); if(p) printf("n二叉排序樹中存在此值："); print(p->data); else printf("n二叉排序樹中不存在此值。"); break; case 2:printf("請輸入需插入的數(shù)據(jù)："); scanf("%d", &j); p = SearchBST(bst, j); if(p) printf("n二叉排序樹中存在此值："); print(p->data); elsetempr = (ElemTy

20、pe*)(malloc(gl_count*sizeof(ElemType); for(i=0; i < gl_count; i+) tempri.key = ri.key; tempri.order = ri.order; tempbst.key = j; tempbst.order = +gl_count; r = (ElemType*)(malloc(gl_count*sizeof(ElemType); for(i=0; i < gl_count-1; i+) ri.key = tempri.key; ri.order = tempri.order; ri.key = temp

21、bst.key; ri.order = tempbst.order; InsertBST(bst, tempbst); printf("數(shù)據(jù)已經(jīng)插入二叉排序樹中。"); printf("n按中序遍歷該二叉排序樹的結(jié)果如下：n"); TraverseOrderDSTable(bst, print); break; case 3: printf("請輸入需刪除的數(shù)據(jù)："); scanf("%d", &j); p = SearchBST(bst, j); if(p)tempr = (ElemType*)(mall

22、oc(gl_count*sizeof(ElemType); for(i=0; i < gl_count; i+) tempri.key = ri.key; tempri.order = ri.order; DeleteBST(bst, j); gl_count-; r = (ElemType*)(malloc(gl_count*sizeof(ElemType); for(i=0, t=0; i < gl_count; i+) if(tempri.key != j) rt.key = tempri.key; rt.order = tempri.order; t+; printf(&q

23、uot;二叉排序樹中該數(shù)據(jù)已經(jīng)刪除。"); TraverseOrderDSTable(bst, print); else printf("需刪除的數(shù)據(jù)不存在于二叉樹中。"); break; case 4: depth = (int*)malloc(gl_count*(sizeof(int); BST_DepthDiff(bst, depth); max = depth0; for(i=1 ; i<gl_count; i+) if(max < depthi) max = depthi; if(max < 2) printf("n該二叉排序

24、樹是平衡二叉樹。"); else printf("n該二叉排序樹不是平衡二叉樹。"); if(max > 4)printf("n該二叉排序樹有結(jié)點的左右子樹之差大于4，系統(tǒng)建議您將該二叉排序樹轉(zhuǎn)換成平衡二叉樹。"); break; case 5: InitDSTable(avl); for(i =0; i < gl_count; i+) InsertAVL(avl, ri, k); printf("該二叉排序樹轉(zhuǎn)換成了平衡二叉樹"); TraverseOrderDSTable(avl, print); flag = 6; break; case 6: break; default : printf("您輸入的選項是錯誤的，請重新輸入！"); break; while(select != 6); 初始提示輸入節(jié)點數(shù)；輸入數(shù)據(jù)用空格符隔開；隨后系統(tǒng)會自動對數(shù)據(jù)