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

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

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

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

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

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

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

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

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

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

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

11、e data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree; Status InitDSTable(BSTree &DT) /構(gòu)造一個(gè)空的動(dòng)態(tài)BST查找表DT DT = NULL; return 1; void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) /按中序遍歷對(duì)DT的每個(gè)結(jié)點(diǎn)調(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() /計(jì)算平均長度 （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é)點(diǎn)（5）Status InsertAVL(AVLTree &T, ElemType e, Status &taller) /創(chuàng)建平衡二叉排序樹 void RightBalance(AVL

14、Tree &T)/對(duì)以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點(diǎn) void LeftBalance(AVLTree &T) /對(duì)以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點(diǎn) AVLTree SearchAVL(AVLTree T, KeyType key)/衡二叉排序樹中進(jìn)行查找。3.流程圖 四、程序的調(diào)試與運(yùn)行結(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("請(qǐng)輸入要輸入的數(shù)據(jù)的總數(shù)，總數(shù)要大于0:"); scanf("%d",&num); if(num <=0) printf("n輸入的總數(shù)要大于0，請(qǐng)重新輸入："); while(num <=0); gl_count = num; r = (ElemType*)malloc(gl_count*(sizeof(ElemType); printf("請(qǐng)輸入

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ù)及序號(hào)如下：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<<"以下是對(duì)二叉排序樹的基本操作:"<<endl <<"1.查找一個(gè)節(jié)點(diǎn)"<<endl <<"2.插入一個(gè)節(jié)點(diǎn)"<<endl <<"3.刪除一個(gè)節(jié)點(diǎn)"<<endl <<"

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

19、p = SearchBST(bst, j); if(p) printf("n二叉排序樹中存在此值："); print(p->data); else printf("n二叉排序樹中不存在此值。"); break; case 2:printf("請(qǐng)輸入需插入的數(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("請(qǐng)輸入需刪除的數(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é)點(diǎn)的左右子樹之差大于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("您輸入的選項(xiàng)是錯(cuò)誤的，請(qǐng)重新輸入！"); break; while(select != 6); 初始提示輸入節(jié)點(diǎn)數(shù)；輸入數(shù)據(jù)用空格符隔開；隨后系統(tǒng)會(huì)自動(dòng)對(duì)數(shù)據(jù)