




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)課程名稱(chēng): 平衡二叉樹(shù)的生成 院 系: 信息工程學(xué)院 年級(jí)專(zhuān)業(yè): 10級(jí)計(jì)科 學(xué) 號(hào): 0942151201 學(xué)生姓名: 指導(dǎo)教師: 開(kāi)題時(shí)間: 2010 年 12 月 01 日完成時(shí)間: 2010 年 12 月 31 日信 息 工 程 學(xué) 院 安徽新華學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)成績(jī)?cè)u(píng)定表院 系:信息工程學(xué)院 年級(jí)專(zhuān)業(yè): 學(xué) 號(hào): 姓 名: 設(shè)計(jì)題目:成績(jī)?cè)u(píng)定: 摘要本篇論文系計(jì)科專(zhuān)業(yè)10年末課程設(shè)計(jì)論文,按照相應(yīng)要求寫(xiě)作而成。主要討論的是平衡二叉樹(shù)的生成問(wèn)題,借助本程序可以由用戶(hù)輸入數(shù)值,并生成平衡二叉樹(shù),并可以對(duì)數(shù)據(jù)進(jìn)行方便的修改和刪除添加,任意插入或刪除一個(gè)結(jié)點(diǎn)后
2、仍然要求任然構(gòu)成平衡二叉樹(shù),并按中序遍歷輸出這棵平衡二叉樹(shù)。本論文共由五個(gè)章構(gòu)成,每個(gè)內(nèi)容獨(dú)立成章,各章下設(shè)相應(yīng)子章節(jié)。各個(gè)章節(jié)逐漸遞進(jìn),分別是: 第一章:需求分析 第二章 系統(tǒng)設(shè)計(jì) 第三章 編碼 第四章 測(cè)試 第五章 維護(hù)本論文特點(diǎn):1. 論述清楚,目錄詳盡,可以方便的查詢(xún)相應(yīng)章節(jié),方便使用。2. 圖文結(jié)合,幾乎沒(méi)一個(gè)子程序模塊都有相應(yīng)的流程圖與之對(duì)應(yīng),有利于讀者理解每個(gè)子程序的設(shè)計(jì)思路。3. 模塊分化清晰,每個(gè)模塊獨(dú)立成節(jié),又彼此聯(lián)系,深化了c語(yǔ)言模塊化編程的特點(diǎn)。4. 測(cè)試模塊配合對(duì)應(yīng)的運(yùn)行截圖,真實(shí)可信,對(duì)讀者理解程序的運(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)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理16第四章 測(cè)試174.1 創(chuàng)建二叉樹(shù)測(cè)試174.2 插入結(jié)點(diǎn)測(cè)試194.3 刪除結(jié)點(diǎn)測(cè)試204.4 中序遍歷結(jié)點(diǎn)測(cè)試214.5 先序遍歷測(cè)試21第五章 維護(hù)225.1 維護(hù)22第一章 需求分析1.1功能描述平衡二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)中一個(gè)非常重要的概念。它對(duì)二叉樹(shù)的優(yōu)化和提高查詢(xún)效率有重要的作用,它是動(dòng)態(tài)查找的一個(gè)
4、非常重要方法,它在實(shí)際生產(chǎn)中有著廣泛的應(yīng)用。通過(guò)本程序的設(shè)計(jì)編寫(xiě)所要求達(dá)到的目的是: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)后仍然要求構(gòu)成平衡二叉樹(shù)。5. 按先序和中序遍歷輸出這棵平衡二叉樹(shù)。1.2數(shù)據(jù)字典平衡因子 任意結(jié)點(diǎn)左子樹(shù)與右子樹(shù)深度之差時(shí)間復(fù)雜度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上是不能算出來(lái)的,必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試,只需知道哪個(gè)算法花費(fèi)的時(shí)間多,哪個(gè)算法花費(fèi)的時(shí)間少就可以了。
5、并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多,它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為t(n)。bst 二叉排序樹(shù)(binary sort tree:bst) 1、二叉排序樹(shù)的定義 二叉排序樹(shù)(binary sort tree)又稱(chēng)二叉查找(搜索)樹(shù)(binary search tree)。其定義為:二叉排序樹(shù)或者是空樹(shù),或者是滿足如下性質(zhì)的二叉樹(shù): 若它的左子樹(shù)非空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值; 若它的右子樹(shù)非空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值; 左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。avl樹(shù)avl樹(shù)是最先發(fā)明的
6、自平衡二叉查找樹(shù)。在avl樹(shù)中任何節(jié)點(diǎn)的兩個(gè)兒子子樹(shù)的高度最大差別為一,所以它也被稱(chēng)為高度平衡樹(shù)。查找、插入和刪除在平均和最壞情況下都是o(log n)。增加和刪除可能需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。結(jié)點(diǎn) 包括一個(gè)數(shù)據(jù)元素及若干個(gè)指向其它子樹(shù)的分支;例如,a,b,c,d等。 在數(shù)據(jù)結(jié)構(gòu)的圖形表示中,對(duì)于數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示,一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn),簡(jiǎn)稱(chēng)結(jié)點(diǎn)。 在c語(yǔ)言中,鏈表中每一個(gè)元素稱(chēng)為“結(jié)點(diǎn)”,每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分:一為用戶(hù)需要用的實(shí)際數(shù)據(jù);二為下一個(gè)結(jié)點(diǎn)的地址,即指針域和數(shù)據(jù)域。 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)儲(chǔ)存單元,這種儲(chǔ)存單元稱(chēng)為儲(chǔ)
7、存結(jié)點(diǎn),也可簡(jiǎn)稱(chēng)結(jié)點(diǎn)。第二章 系統(tǒng)設(shè)計(jì)2.1 基本概念介紹樹(shù)的概念樹(shù)(tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中:1) 有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn);2) 當(dāng)n1時(shí),其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集t1,t2.tm,其中每一個(gè)集合又是一棵樹(shù),并且稱(chēng)為根的子樹(shù)(subtree)?!纠咳鐖D1-1所示:abcedfgh圖1-1圖1是有8個(gè)結(jié)點(diǎn)的樹(shù),其中a是根,其余結(jié)點(diǎn)分成2個(gè)子集:t1=b,d,t2=c,e,f,g,h;t1和t2都是根a的子樹(shù),且本身也是一棵樹(shù)。平衡二叉樹(shù)的概念形態(tài)勻稱(chēng)的二叉樹(shù)稱(chēng)為平衡二叉樹(shù) (balanced binary tree) :若 t 是一
8、棵非空二叉樹(shù),其左、右子樹(shù)分別為 tl 和 tr ,令 hl 和 hr 分別為左、右子樹(shù)的深度。當(dāng)且僅當(dāng)tl 、 tr 都是平衡二叉樹(shù); hl hr 1;時(shí),則 t 是平衡二叉樹(shù)。【例】如圖1-2 所示:aaacbcbcbefddhg(a)平衡二叉樹(shù) (b)非平衡二叉樹(shù)圖1-2 平衡二叉樹(shù)與非平衡二叉樹(shù)相應(yīng)地定義 hl hr 為二叉平衡樹(shù)的平衡因子 。因此,平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子可能是 -1 , 0 , 1 。若一棵二叉樹(shù)上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值都不大于 1 ,則該樹(shù)是就平衡二叉樹(shù)。遍歷的概念遍歷二叉樹(shù)指按某條搜索路徑訪問(wèn)樹(shù)中的每個(gè)結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次,而且僅被訪問(wèn)一次。
9、動(dòng)態(tài)平衡技術(shù)的概念adelson-velskii 和 landis 提出了一個(gè)動(dòng)態(tài)地保持二叉排序樹(shù)平衡的方法,其基本思想是:在構(gòu)造二叉排序樹(shù)的過(guò)程中,每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí),首先檢查是否因插入而破壞了樹(shù)的平衡性,如果是因插入結(jié)點(diǎn)而破壞了樹(shù)的平衡性,則找出其中最小不平衡子樹(shù),在保持排序樹(shù)特性的前提下,調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的連接關(guān)系,以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹(shù)簡(jiǎn)稱(chēng)為 avl 樹(shù)。為了保證二叉排序樹(shù)的高度為lgn,從而保證二叉排序樹(shù)上實(shí)現(xiàn)的插入、刪除和查找等基本操作的平均時(shí)間為o(lgn),在往樹(shù)中插入或刪除結(jié)點(diǎn)時(shí),要調(diào)整樹(shù)的形態(tài)來(lái)保持樹(shù)的平衡。使之既保持bst性質(zhì)不變又保
10、證樹(shù)的高度在任何情況下均為o(lgn),從而確保樹(shù)上的基本操作在最壞情況下的時(shí)間均為o(lgn)。注意:1) 任一結(jié)點(diǎn)的左右子樹(shù)的高度均相同,則二叉樹(shù)是完全平衡的。通常,只要二叉樹(shù)的高度為o(1gn),就可看作是平衡的。2) 平衡的二叉排序樹(shù)指滿足bst性質(zhì)的平衡二叉樹(shù)。3) avl樹(shù)中任一結(jié)點(diǎn)的左、右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。在最壞情況下,n個(gè)結(jié)點(diǎn)的avl樹(shù)的高度約為1.44lgn。而完全平衡的二叉樹(shù)度高約為lgn,avl樹(shù)是接近最優(yōu)的。最小不平衡子樹(shù)的概念以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹(shù)。假設(shè)二叉排序樹(shù)的最小不平衡子樹(shù)的根結(jié)點(diǎn)為 a ,則調(diào)整該子樹(shù)的規(guī)
11、律可歸納為下列四種情況:abxxba 圖1-3(1)ll 型:新結(jié)點(diǎn) x 插在 a 的左孩子的左子樹(shù)里。調(diào)整方法見(jiàn)圖1-3。圖中以 b 為軸心,將 a 結(jié)點(diǎn)從 b 的右上方轉(zhuǎn)到 b 的右下側(cè),使 a 成為 b 的右孩子。abxbax圖(2)rr 型:新結(jié)點(diǎn) x 插在 a 的右孩子的右子樹(shù)里。調(diào)整方法見(jiàn)圖 。圖中以 b 為軸心,將 a 結(jié)點(diǎn)從 b 的左上方轉(zhuǎn)到 b 的左下側(cè),使 a 成為 b 的左孩子。a圖(3)lr 型:新結(jié)點(diǎn) x 插在 a 的左孩子的右子樹(shù)里。調(diào)整方法見(jiàn)圖 。分為兩步進(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 的右孩子的左子樹(shù)里。調(diào)整方法見(jiàn)圖。分為兩步進(jìn)行:第一步以 x 為軸心,將 b 從 x 的右上方轉(zhuǎn)到 x 的右下側(cè),使 b 成為 x 的右孩子, x 成為 a 的右孩子。第二步跟 rr 型一樣處理 ( 應(yīng)以 x 為軸心 ) 。2.2 總體設(shè)計(jì)我們希望由任何初始序列構(gòu)成的二叉排序樹(shù)都是avl樹(shù)。因?yàn)閍vl樹(shù)上任何結(jié)點(diǎn)的左右子樹(shù)的深度之差都不超過(guò)1,則可以證明它的深度和logn是同數(shù)量級(jí)的(其中n為結(jié)點(diǎn)數(shù))。由此,它的平均查找長(zhǎng)度也是和logn同數(shù)量級(jí)的。如何使構(gòu)成的二叉排序樹(shù)成為平衡樹(shù)呢
13、?先看一個(gè)具體的例子(常見(jiàn)圖4)。假設(shè)表中關(guān)鍵字序列為(10,24,30,88,53)??諛?shù)和1個(gè)結(jié)點(diǎn)10的樹(shù)顯然都是平衡的二叉樹(shù)。在插入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)的兩頭就平衡了。由此,可以對(duì)樹(shù)左一個(gè)向左逆時(shí)針“旋轉(zhuǎn)”的操作,令結(jié)點(diǎn)24為根,而結(jié)點(diǎn)10為它的左子樹(shù),此時(shí),結(jié)點(diǎn)10和24的平衡因子都為0,而且依保持二叉排序樹(shù)的特性。在繼續(xù)插入88和53之后,由于結(jié)點(diǎn)30的bf值由1變成2,排序樹(shù)中出現(xiàn)了新的不平衡現(xiàn)象
14、,需要調(diào)整。當(dāng)此時(shí)由于結(jié)點(diǎn)53插在結(jié)點(diǎn)88結(jié)點(diǎn)的左子樹(shù)上,因此不能和上作簡(jiǎn)單調(diào)整。對(duì)于以結(jié)點(diǎn)30為根的子樹(shù)來(lái)說(shuō),即要保持二叉排序樹(shù)的特性,又要平衡,則必須以53作為根結(jié)點(diǎn),而使37為它的左子樹(shù)的根,88成為它的左子樹(shù)的根。這好比對(duì)樹(shù)作了兩次“旋轉(zhuǎn)”操作先向右順時(shí)針,后向左逆時(shí)針(見(jiàn)圖2-7(f)(h),使二叉排序樹(shù)由不平衡轉(zhuǎn)化為平衡。一般情況下,假設(shè)由于在二叉排序樹(shù)上插入結(jié)點(diǎn)而失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為最小不平衡子樹(shù)的概念中提到的4中操作。圖2-7 平衡二叉樹(shù)的生成過(guò)程(a)空樹(shù);(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)對(duì)稱(chēng),(2)和(4)對(duì)稱(chēng)。旋轉(zhuǎn)操作的正確性容易由“保持二叉排序樹(shù)的特性:中序遍歷所得關(guān)鍵字序列自小到大有序”證明之。當(dāng)平衡二叉樹(shù)因插入或者刪除結(jié)點(diǎn)而失去平衡時(shí),僅需對(duì)最小不平衡子樹(shù)進(jìn)行平衡旋轉(zhuǎn)處理即可。因?yàn)榻?jīng)過(guò)旋轉(zhuǎn)處理之后的子樹(shù)深度和插入或刪除之前相同,因而不影響插入或刪除路徑上所有祖先結(jié)點(diǎn)的平衡。2.3 插入結(jié)點(diǎn)在平衡二叉排序樹(shù)bbst上插入一個(gè)新數(shù)據(jù)元素e的遞規(guī)算法可以描述如下:(1) 若bbst為空樹(shù),則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為bbst的根結(jié)點(diǎn),樹(shù)的深度增加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的左子樹(shù)中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn),則將e插入在bbst的左子樹(shù)上,并且當(dāng)插入之后的左子樹(shù)深度增加1時(shí),分別就下列情況處理之:1. bbst的根結(jié)點(diǎn)的平衡因子為1(右子樹(shù)深度大于左子樹(shù)深度):則將根結(jié)點(diǎn)的平衡因子更改為0,bbst的深度不變;2. bbst的根結(jié)點(diǎn)的平衡因子為0(左,右子樹(shù)深度相等):則將根結(jié)點(diǎn)的平衡因子更改為1,bbst的深度增加1;3. bbst的根結(jié)點(diǎn)的平衡因子為1(左子樹(shù)深度大于右子樹(shù)深度):若bbst的左子樹(shù)根結(jié)點(diǎn)的平衡因子為1,則需要進(jìn)行單向右旋平衡處理,并且在右旋處理之后將
17、根結(jié)點(diǎn)和右子樹(shù)根結(jié)點(diǎn)的平衡因子更改為0,樹(shù)的深度不變;若bbst的左子樹(shù)根結(jié)點(diǎn)的平衡因子為1,這需進(jìn)行先向左后向右的雙向旋轉(zhuǎn)平衡處理,并且在旋轉(zhuǎn)處理之后,修改根結(jié)點(diǎn)和其左、右子樹(shù)根結(jié)點(diǎn)的平衡因子,樹(shù)的深度不變;(4) 若e的關(guān)鍵字大于bbst的根結(jié)點(diǎn)的關(guān)鍵字,而且在bbst的右子樹(shù)中不存在和e相同關(guān)鍵字的結(jié)點(diǎn),則將e插入在bbst的右子樹(shù)上,并且當(dāng)插入之后的右子樹(shù)深度增加1時(shí),分別就不同情況處理。2.4 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)過(guò)程與插入結(jié)點(diǎn)的操作類(lèi)似,基本過(guò)程是:平衡二叉樹(shù)-找到要?jiǎng)h除的結(jié)點(diǎn)-刪除一個(gè)結(jié)點(diǎn)-變成二叉樹(shù)-旋轉(zhuǎn)-變回平衡二叉樹(shù)。具體過(guò)程將詳細(xì)設(shè)計(jì)中的代碼。2.5 中序遍歷右遍歷的定義可知
18、,中序遍歷二叉樹(shù)的遞規(guī)算法可以定義為:若二叉樹(shù)為空,則空操作;否則1) 中序遍歷左子樹(shù)2) 訪問(wèn)根結(jié)點(diǎn)3) 中序遍歷右子樹(shù)如中序遍歷圖2-8的二叉樹(shù),結(jié)點(diǎn)的訪問(wè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長(zhǎng)高與否*/int shorter=0;/*shorter反映t變矮與
19、否*/d. 數(shù)據(jù)結(jié)構(gòu)定義/*根據(jù)平衡二叉樹(shù)特點(diǎn)可以定義平衡二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)*/*二叉排序樹(shù)的類(lèi)型定義*/typedef struct bstnode int data;/*結(jié)點(diǎn)值*/int bf;/*結(jié)點(diǎn)的平衡因子*/struct bstnode * lchild, * rchild;/*分別指向左右孩子的指針*/bstnode, *bstree;/*同時(shí)聲明一個(gè)bstnode和一個(gè)指針類(lèi)型的*bstree*/e. 部分關(guān)鍵函數(shù)原型說(shuō)明void midorder(bstree t)/*樹(shù)的中序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)點(diǎn)值,不返回值*/bstree r_rotate(bstr
20、ee p)/*對(duì)以p為根的二叉排序樹(shù)作右旋處理,處理之p指向新的樹(shù)根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的左子樹(shù)根結(jié)點(diǎn)*/bstree l_rotate(bstree p) /*對(duì)以p為根的二叉排序樹(shù)作左旋處理,處理之p指向新的樹(shù)根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的右子樹(shù)根結(jié)點(diǎn)*/bstree leftbalance(bstree t)/*對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance(bstree t)/*對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree insertavl(bstree t, int
21、 e)/*向平衡樹(shù)中插入一個(gè)結(jié)點(diǎn),返回插入后的新根結(jié)點(diǎn)*/bstree leftbalance1(bstree p)/*刪除結(jié)點(diǎn)時(shí)對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance1(bstree p) /*刪除結(jié)點(diǎn)時(shí)對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree delete(bstree q, bstree r) /*對(duì)結(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ù)對(duì)其進(jìn)行刪除,本算法結(jié)束時(shí)指針p指向新的根結(jié)點(diǎn)*/bstree creatnode(int nodevalue) /*建立關(guān)鍵字值為nodevalue的新結(jié)點(diǎn),返回根結(jié)點(diǎn)*/3.2 總流程圖開(kāi)始輸入e ebuildtreedeleteavlmidorderrootorderexitbreak結(jié)束e=n,n=(1,2,3,4,5)e=1e=5e=2e=4e=3insertavl進(jìn)入功能選擇界面,用戶(hù)按照提示輸入相應(yīng)選擇項(xiàng)數(shù)值,選擇后程序根據(jù)用戶(hù)的輸入調(diào)用相應(yīng)函數(shù)3.3 以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理t-bf=rc-bf=ehl_rotate開(kāi)始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)類(lèi)推第四章 測(cè)試4.1 創(chuàng)建平衡二叉樹(shù)測(cè)試第一步:選擇1,如圖4-1第二步:輸入序列(10,24,30,88,53)創(chuàng)建一刻二叉平衡樹(shù),以0為結(jié)尾,如圖4-2圖4-1圖4-2第三步:為查看創(chuàng)建結(jié)果,我們選擇5,先序輸出二叉樹(shù),如圖4-3圖4-34.2 插入結(jié)點(diǎn)測(cè)試第一步:選擇2,插入一個(gè)新結(jié)點(diǎn),其值為7,插入后選擇5,第二步:先序輸出該樹(shù):4.3 刪除結(jié)點(diǎn)測(cè)試第一
24、步:選擇3刪除一個(gè)結(jié)點(diǎn),這里刪除結(jié)點(diǎn)7第二步:先序輸出該樹(shù):4.4 中序遍歷二叉樹(shù)第一步:輸入4,中序遍歷二叉樹(shù):4.5先序遍歷二叉樹(shù)第一步:輸入5,先序遍歷二叉樹(shù):第五章 維護(hù)通過(guò)平衡二叉樹(shù)的生成程序的設(shè)計(jì),我們很好的理解了平衡二叉樹(shù)的生成和各項(xiàng)操作的相關(guān)知識(shí),同時(shí)還較好的掌握了動(dòng)態(tài)查找相關(guān)概念。4、程序調(diào)試與體會(huì)平衡二叉樹(shù)的生成是數(shù)據(jù)結(jié)構(gòu)中一個(gè)重要的存儲(chǔ)結(jié)構(gòu)。由于本程序的輸入較多,所以輸入數(shù)據(jù)時(shí)必須小心細(xì)致。本程序比較復(fù)雜,需要使用結(jié)構(gòu)體并使用了指針。必須將程序分解為多個(gè)子程序以降低編寫(xiě)難度。適當(dāng)使用全局常量可以控制有效控制內(nèi)存溢出。由于程序較大,調(diào)試不容易易找出程序中的隱藏錯(cuò)誤,測(cè)試時(shí)候
25、沒(méi)有發(fā)現(xiàn)錯(cuò)誤,隱藏的難以發(fā)現(xiàn)。編寫(xiě)過(guò)程中發(fā)現(xiàn)很多困難,都是查找參考書(shū)查找解決方法,在后來(lái)程序運(yùn)行過(guò)程中應(yīng)多結(jié)合相應(yīng)參考書(shū),查找問(wèn)題,便于后期維護(hù)。附錄:【1】本論文寫(xiě)作期間參考了大量書(shū)籍資料,由于時(shí)間限制和水平的限制,難免有錯(cuò)誤和不盡如人意的地方,希望老師指正,幫助我水平的提高,特此感謝【2】參考書(shū)目1 數(shù)據(jù)結(jié)構(gòu) 黃劉生 高等教育出版社2 c語(yǔ)言程序設(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長(zhǎng)高與否*/int shorter=0;/*shorter反映t變矮與否*/*二叉排序樹(shù)的類(lèi)型定義*/typedef struct bstnode int data;/*結(jié)點(diǎn)值*/int bf;/*結(jié)點(diǎn)的平衡因子*/struct bstnode * lchild, * rchild;/*分別指向左右孩子的指針*/bstnode, *bstree;/*同時(shí)聲明一個(gè)bstnode和一個(gè)指針類(lèi)型的*bstree*/*樹(shù)的中序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)
27、點(diǎn)值*/void midorder(bstree t) /*中序遍歷的特點(diǎn)是:當(dāng)二叉樹(shù)為空,則空操作;否則*/*1.中序遍歷左子樹(shù);*/*2.訪問(wèn)根結(jié)點(diǎn);*/*3.中序遍歷右子樹(shù)。*/if(t-lchild) midorder(t-lchild); if(t-data) /*以適當(dāng)?shù)男问礁袷交敵龈鱾€(gè)結(jié)點(diǎn)及其附加信息可以方便用戶(hù)重構(gòu)二叉樹(shù)*/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); /*樹(shù)的先序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)點(diǎn)值*/void rootorder(bstree t) /*先序遍歷的特點(diǎn)是:當(dāng)二叉樹(shù)為空,則空操作;否則*/*1.訪問(wèn)根結(jié)點(diǎn);*/*2.先序遍歷左子樹(shù);*/*3.先序遍歷右子樹(shù)。*/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); /*對(duì)以p為根的樹(shù)作右旋處理,處理之p指向新的樹(shù)根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的左子樹(shù)根結(jié)點(diǎn)*/bstree r_rotate(bstree p)bstnode *lc;/*聲明bstnode* 臨時(shí)變量*/lc=p-lchild;/*lc指向的*p的左子樹(shù)根結(jié)點(diǎn)*/p-lchild=lc-rchild;/*lc的右子樹(shù)掛接為*p的左子樹(shù)*/lc-rchild=p;p=lc;/*p指向
30、新的根結(jié)點(diǎn)*/return p;/*返回新的根結(jié)點(diǎn)*/*對(duì)以p為根的樹(shù)作左旋處理,處理之p指向新的樹(shù)根結(jié)點(diǎn)即旋轉(zhuǎn)處理之前的右子樹(shù)根結(jié)點(diǎn)*/bstree l_rotate(bstree p) bstnode *rc;/*聲明bstnode* 臨時(shí)變量*/rc=p-rchild;/*rc指向的*p的右子樹(shù)根結(jié)點(diǎn)*/p-rchild=rc-lchild;/*rc的左子樹(shù)掛接為*p的右子樹(shù)*/rc-lchild=p;p=rc;/*p指向新的根結(jié)點(diǎn)*/return p;/*返回新的根結(jié)點(diǎn)*/*對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree leftbal
31、ance(bstree t) bstnode *lc,*rd;lc=t-lchild;/*lc指向*t的左子樹(shù)根結(jié)點(diǎn)*/switch(lc-bf)/*檢查*t的左子樹(shù)平衡度,并做相應(yīng)的平衡處理*/case lh:/*新結(jié)點(diǎn)插入在*t的左孩子的左子樹(shù)上,要做單右旋處理*/t-bf=lc-bf=eh;t=r_rotate(t);break;case rh:/*新結(jié)點(diǎn)插入在*t的左孩子的右子樹(shù)上,要做雙旋處理*/rd=lc-rchild;/*rd指向*t的左孩子的右子樹(shù)根*/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);/*對(duì)*t的左孩子做左旋平衡處理*/t=r_rotate(t);/*對(duì)*t做右旋處理*/return t;/*對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針t指向新的根結(jié)點(diǎn)*/bstree rightbalance(bstree t) bstree rc,ld;rc=t-rchild;/*rc指向*t的右子樹(shù)根結(jié)點(diǎn)*/switch(rc-bf)/*檢查*t的右子樹(shù)平衡度,并做相應(yīng)的平衡處理
33、*/case rh:/*新結(jié)點(diǎn)插入在*t的右孩子的右子樹(shù)上,要做單右旋處理*/t-bf=rc-bf=eh;t=l_rotate(t);break;case lh:/*新結(jié)點(diǎn)插入在*t的右孩子的左子樹(shù)上,要做雙旋處理*/ld=rc-lchild;/*ld指向*t的右孩子的左子樹(shù)根*/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、*對(duì)*t的右孩子做右旋平衡處理*/t=l_rotate(t);/*對(duì)*t做左旋處理*/return t;/*若在平衡的二叉排序樹(shù)t中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn),則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn),并返回插入后所建成的平衡二叉排序樹(shù),否則返回null.若因插入而使二叉數(shù)失去平衡,則作平衡旋轉(zhuǎn)處理,布爾變量taller反映t長(zhǎng)高與否*/bstree insertavl(bstree t, int e) bstree p;/*插入新結(jié)點(diǎn),樹(shù)長(zhǎng)高置taller為true*/if(!t)t=(bstree)malloc(sizeof(bstnode);t-data=e;t-lchild=t-rchild=
35、null;t-bf=eh;taller=true;else/*樹(shù)中存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入*/if(e=t-data)taller=false;return null;/*值小于則繼續(xù)在樹(shù)的左子樹(shù)中搜索*/if(e data)p=insertavl(t-lchild,e); /*插入到左子樹(shù)且左子樹(shù)長(zhǎng)高*/if(p)t-lchild=p;if(taller)switch(t-bf)/*檢查*t的平衡度*/case lh:/*原本左子樹(shù)比右子樹(shù)高,需要做左平衡處理*/t=leftbalance(t);taller=false;break;case eh:/*原本左、右子樹(shù)同高,現(xiàn)因左
36、子樹(shù)爭(zhēng)高而使樹(shù)增高*/t-bf=lh;taller=true;break;case rh:/*原本右子樹(shù)比左子樹(shù)高,現(xiàn)在左右子樹(shù)等高*/t-bf=eh;taller=false;break;/*繼續(xù)在*t的右子樹(shù)中搜索*/else/*插入到右子樹(shù)且使右子樹(shù)長(zhǎng)高*/p=insertavl(t-rchild,e);if (p)t-rchild=p;if(taller)switch(t-bf)/*檢查*t的平衡度*/case lh:/*原本左子樹(shù)比右子樹(shù)高,現(xiàn)在左右子樹(shù)等高*/t-bf=eh;taller=false;break;case eh:/*原本左、右子樹(shù)同高,現(xiàn)因右子樹(shù)增高而使樹(shù)增高*/t
37、-bf=rh;taller=true;break;case rh:/*原本右子樹(shù)比左子樹(shù)高,需要做右平衡處理*/t=rightbalance(t);taller=false;break;return t;/*刪除結(jié)點(diǎn)時(shí)對(duì)以指針p所指結(jié)點(diǎn)為根的樹(shù)作左平衡旋轉(zhuǎn)處理,本算法結(jié)束時(shí)指針p指向新的根結(jié)點(diǎn)*/bstree leftbalance1(bstree p) bstree p1,p2;/*左子樹(shù)比右子樹(shù)高*/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í)對(duì)以指針t所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(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;/*對(duì)結(jié)點(diǎn)進(jìn)行刪除處理*/bstree delete(bstree q,
41、bstree r) if(r-rchild=null)/*根結(jié)點(diǎn)的右子樹(shù)為空則將左子樹(shù)提高并標(biāo)記樹(shù)變矮了*/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ù)對(duì)其進(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ù)在左子樹(shù)中搜索*/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ù)在右子樹(shù)中搜索*/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的右子樹(shù)為空則將其左子樹(shù)提高一層*/p
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 隔音墊施工方案
- 水利設(shè)施提升施工方案
- 路面硬化路肩首件施工方案
- 青海四合院庭院施工方案
- 地下室成品隔油池施工方案
- 晉中導(dǎo)向標(biāo)志牌施工方案
- 【市占率證明權(quán)威指南】摩托車(chē)行業(yè)市占率全解(智研咨詢(xún)發(fā)布)
- 排放源的治理技術(shù)選擇與應(yīng)用分析
- 綠色金融與低碳投資的策略及實(shí)施路徑
- 低空經(jīng)濟(jì)公司的經(jīng)營(yíng)策略
- 部編版道德與法治七年級(jí)下冊(cè)每課教學(xué)反思
- 自考14237《手機(jī)媒體概論》備考試題庫(kù)(含答案)
- 工會(huì)工作制度匯編
- LKJ2000型監(jiān)控裝置特殊情況下的操作課件講解
- 高考英語(yǔ)688高頻詞匯excel版
- 2024年黑龍江省行政職業(yè)能力測(cè)驗(yàn)題庫(kù)附解析答案
- QCT1170-2022汽車(chē)玻璃用功能膜
- HG/T 6312-2024 化工園區(qū)競(jìng)爭(zhēng)力評(píng)價(jià)導(dǎo)則(正式版)
- 《鐵路職業(yè)道德》課件-2.1鐵路職業(yè)道德的內(nèi)涵及規(guī)范
- 劇本寫(xiě)作教程03劇本結(jié)構(gòu)
- 語(yǔ)法大全之一般現(xiàn)在時(shí)動(dòng)詞三單變化練習(xí)題-(答案)
評(píng)論
0/150
提交評(píng)論