數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(論文)平衡二叉樹的生成

1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)課程名稱： 平衡二叉樹的生成 院 系： 信息工程學(xué)院 年級專業(yè)： 10級計(jì)科 學(xué) 號(hào)： 0942151201 學(xué)生姓名： 指導(dǎo)教師： 開題時(shí)間： 2010 年 12 月 01 日完成時(shí)間： 2010 年 12 月 31 日信 息 工 程 學(xué) 院 安徽新華學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)成績評定表院 系：信息工程學(xué)院 年級專業(yè)： 學(xué) 號(hào)： 姓 名： 設(shè)計(jì)題目：成績評定： 摘要本篇論文系計(jì)科專業(yè)10年末課程設(shè)計(jì)論文，按照相應(yīng)要求寫作而成。主要討論的是平衡二叉樹的生成問題，借助本程序可以由用戶輸入數(shù)值，并生成平衡二叉樹，并可以對數(shù)據(jù)進(jìn)行方便的修改和刪除添加，任意插入或刪除一個(gè)結(jié)點(diǎn)后

2、仍然要求任然構(gòu)成平衡二叉樹，并按中序遍歷輸出這棵平衡二叉樹。本論文共由五個(gè)章構(gòu)成，每個(gè)內(nèi)容獨(dú)立成章，各章下設(shè)相應(yīng)子章節(jié)。各個(gè)章節(jié)逐漸遞進(jìn)，分別是： 第一章：需求分析 第二章 系統(tǒng)設(shè)計(jì) 第三章 編碼 第四章 測試 第五章 維護(hù)本論文特點(diǎn)：1. 論述清楚，目錄詳盡，可以方便的查詢相應(yīng)章節(jié)，方便使用。2. 圖文結(jié)合，幾乎沒一個(gè)子程序模塊都有相應(yīng)的流程圖與之對應(yīng)，有利于讀者理解每個(gè)子程序的設(shè)計(jì)思路。3. 模塊分化清晰，每個(gè)模塊獨(dú)立成節(jié)，又彼此聯(lián)系，深化了c語言模塊化編程的特點(diǎn)。4. 測試模塊配合對應(yīng)的運(yùn)行截圖，真實(shí)可信，對讀者理解程序的運(yùn)行情況起到了很大作用。5. 程序清單完整詳細(xì)，解釋詳細(xì)。目 錄第

3、一章 需求分析11.1 功能描述11.2 數(shù)據(jù)詞典1第二章 系統(tǒng)設(shè)計(jì)3 2.1 基本概念介紹3 2.2 總體設(shè)計(jì)8 2.3 插入結(jié)點(diǎn)10 2.4 刪除結(jié)點(diǎn)11 2.5 中序遍歷11第三章 編碼123.1 總體編碼123.2 總流程圖153.3 以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理16第四章 測試174.1 創(chuàng)建二叉樹測試174.2 插入結(jié)點(diǎn)測試194.3 刪除結(jié)點(diǎn)測試204.4 中序遍歷結(jié)點(diǎn)測試214.5 先序遍歷測試21第五章 維護(hù)225.1 維護(hù)22第一章 需求分析1.1功能描述平衡二叉樹是數(shù)據(jù)結(jié)構(gòu)中一個(gè)非常重要的概念。它對二叉樹的優(yōu)化和提高查詢效率有重要的作用，它是動(dòng)態(tài)查找的一個(gè)

4、非常重要方法，它在實(shí)際生產(chǎn)中有著廣泛的應(yīng)用。通過本程序的設(shè)計(jì)編寫所要求達(dá)到的目的是：1. 充分理解和掌握二叉樹、平衡二叉樹的相關(guān)概念和知識(shí)。2. 掌握平衡二叉樹的生成、結(jié)點(diǎn)刪除、插入等操作過程。3. 并實(shí)現(xiàn)從鍵盤上輸入一系列數(shù)據(jù)（整型），建立一棵平衡二叉樹。4. 任意插入或刪除一個(gè)結(jié)點(diǎn)后仍然要求構(gòu)成平衡二叉樹。5. 按先序和中序遍歷輸出這棵平衡二叉樹。1.2數(shù)據(jù)字典平衡因子 任意結(jié)點(diǎn)左子樹與右子樹深度之差時(shí)間復(fù)雜度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。

