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

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

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

3、要求編寫(xiě)AVL樹(shù)判別程序，并判別一個(gè)二叉排序樹(shù)是否為 AVL樹(shù)。二叉排序樹(shù) 用其先序遍歷結(jié)果表示，如：5, 2, 1, 3, 7, 8。實(shí)現(xiàn)AVL樹(shù)的ADT包括其上的基本操作：結(jié)點(diǎn)的加入和刪除；另外包括 將一般二叉排序樹(shù)轉(zhuǎn)變?yōu)锳VL樹(shù)的操作。實(shí)現(xiàn)提示主要考慮樹(shù)的旋轉(zhuǎn)操作。目錄一、課程設(shè)計(jì)題目：二叉排序樹(shù)與平衡二叉排序樹(shù)基本操作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é)果說(shuō)明 9五、課程設(shè)計(jì)總結(jié) 14參考文獻(xiàn)

4、 14、概述1.課程設(shè)計(jì)的目的1 .充分理解和掌握二叉樹(shù)、平衡二叉樹(shù)的相關(guān)概念和知識(shí)。2 .掌握排序二叉樹(shù)的生成、結(jié)點(diǎn)刪除、插入等操作過(guò)程。3 .并實(shí)現(xiàn)從鍵盤(pán)上輸入一系列數(shù)據(jù)（整型），建立一棵平衡二叉樹(shù)。4 .任意插入或刪除一個(gè)結(jié)點(diǎn)后判斷是否為平衡二叉樹(shù)。5 .將非平衡二叉樹(shù)轉(zhuǎn)換成平衡二叉樹(shù)。6 .按中序遍歷輸出這棵平衡二叉樹(shù)。7 .課程設(shè)計(jì)的要求用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序?qū)崿F(xiàn)二叉排序樹(shù)上的基本操作：以回車(chē)（'n'）為輸入結(jié)束標(biāo)志，輸入數(shù)列L,生成二叉排序樹(shù)T;對(duì)二叉排序樹(shù)T作中序遍 歷;計(jì)算二叉排序樹(shù)T的平均查找長(zhǎng)度，輸出結(jié)果；輸入元素x,查找二叉排序樹(shù) T,若存在含x的

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

6、，編寫(xiě)二叉排序樹(shù) T作中序遍歷。2）查找刪除二叉排序樹(shù)函數(shù)。3）編寫(xiě)判斷二叉排序樹(shù)T是否為平衡二叉樹(shù)函數(shù)，把非平衡二叉排序樹(shù)轉(zhuǎn) 換成平衡二叉排序樹(shù)。4）編寫(xiě)計(jì)算二叉樹(shù)BT的平均查找長(zhǎng)度函數(shù)。我負(fù)責(zé)的是第一部分，二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二 叉樹(shù)：1 .若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；2 .若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；3 .它的左、右子樹(shù)也分別為二叉排序樹(shù)。以鏈表存儲(chǔ)結(jié)構(gòu)創(chuàng)建二叉排序樹(shù)，以回車(chē)（'n'）為輸入結(jié)束標(biāo)志，輸入數(shù)列L, 生成二叉排序樹(shù)T;對(duì)二叉排序樹(shù)T作中序遍歷。中序遍歷二叉樹(shù)算法的框