5、并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為t(n)。bst 二叉排序樹(binary sort tree：bst) 1、二叉排序樹的定義 二叉排序樹(binary sort tree)又稱二叉查找(搜索)樹(binary search tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹： 若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 左、右子樹本身又各是一棵二叉排序樹。avl樹avl樹是最先發(fā)明的

6、自平衡二叉查找樹。在avl樹中任何節(jié)點(diǎn)的兩個(gè)兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是o（log n）。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。結(jié)點(diǎn) 包括一個(gè)數(shù)據(jù)元素及若干個(gè)指向其它子樹的分支；例如，a，b，c，d等。 在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。 在c語言中，鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)；二為下一個(gè)結(jié)點(diǎn)的地址，即指針域和數(shù)據(jù)域。 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對應(yīng)于一個(gè)儲(chǔ)存單元，這種儲(chǔ)存單元稱為儲(chǔ)

7、存結(jié)點(diǎn)，也可簡稱結(jié)點(diǎn)。第二章 系統(tǒng)設(shè)計(jì)2.1 基本概念介紹樹的概念樹（tree）是n（n=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：1) 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；2) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m（m0）個(gè)互不相交的有限集t1，t2.tm，其中每一個(gè)集合又是一棵樹，并且稱為根的子樹（subtree）?！纠咳鐖D1-1所示：abcedfgh圖1-1圖1是有8個(gè)結(jié)點(diǎn)的樹，其中a是根，其余結(jié)點(diǎn)分成2個(gè)子集：t1=b，d，t2=c，e，f，g，h；t1和t2都是根a的子樹，且本身也是一棵樹。平衡二叉樹的概念形態(tài)勻稱的二叉樹稱為平衡二叉樹 (balanced binary tree) ：若 t 是一

8、棵非空二叉樹，其左、右子樹分別為 tl 和 tr ，令 hl 和 hr 分別為左、右子樹的深度。當(dāng)且僅當(dāng)tl 、 tr 都是平衡二叉樹； hl hr 1；時(shí)，則 t 是平衡二叉樹?！纠咳鐖D1-2 所示：aaacbcbcbefddhg（a）平衡二叉樹 （b）非平衡二叉樹圖1-2 平衡二叉樹與非平衡二叉樹相應(yīng)地定義 hl hr 為二叉平衡樹的平衡因子 。因此，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子可能是 -1 ， 0 ， 1 。若一棵二叉樹上任一結(jié)點(diǎn)的平衡因子的絕對值都不大于 1 ，則該樹是就平衡二叉樹。遍歷的概念遍歷二叉樹指按某條搜索路徑訪問樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。

9、動(dòng)態(tài)平衡技術(shù)的概念adelson-velskii 和 landis 提出了一個(gè)動(dòng)態(tài)地保持二叉排序樹平衡的方法，其基本思想是：在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性，如果是因插入結(jié)點(diǎn)而破壞了樹的平衡性，則找出其中最小不平衡子樹，在保持排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹簡稱為 avl 樹。為了保證二叉排序樹的高度為lgn，從而保證二叉排序樹上實(shí)現(xiàn)的插入、刪除和查找等基本操作的平均時(shí)間為o(lgn)，在往樹中插入或刪除結(jié)點(diǎn)時(shí)，要調(diào)整樹的形態(tài)來保持樹的平衡。使之既保持bst性質(zhì)不變又保

10、證樹的高度在任何情況下均為o(lgn)，從而確保樹上的基本操作在最壞情況下的時(shí)間均為o(lgn)。注意：1) 任一結(jié)點(diǎn)的左右子樹的高度均相同，則二叉樹是完全平衡的。通常，只要二叉樹的高度為o(1gn)，就可看作是平衡的。2) 平衡的二叉排序樹指滿足bst性質(zhì)的平衡二叉樹。3) avl樹中任一結(jié)點(diǎn)的左、右子樹的高度之差的絕對值不超過1。在最壞情況下，n個(gè)結(jié)點(diǎn)的avl樹的高度約為1.44lgn。而完全平衡的二叉樹度高約為lgn，avl樹是接近最優(yōu)的。最小不平衡子樹的概念以離插入結(jié)點(diǎn)最近、且平衡因子絕對值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹。假設(shè)二叉排序樹的最小不平衡子樹的根結(jié)點(diǎn)為 a ，則調(diào)整該子樹的規(guī)

11、律可歸納為下列四種情況：abxxba 圖1-3（1）ll 型：新結(jié)點(diǎn) x 插在 a 的左孩子的左子樹里。調(diào)整方法見圖1-3。圖中以 b 為軸心，將 a 結(jié)點(diǎn)從 b 的右上方轉(zhuǎn)到 b 的右下側(cè)，使 a 成為 b 的右孩子。abxbax圖（2）rr 型：新結(jié)點(diǎn) x 插在 a 的右孩子的右子樹里。調(diào)整方法見圖 。圖中以 b 為軸心，將 a 結(jié)點(diǎn)從 b 的左上方轉(zhuǎn)到 b 的左下側(cè)，使 a 成為 b 的左孩子。a圖（3）lr 型：新結(jié)點(diǎn) x 插在 a 的左孩子的右子樹里。調(diào)整方法見圖 。分為兩步進(jìn)行：第一步以 x 為軸心，將 b 從 x 的左上方轉(zhuǎn)到 x 的左下側(cè)，使 b 成為 x 的左孩子， x 成為

12、 a 的左孩子。第二步跟 ll 型一樣處理 ( 應(yīng)以 x 為軸心 ) 。圖（4）rl 型：新結(jié)點(diǎn) x 插在 a 的右孩子的左子樹里。調(diào)整方法見圖。分為兩步進(jìn)行：第一步以 x 為軸心，將 b 從 x 的右上方轉(zhuǎn)到 x 的右下側(cè)，使 b 成為 x 的右孩子， x 成為 a 的右孩子。第二步跟 rr 型一樣處理 ( 應(yīng)以 x 為軸心 ) 。2.2 總體設(shè)計(jì)我們希望由任何初始序列構(gòu)成的二叉排序樹都是avl樹。因?yàn)閍vl樹上任何結(jié)點(diǎn)的左右子樹的深度之差都不超過1，則可以證明它的深度和logn是同數(shù)量級的（其中n為結(jié)點(diǎn)數(shù)）。由此，它的平均查找長度也是和logn同數(shù)量級的。如何使構(gòu)成的二叉排序樹成為平衡樹呢

13、？先看一個(gè)具體的例子（常見圖4）。假設(shè)表中關(guān)鍵字序列為（10，24，30，88，53）?？諛浜?個(gè)結(jié)點(diǎn)10的樹顯然都是平衡的二叉樹。在插入24之后依是平衡的，只是根結(jié)點(diǎn)的平衡因子bf由0變?yōu)?；在繼續(xù)插入30之后，由于結(jié)點(diǎn)10的bf值由1變成2，由此出現(xiàn)不平衡現(xiàn)象。此時(shí)好比一根扁擔(dān)出現(xiàn)一頭重一頭輕的現(xiàn)象，若能將扁擔(dān)的支撐點(diǎn)由10改成至24，扁擔(dān)的兩頭就平衡了。由此，可以對樹左一個(gè)向左逆時(shí)針“旋轉(zhuǎn)”的操作，令結(jié)點(diǎn)24為根，而結(jié)點(diǎn)10為它的左子樹，此時(shí)，結(jié)點(diǎn)10和24的平衡因子都為0，而且依保持二叉排序樹的特性。在繼續(xù)插入88和53之后，由于結(jié)點(diǎn)30的bf值由1變成2，排序樹中出現(xiàn)了新的不平衡現(xiàn)象