7、架是：若二叉樹(shù)為空，則空操作；否則（1）中序遍歷左子樹(shù)（L）;訪問(wèn)根結(jié)點(diǎn)（V）;（3）中序遍歷右子樹(shù)（R）。函數(shù)1:中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)也采用遞歸函數(shù)的方式，先訪問(wèn)左子樹(shù)2i,然后訪問(wèn)根結(jié)點(diǎn)i,最后訪問(wèn)右子樹(shù)2i+1.先向左走到底再層層返回，直至所有的結(jié)點(diǎn)都被訪問(wèn)完 畢。（謝石林）函數(shù)2:平均查找長(zhǎng)度計(jì)算二叉排序樹(shù)的平均查詢(xún)長(zhǎng)度時(shí)，可采用類(lèi)似中序遍歷的遞歸方式，用 s記 錄總查詢(xún)長(zhǎng)度，j記錄每個(gè)結(jié)點(diǎn)的查詢(xún)長(zhǎng)度，s值初值為0,采用累加的方式最 總得到總查詢(xún)長(zhǎng)度s,平均查詢(xún)長(zhǎng)度等于s/i （i為樹(shù)中結(jié)點(diǎn)個(gè)數(shù)）。（吳進(jìn)）函數(shù)3:查找刪除二叉排序樹(shù)函數(shù)輸入元素x,查找二叉排序樹(shù)T,若存在含x的

8、結(jié)點(diǎn)，則刪該結(jié)點(diǎn)，并作中序遍歷 （執(zhí)行函數(shù)1）;否則輸出信息“無(wú)x”。（張常勛）函數(shù)4:判斷二叉排序樹(shù)T是否為平衡二叉樹(shù)，若不是則用數(shù)列 L, 生成平衡排序二叉樹(shù)BT;最后調(diào)用函數(shù)6 ,接著調(diào)用函數(shù)5.判斷二叉排序樹(shù) 是否為平衡二叉樹(shù)的函數(shù)也是采用遞歸函數(shù)的方式，分別判定以樹(shù)中每個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)是否為平衡二叉樹(shù)。只要有一個(gè)子樹(shù)不為平衡二叉樹(shù)，則該樹(shù) 便不是平衡二叉樹(shù)。函數(shù)5:在平衡二叉樹(shù)BT上插入新元素，若發(fā)現(xiàn)當(dāng)前的二叉排序樹(shù) BT不是平 衡二叉排序樹(shù)，則立即將它轉(zhuǎn)換成新的平衡二叉排序樹(shù)BT。4兩I "4N察他課程設(shè)計(jì)(論文)三、詳細(xì)設(shè)計(jì)1.課程設(shè)計(jì)總體思想1 .生成二叉排序樹(shù)：

9、建立二叉排序樹(shù)采用的是邊查找邊插入的方式。查找函數(shù)采用遞歸的方式 進(jìn)行查找。查找是按照二叉排序樹(shù)的性質(zhì)進(jìn)行的，通過(guò)比較要插入元素的關(guān)鍵 字與當(dāng)前結(jié)點(diǎn)關(guān)鍵字的大小來(lái)決定我們是遍歷當(dāng)前結(jié)點(diǎn)的哪個(gè)子樹(shù)。如果小于 當(dāng)前結(jié)點(diǎn)關(guān)鍵字，則遍歷它的左子樹(shù)；大于當(dāng)前結(jié)點(diǎn)關(guān)鍵字，則遍歷它的右子 樹(shù)；等于當(dāng)前關(guān)鍵字，則此元素不插入原樹(shù)。我們按照這樣的規(guī)律，一直向下 遍歷，知道它的子樹(shù)為空，則返回當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)。然后利用插入函數(shù) 將該元素插入原樹(shù)。2 .中序遍歷：對(duì)二叉排序樹(shù)進(jìn)行中序遍歷采用遞歸函數(shù)的方式。在根節(jié)點(diǎn)不為空的情況 下，先訪問(wèn)左子樹(shù)，在訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。3 .平均查找長(zhǎng)度：計(jì)算二叉排序樹(shù)的