14、，需要調(diào)整。當(dāng)此時(shí)由于結(jié)點(diǎn)53插在結(jié)點(diǎn)88結(jié)點(diǎn)的左子樹上，因此不能和上作簡單調(diào)整。對于以結(jié)點(diǎn)30為根的子樹來說，即要保持二叉排序樹的特性，又要平衡，則必須以53作為根結(jié)點(diǎn)，而使37為它的左子樹的根，88成為它的左子樹的根。這好比對樹作了兩次“旋轉(zhuǎn)”操作先向右順時(shí)針，后向左逆時(shí)針（見圖2-7（f）（h），使二叉排序樹由不平衡轉(zhuǎn)化為平衡。一般情況下，假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為最小不平衡子樹的概念中提到的4中操作。圖2-7 平衡二叉樹的生成過程（a）空樹；（b）插入10；（c）插入24；（d）插入37；（e）向左逆時(shí)針右旋轉(zhuǎn)平衡；（f）相繼插入90和53；（g）

15、第一次向右順時(shí)針旋轉(zhuǎn)；（h）第二次向左逆時(shí)針旋轉(zhuǎn)平衡4種插入中，（1）和（3）對稱，（2）和（4）對稱。旋轉(zhuǎn)操作的正確性容易由“保持二叉排序樹的特性：中序遍歷所得關(guān)鍵字序列自小到大有序”證明之。當(dāng)平衡二叉樹因插入或者刪除結(jié)點(diǎn)而失去平衡時(shí)，僅需對最小不平衡子樹進(jìn)行平衡旋轉(zhuǎn)處理即可。因?yàn)榻?jīng)過旋轉(zhuǎn)處理之后的子樹深度和插入或刪除之前相同，因而不影響插入或刪除路徑上所有祖先結(jié)點(diǎn)的平衡。2.3 插入結(jié)點(diǎn)在平衡二叉排序樹bbst上插入一個(gè)新數(shù)據(jù)元素e的遞規(guī)算法可以描述如下：(1) 若bbst為空樹，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為bbst的根結(jié)點(diǎn)，樹的深度增加1；(2) 若e的關(guān)鍵字和bbst的根結(jié)點(diǎn)的關(guān)

16、鍵字相等，則不進(jìn)行插入；(3) 若e的關(guān)鍵字小于bbst的根結(jié)點(diǎn)的關(guān)鍵字，而且在bbst的左子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在bbst的左子樹上，并且當(dāng)插入之后的左子樹深度增加1時(shí)，分別就下列情況處理之：1. bbst的根結(jié)點(diǎn)的平衡因子為1（右子樹深度大于左子樹深度）：則將根結(jié)點(diǎn)的平衡因子更改為0，bbst的深度不變；2. bbst的根結(jié)點(diǎn)的平衡因子為0（左，右子樹深度相等）：則將根結(jié)點(diǎn)的平衡因子更改為1，bbst的深度增加1；3. bbst的根結(jié)點(diǎn)的平衡因子為1（左子樹深度大于右子樹深度）：若bbst的左子樹根結(jié)點(diǎn)的平衡因子為1，則需要進(jìn)行單向右旋平衡處理，并且在右旋處理之后將

17、根結(jié)點(diǎn)和右子樹根結(jié)點(diǎn)的平衡因子更改為0，樹的深度不變；若bbst的左子樹根結(jié)點(diǎn)的平衡因子為1，這需進(jìn)行先向左后向右的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點(diǎn)和其左、右子樹根結(jié)點(diǎn)的平衡因子，樹的深度不變；(4) 若e的關(guān)鍵字大于bbst的根結(jié)點(diǎn)的關(guān)鍵字，而且在bbst的右子樹中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在bbst的右子樹上，并且當(dāng)插入之后的右子樹深度增加1時(shí)，分別就不同情況處理。2.4 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)過程與插入結(jié)點(diǎn)的操作類似，基本過程是：平衡二叉樹-找到要?jiǎng)h除的結(jié)點(diǎn)-刪除一個(gè)結(jié)點(diǎn)-變成二叉樹-旋轉(zhuǎn)-變回平衡二叉樹。具體過程將詳細(xì)設(shè)計(jì)中的代碼。2.5 中序遍歷右遍歷的定義可知

18、，中序遍歷二叉樹的遞規(guī)算法可以定義為：若二叉樹為空，則空操作；否則1) 中序遍歷左子樹2) 訪問根結(jié)點(diǎn)3) 中序遍歷右子樹如中序遍歷圖2-8的二叉樹，結(jié)點(diǎn)的訪問順序?yàn)椋篴bcdefg圖2-8第三章 編碼3.1 總體編碼a. 使用的頭文件#include #include b. 常量定義# define lh 1/*左高*/# define eh 0/*等高*/# define rh -1/*右高*/# define true 1# define false 0c. 全局變量定義int taller=0;/*taller反映t長高與否*/int shorter=0;/*shorter反映t變矮與

19、否*/d. 數(shù)據(jù)結(jié)構(gòu)定義/*根據(jù)平衡二叉樹特點(diǎn)可以定義平衡二叉樹的存儲(chǔ)結(jié)構(gòu)*/*二叉排序樹的類型定義*/typedef struct bstnode int data;/*結(jié)點(diǎn)值*/int bf;/*結(jié)點(diǎn)的平衡因子*/struct bstnode * lchild, * rchild;/*分別指向左右孩子的指針*/bstnode, *bstree;/*同時(shí)聲明一個(gè)bstnode和一個(gè)指針類型的*bstree*/e. 部分關(guān)鍵函數(shù)原型說明void midorder(bstree t)/*樹的中序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)點(diǎn)值，不返回值*/bstree r_rotate(bstr

20、ee p)/*對以p為根的二叉排序樹作右旋處理，處理之p指向新的樹根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的左子樹根結(jié)點(diǎn)*/bstree l_rotate(bstree p) /*對以p為根的二叉排序樹作左旋處理，處理之p指向新的樹根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的右子樹根結(jié)點(diǎn)*/bstree leftbalance(bstree t)/*對以指針t所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance(bstree t)/*對以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree insertavl(bstree t, int

21、 e)/*向平衡樹中插入一個(gè)結(jié)點(diǎn)，返回插入后的新根結(jié)點(diǎn)*/bstree leftbalance1(bstree p)/*刪除結(jié)點(diǎn)時(shí)對以指針t所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance1(bstree p) /*刪除結(jié)點(diǎn)時(shí)對以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree delete(bstree q, bstree r) /*對結(jié)點(diǎn)進(jìn)行刪除處理，本算法結(jié)束時(shí)指針q指向新的根結(jié)點(diǎn)*/bstree deleteavl(bstree p, int e) /*找到要?jiǎng)h除的結(jié)點(diǎn),并調(diào)用刪

22、除函數(shù)對其進(jìn)行刪除，本算法結(jié)束時(shí)指針p指向新的根結(jié)點(diǎn)*/bstree creatnode(int nodevalue) /*建立關(guān)鍵字值為nodevalue的新結(jié)點(diǎn)，返回根結(jié)點(diǎn)*/3.2 總流程圖開始輸入e ebuildtreedeleteavlmidorderrootorderexitbreak結(jié)束e=n,n=(1,2,3,4,5)e=1e=5e=2e=4e=3insertavl進(jìn)入功能選擇界面，用戶按照提示輸入相應(yīng)選擇項(xiàng)數(shù)值，選擇后程序根據(jù)用戶的輸入調(diào)用相應(yīng)函數(shù)3.3 以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理t-bf=rc-bf=ehl_rotate開始rc=t-rchildrc-bf

23、ld=rc-lchildld-bfbf=lht-bf=lhrc-bf=eht-bf=rc-bf=eht-bf=ehrc-bf=rhld-bf=ehr_rotatel_rotatereturn t bf=rhbf=rhbf=eh其他旋轉(zhuǎn)類推第四章 測試4.1 創(chuàng)建平衡二叉樹測試第一步：選擇1，如圖4-1第二步：輸入序列（10，24，30，88，53）創(chuàng)建一刻二叉平衡樹，以0為結(jié)尾，如圖4-2圖4-1圖4-2第三步：為查看創(chuàng)建結(jié)果，我們選擇5，先序輸出二叉樹，如圖4-3圖4-34.2 插入結(jié)點(diǎn)測試第一步：選擇2，插入一個(gè)新結(jié)點(diǎn)，其值為7，插入后選擇5，第二步：先序輸出該樹：4.3 刪除結(jié)點(diǎn)測試第一