10、平均查找長(zhǎng)度，仍采用類(lèi)似中序遍歷的遞歸方式，用 s 記錄總查找長(zhǎng)度，j記錄每個(gè)結(jié)點(diǎn)的查找長(zhǎng)度，s置初值為0,采用累加的方式 最終得到總查找長(zhǎng)度s,平均查找長(zhǎng)度就等于s/j (i為樹(shù)中結(jié)點(diǎn)的總個(gè)數(shù))。4 .刪除結(jié)點(diǎn)：刪除結(jié)點(diǎn)函數(shù)，采用邊查找變刪除的方式。如果沒(méi)有查找到，則不對(duì)樹(shù)做 任何的修改：如果查找到結(jié)點(diǎn)，則分四種情況分別進(jìn)行討論：(1)該結(jié)點(diǎn)左右子樹(shù)均為空；(2)該結(jié)點(diǎn)僅左子樹(shù)為空；(3)該結(jié)點(diǎn)僅右子樹(shù)為空；(4)該結(jié)點(diǎn)左右子樹(shù)都不為空；5.用數(shù)列L,生成平衡的二叉排序樹(shù)BT;當(dāng)插入新元素之后，發(fā)現(xiàn)當(dāng)前的二叉 排序樹(shù)BT不是平衡二叉排序樹(shù)，則立即將它轉(zhuǎn)換成新的平衡的二叉排序樹(shù) BT。 我所負(fù)