24、步：選擇3刪除一個(gè)結(jié)點(diǎn)，這里刪除結(jié)點(diǎn)7第二步：先序輸出該樹：4.4 中序遍歷二叉樹第一步：輸入4，中序遍歷二叉樹：4.5先序遍歷二叉樹第一步：輸入5，先序遍歷二叉樹：第五章 維護(hù)通過平衡二叉樹的生成程序的設(shè)計(jì)，我們很好的理解了平衡二叉樹的生成和各項(xiàng)操作的相關(guān)知識(shí)，同時(shí)還較好的掌握了動(dòng)態(tài)查找相關(guān)概念。4、程序調(diào)試與體會(huì)平衡二叉樹的生成是數(shù)據(jù)結(jié)構(gòu)中一個(gè)重要的存儲(chǔ)結(jié)構(gòu)。由于本程序的輸入較多，所以輸入數(shù)據(jù)時(shí)必須小心細(xì)致。本程序比較復(fù)雜，需要使用結(jié)構(gòu)體并使用了指針。必須將程序分解為多個(gè)子程序以降低編寫難度。適當(dāng)使用全局常量可以控制有效控制內(nèi)存溢出。由于程序較大，調(diào)試不容易易找出程序中的隱藏錯(cuò)誤，測試時(shí)候

25、沒有發(fā)現(xiàn)錯(cuò)誤，隱藏的難以發(fā)現(xiàn)。編寫過程中發(fā)現(xiàn)很多困難，都是查找參考書查找解決方法，在后來程序運(yùn)行過程中應(yīng)多結(jié)合相應(yīng)參考書，查找問題，便于后期維護(hù)。附錄：【1】本論文寫作期間參考了大量書籍資料，由于時(shí)間限制和水平的限制，難免有錯(cuò)誤和不盡如人意的地方，希望老師指正，幫助我水平的提高，特此感謝【2】參考書目1 數(shù)據(jù)結(jié)構(gòu) 黃劉生 高等教育出版社2 c語言程序設(shè)計(jì) 譚浩強(qiáng)（第二版） 清華大學(xué)出版社 3 c primer plus（第四版）中文版 人民郵電出版社 【3】程序清單：#include #include # define lh 1/*左高*/# define eh 0/*等高*/# define

26、 rh -1/*右高*/# define true 1# define false 0int taller=0;/*taller反映t長高與否*/int shorter=0;/*shorter反映t變矮與否*/*二叉排序樹的類型定義*/typedef struct bstnode int data;/*結(jié)點(diǎn)值*/int bf;/*結(jié)點(diǎn)的平衡因子*/struct bstnode * lchild, * rchild;/*分別指向左右孩子的指針*/bstnode, *bstree;/*同時(shí)聲明一個(gè)bstnode和一個(gè)指針類型的*bstree*/*樹的中序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)

27、點(diǎn)值*/void midorder(bstree t) /*中序遍歷的特點(diǎn)是：當(dāng)二叉樹為空，則空操作；否則*/*1.中序遍歷左子樹；*/*2.訪問根結(jié)點(diǎn)；*/*3.中序遍歷右子樹。*/if(t-lchild) midorder(t-lchild); if(t-data) /*以適當(dāng)?shù)男问礁袷交敵龈鱾€(gè)結(jié)點(diǎn)及其附加信息可以方便用戶重構(gòu)二叉樹*/printf( %d %d,t-data,t-bf);if (t-lchild ) printf( %d,t-lchild-data); else printf( -);if (t-rchild ) printf( %d,t-rchild-data); e