11、責(zé)的模塊函數(shù)定義如下void TraverseOrderDSTable(BSTree DT, void(*Visit)(ElemType) 按中序 遍歷詳細(xì)的程序代碼如下：typedef struct BSTNode /二叉排序樹(shù)類(lèi)型 ElemType data;struct BSTNode *lchild, *rchild;BSTNode, *BSTree;Status InitDSTable(BSTree &DT)構(gòu)造一個(gè)空的動(dòng)態(tài) BST查找表DTDT = NULL;return 1;void TraverseOrderDSTable(BSTree DT, void(*Visit)

12、(ElemType)按中序遍歷對(duì)DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit() 一次且至多一次if(DT) TraverseOrderDSTable (DT->lchild, Visit);Visit(DT->data);TraverseOrderDSTable (DT->rchild, Visit);2 .模塊劃分Main:主函數(shù)模塊，在主函數(shù)中調(diào)用其他函數(shù)：(1) Status InsertBST(BSTree &T, ElemType e) /創(chuàng)建二叉排序樹(shù)(2) void TraverseOrderDSTable(BSTree DT, void(*Visit)(Ele

13、mType) void TraverseOrderDSTable(AVLTree DT, void(*Visit)(ElemType) /中序遍歷二叉排序樹(shù)和平衡二叉排序樹(shù)(3) void asl() /計(jì)算平均長(zhǎng)度(4) BSTree 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, KeyTyp

14、e key)/查找并刪除結(jié)點(diǎn)(5) Status InsertAVL(AVLTree &T, ElemType e, Status &taller) /創(chuàng)建平衡二叉排序樹(shù)void RightBalance(AVLTree &T)/對(duì)以*p為根的二叉排序樹(shù)作右旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的左子樹(shù)的根結(jié)點(diǎn)void LeftBalance(AVLTree &T) /對(duì)以*p為根的二叉排序樹(shù)作左旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的右子樹(shù)的根結(jié)點(diǎn)6vtfl /理工學(xué)茂課程設(shè)計(jì)（論文）衡二叉排序樹(shù)中進(jìn)行查AVLTree SearchAV

15、L(AVLTree T, KeyType key)/找。3 .流程圖四、程序的調(diào)試與運(yùn)行結(jié)果說(shuō)明主函數(shù)代碼：void main()int num, i, select, t, *depth, max, flag;KeyType j; Status k;ElemType *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ù)要大

16、于0,請(qǐng)重新輸入：”)；while(num <=0);gl_count = num;r = (ElemType*)malloc(gl_count*(sizeof(ElemType);printf("請(qǐng)輸入生成二叉樹(shù)的整型數(shù)據(jù)，前后數(shù)據(jù)用空格隔開(kāi)：n");for(i=0; i<gl_count; i+)scanf("%d”, &ri.key) ;ri.order = i+1;printf("n用戶(hù)輸入的數(shù)據(jù)及序號(hào)如下：n");for(i=0; i< gl_count; i+)print(ri);if(i+1)%6 = 0

17、) printf("n");select = 0; flag = 0; InitDSTable(bst);for(i=0; i<gl_count; i+) InsertBST(bst, ri);printf("n按中序遍歷該二叉排序樹(shù)的結(jié)果如下：n");TraverseOrderDSTable(bst, print);cout<<endl<<endl<<”以下是對(duì)二叉排序樹(shù)的基本操作："<<endl<<"1.查找一個(gè)節(jié)點(diǎn)"<<endl<<

18、;"2.插入一個(gè)節(jié)點(diǎn)"<<endl<<"3.刪除一個(gè)節(jié)點(diǎn)"<<endl<<"4.判別二元查找樹(shù)是否為平衡二叉樹(shù)"<<endl<<"5.二叉樹(shù)轉(zhuǎn)換為平衡二叉樹(shù)"<<endl<<"6.退出系統(tǒng)"<<endl;doif(flag = 6);printf("n請(qǐng)輸入二叉排序樹(shù)基本操作的選項(xiàng)：”)；scanf("%d”, &select);switch(select)ca

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

20、排序樹(shù)中存在此值：");print(p->data);elsetempr(ElemType*)(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 = tempr

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

22、;if(p)tempr (ElemType*)(malloc(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 = temp

23、ri.order; t+;printf("二叉排序樹(shù)中該數(shù)據(jù)已經(jīng)刪除。");TraverseOrderDSTable(bst, print);else printf("需刪除的數(shù)據(jù)不存在于二叉樹(shù)中。")；break;case 4: depth = (int*)malloc(gl_count*(sizeof(int);10vtfl /理工學(xué)茂課程設(shè)計(jì)(論文)BST_DepthDiff(bst, depth); max = depth0;for(i=1 ; i<gl_count; i+)if(max < depthi) max = depthi;

24、if(max < 2) printf("n該二叉排序樹(shù)是平衡二叉樹(shù)。");else printf("n該二叉排序樹(shù)不是平衡二叉樹(shù)。");if(max > 4)printf("n該二叉排序樹(shù)有結(jié)點(diǎn)的左右子樹(shù)之差大于4,系統(tǒng)建議您將該二叉排序樹(shù)轉(zhuǎn)換成平衡二叉樹(shù)。");break;case 5: InitDSTable(avl);for(i =0; i < gl_count; i+)InsertAVL(avl, ri, k);printf("該二叉排序樹(shù)轉(zhuǎn)換成了平衡二叉樹(shù)");TraverseOrder

25、DSTable(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ù)用空格符隔開(kāi);請(qǐng)麗人生質(zhì)二義陰的要型數(shù)據(jù).期后敘據(jù)用三格府升1 14 S & 12 15 21 23 3& 9 10隨后系統(tǒng)會(huì)自動(dòng)對(duì)數(shù)據(jù)進(jìn)行中序遍歷；用戶(hù)稀人的數(shù)據(jù)及序號(hào)如不：<14.IX5.2><G,3><12.4(15.GX21,6><2"7><%,Q*9

26、><10)按中序遍歷該二叉排序樹(shù)的結(jié)果如下；<£*2><6*9*»><1瓦10><12t4X14.IX15.SX 21,(><23*7>< 溝 8>功能菜單;12dj松序平樹(shù) 為叉 否二 日南 樹(shù)平排點(diǎn)點(diǎn)點(diǎn)我為 叉節(jié)節(jié)-睿換 二-元襄 對(duì)二一二WH 日拆人除別叉出 下查ijggS二退 JA - - - - - - c j 2 3 4 5 6vtfl 山穴N孝茂課程設(shè)計(jì)（論文）執(zhí)行節(jié)點(diǎn)的查找功能;眄磊翻勰I本鼾的選項(xiàng)” L叉排序期中存在此值匕（一”一c14樹(shù)基歷該二叉排 2><6執(zhí)行插入功能;人入已序< 捋花由請(qǐng)執(zhí)行刪除功能;判斷是