28、lse printf( -);printf(n);if(t-rchild) midorder(t-rchild); /*樹的先序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)點(diǎn)值*/void rootorder(bstree t) /*先序遍歷的特點(diǎn)是：當(dāng)二叉樹為空，則空操作；否則*/*1.訪問根結(jié)點(diǎn)；*/*2.先序遍歷左子樹；*/*3.先序遍歷右子樹。*/if(t-data) printf( %d %d,t-data,t-bf);if (t-lchild ) printf( %d,t-lchild-data); else printf( -);if (t-rchild ) printf( %d

29、,t-rchild-data); else printf( -);printf(n);if(t-lchild) rootorder(t-lchild); if(t-rchild) rootorder(t-rchild); /*對以p為根的樹作右旋處理，處理之p指向新的樹根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的左子樹根結(jié)點(diǎn)*/bstree r_rotate(bstree p)bstnode *lc;/*聲明bstnode* 臨時(shí)變量*/lc=p-lchild;/*lc指向的*p的左子樹根結(jié)點(diǎn)*/p-lchild=lc-rchild;/*lc的右子樹掛接為*p的左子樹*/lc-rchild=p;p=lc;/*p指向

30、新的根結(jié)點(diǎn)*/return p;/*返回新的根結(jié)點(diǎn)*/*對以p為根的樹作左旋處理，處理之p指向新的樹根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的右子樹根結(jié)點(diǎn)*/bstree l_rotate(bstree p) bstnode *rc;/*聲明bstnode* 臨時(shí)變量*/rc=p-rchild;/*rc指向的*p的右子樹根結(jié)點(diǎn)*/p-rchild=rc-lchild;/*rc的左子樹掛接為*p的右子樹*/rc-lchild=p;p=rc;/*p指向新的根結(jié)點(diǎn)*/return p;/*返回新的根結(jié)點(diǎn)*/*對以指針t所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree leftbal

31、ance(bstree t) bstnode *lc,*rd;lc=t-lchild;/*lc指向*t的左子樹根結(jié)點(diǎn)*/switch(lc-bf)/*檢查*t的左子樹平衡度，并做相應(yīng)的平衡處理*/case lh:/*新結(jié)點(diǎn)插入在*t的左孩子的左子樹上，要做單右旋處理*/t-bf=lc-bf=eh;t=r_rotate(t);break;case rh:/*新結(jié)點(diǎn)插入在*t的左孩子的右子樹上，要做雙旋處理*/rd=lc-rchild;/*rd指向*t的左孩子的右子樹根*/switch(rd-bf)/*修改*t及其左孩子的平衡因子*/case lh:t-bf=rh;lc-bf=eh;break;c

32、ase eh:t-bf=lc-bf=eh;break;case rh:t-bf=eh;lc-bf=lh;break;rd-bf=eh;t-lchild=l_rotate(t-lchild);/*對*t的左孩子做左旋平衡處理*/t=r_rotate(t);/*對*t做右旋處理*/return t;/*對以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance(bstree t) bstree rc,ld;rc=t-rchild;/*rc指向*t的右子樹根結(jié)點(diǎn)*/switch(rc-bf)/*檢查*t的右子樹平衡度，并做相應(yīng)的平衡處理

33、*/case rh:/*新結(jié)點(diǎn)插入在*t的右孩子的右子樹上，要做單右旋處理*/t-bf=rc-bf=eh;t=l_rotate(t);break;case lh:/*新結(jié)點(diǎn)插入在*t的右孩子的左子樹上，要做雙旋處理*/ld=rc-lchild;/*ld指向*t的右孩子的左子樹根*/switch(ld-bf)/*修改*t及其右孩子的平衡因子*/case lh:t-bf=lh;rc-bf=eh;break;case eh:t-bf=rc-bf=eh;break;case rh:t-bf=eh;rc-bf=rh;break;ld-bf=eh;t-rchild=r_rotate(t-rchild);/

34、*對*t的右孩子做右旋平衡處理*/t=l_rotate(t);/*對*t做左旋處理*/return t;/*若在平衡的二叉排序樹t中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn),則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn),并返回插入后所建成的平衡二叉排序樹,否則返回null.若因插入而使二叉數(shù)失去平衡,則作平衡旋轉(zhuǎn)處理,布爾變量taller反映t長高與否*/bstree insertavl(bstree t, int e) bstree p;/*插入新結(jié)點(diǎn)，樹長高置taller為true*/if(!t)t=(bstree)malloc(sizeof(bstnode);t-data=e;t-lchild=t-rchild=

35、null;t-bf=eh;taller=true;else/*樹中存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入*/if(e=t-data)taller=false;return null;/*值小于則繼續(xù)在樹的左子樹中搜索*/if(e data)p=insertavl(t-lchild,e); /*插入到左子樹且左子樹長高*/if(p)t-lchild=p;if(taller)switch(t-bf)/*檢查*t的平衡度*/case lh:/*原本左子樹比右子樹高，需要做左平衡處理*/t=leftbalance(t);taller=false;break;case eh:/*原本左、右子樹同高，現(xiàn)因左

36、子樹爭高而使樹增高*/t-bf=lh;taller=true;break;case rh:/*原本右子樹比左子樹高，現(xiàn)在左右子樹等高*/t-bf=eh;taller=false;break;/*繼續(xù)在*t的右子樹中搜索*/else/*插入到右子樹且使右子樹長高*/p=insertavl(t-rchild,e);if (p)t-rchild=p;if(taller)switch(t-bf)/*檢查*t的平衡度*/case lh:/*原本左子樹比右子樹高，現(xiàn)在左右子樹等高*/t-bf=eh;taller=false;break;case eh:/*原本左、右子樹同高，現(xiàn)因右子樹增高而使樹增高*/t

37、-bf=rh;taller=true;break;case rh:/*原本右子樹比左子樹高，需要做右平衡處理*/t=rightbalance(t);taller=false;break;return t;/*刪除結(jié)點(diǎn)時(shí)對以指針p所指結(jié)點(diǎn)為根的樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針p指向新的根結(jié)點(diǎn)*/bstree leftbalance1(bstree p) bstree p1,p2;/*左子樹比右子樹高*/if(p-bf=1)p-bf=0;shorter=1;else if(p-bf=0)p-bf=-1;shorter=0;elsep1=p-rchild;if(p1-bf=0)p-rchild

38、= p1-lchild;p1-lchild = p;p1-bf = 1;p-bf = -1;p = p1;shorter = 0;else if(p1-bf=-1)p-rchild=p1-lchild;p1-lchild=p;p1-bf=p-bf=0;p=p1;shorter=1;elsep2=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;elsep-bf=0;p1-bf=-1;

39、p2-bf=0;p=p2;shorter=1;return p;/*刪除結(jié)點(diǎn)時(shí)對以指針t所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance1(bstree p) bstree p1,p2;if(p-bf=-1)p-bf=0;shorter=1;else if(p-bf=0)p-bf=1;shorter=0;elsep1=p-lchild;if(p1-bf=0)p-lchild = p1-rchild;p1-rchild = p;p1-bf=-1;p-bf=1;p=p1;shorter=0;else if(p1-bf=1)p-lchi

40、ld=p1-rchild;p1-rchild=p;p1-bf=p-bf=0;p=p1;shorter=1;elsep2=p1-rchild;p1-rchild = p2-lchild;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;elsep-bf=0;p1-bf=1;p2-bf=0;p=p2;shorter=1;return p;/*對結(jié)點(diǎn)進(jìn)行刪除處理*/bstree delete(bstree q,

41、bstree r) if(r-rchild=null)/*根結(jié)點(diǎn)的右子樹為空則將左子樹提高并標(biāo)記樹變矮了*/q-data=r-data;q=r;r=r-lchild;free(q);shorter=1;else/*繼續(xù)遞規(guī)搜索并刪除*/r-rchild=delete(q,r-rchild); return r;/*找到要?jiǎng)h除的結(jié)點(diǎn),并調(diào)用刪除函數(shù)對其進(jìn)行刪除*/bstree deleteavl(bstree p, int e) bstree q;/*拋棄空刪除*/if(p=null) return null;else if(e data)/*欲刪除值小于當(dāng)前結(jié)點(diǎn)值則繼續(xù)在左子樹中搜索*/p-lchild = deleteavl(p-lchild,e);if(shorter=1) p=leftbalance1(p);return p;else if(e p-data)/*欲刪除值大于當(dāng)前結(jié)點(diǎn)值則繼續(xù)在右子樹中搜索*/p-rchild=deleteavl(p-rchild,e);if(shorter=1) p=rightbalance1(p);return p;else/*找到了*/q=p;/*將p存儲(chǔ)到臨時(shí)變量q里面*/if(p-rchild=null)/如果p的右子樹為空則將其左子樹提高一層*/p