二叉樹論文 二叉樹的應(yīng)用

《二叉樹論文 二叉樹的應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、本科畢業(yè)論文（設(shè)計(jì)）模板2013年度本科實(shí)踐論文實(shí)踐題目：二叉樹的應(yīng)用學(xué)生姓名：杜鑫學(xué)號：1105290124專業(yè)：軟件工程班級：軟件工程1101完成日期：2013年08月25日-12-序言在計(jì)算機(jī)科學(xué)中，樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)。二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的有序樹。通常子樹被稱作“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。值得注意的是，二叉樹不是樹的特殊情形。在圖論中，二叉樹是一個連通的無環(huán)圖，并且每一個頂點(diǎn)的度

2、不大于3。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)后，每個頂點(diǎn)定義了唯一的根結(jié)點(diǎn)，和最多2個子結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中二叉樹的應(yīng)用有著很重要的作用，對解決很多程序問題都有很大幫助，因此，我們更應(yīng)該深入的學(xué)習(xí)和了解二叉樹的應(yīng)用，為以后更方便的解決計(jì)算機(jī)的相關(guān)問題做鋪墊。只有詳細(xì)學(xué)習(xí)二叉樹，了解二叉樹的具體應(yīng)用范圍、方法以及針對性，才能很好地完成任務(wù)，解決問題。-12-內(nèi)容摘要本實(shí)踐論文主要包含以下幾個方面：二叉樹的定義，二叉樹的特點(diǎn)，二叉樹的存儲結(jié)構(gòu)，二叉樹的排序、查找、插入、刪除，平衡二叉樹，二叉樹的遍歷，二叉樹的相關(guān)應(yīng)用等內(nèi)容。由淺入深的介紹了二叉樹的主要

3、內(nèi)容和結(jié)構(gòu)特性、操作實(shí)現(xiàn)，同時介紹了線索二叉樹和哈夫曼樹的基本情況。最后簡短的引用兩個二叉樹應(yīng)用的源程序例子來說明二叉樹的具體使用。二叉樹結(jié)構(gòu)的應(yīng)用非常廣泛，特別是在大量數(shù)據(jù)處理方面，如在文件系統(tǒng)、編譯系統(tǒng)、目錄組織等方面顯得更加突出。存儲結(jié)構(gòu)的不同，二叉樹實(shí)現(xiàn)的操作也不同。其中，二叉樹的遍歷運(yùn)算時一個重要的基礎(chǔ)，對訪問根結(jié)點(diǎn)操作的理解可包括多種操作。關(guān)鍵詞：二叉樹二叉樹特性二叉樹存儲結(jié)構(gòu)二叉樹遍歷、拓展哈夫曼樹-12-目錄一、二叉樹的基本內(nèi)容-4-（一）二叉樹-4-（二）二叉樹的存儲結(jié)構(gòu)-4-（三）二叉樹的遍歷-5-錯誤！未找到索引項(xiàng)。二、二叉樹的應(yīng)用-5

4、-（一）二叉排序樹-5-（二）二叉排序樹查找-6-（三）二叉排序樹插入結(jié)點(diǎn)的算法-6-（四）二叉排序樹刪除結(jié)點(diǎn)的算法-6-（五）平衡二叉樹-6-（六）判定樹-7-（七）二分查找判定樹的查找-7-（八）線索二叉樹-7-一、哈夫曼樹-10-（一）哈夫曼樹的構(gòu)造算法-10-參考文獻(xiàn)-12--12-一、二叉樹的基本內(nèi)容（一）二叉樹二叉樹很像一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把數(shù)據(jù)聯(lián)系起來，這種數(shù)據(jù)結(jié)構(gòu)就叫做樹結(jié)構(gòu)，簡稱樹。樹中每個分叉點(diǎn)稱為結(jié)點(diǎn)，起始結(jié)點(diǎn)稱為樹根，任意兩個結(jié)點(diǎn)間的連接關(guān)系稱為樹枝，結(jié)點(diǎn)下面不再有分枝稱為樹葉。結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的"

5、雙親"，結(jié)點(diǎn)的后趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的"子女"或"孩子"，同一結(jié)點(diǎn)的"子女"之間互稱"兄弟"。二叉樹也是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分：(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第h層外，其它各層(1～h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。(2)滿二叉樹——除了葉結(jié)點(diǎn)外每一個結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。(3)深度——二叉樹的層數(shù)，就是高度。（二）二叉樹的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)（適合完全二叉樹和滿二叉樹）（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)（適合非完全二叉樹）（三）二叉樹的遍歷（1）遞歸遍歷

6、（中序遍歷、先序遍歷、后序遍歷）（2）非遞歸遍歷（利用堆棧實(shí)現(xiàn)）（四）二叉樹的拓展（1）線索二叉樹——（在節(jié)點(diǎn)空指針域存放前驅(qū)和后繼節(jié)點(diǎn)的指針，加上線索標(biāo)志域區(qū)分是線索指針還是child指針；建立線索二叉樹，實(shí)質(zhì)上就是遍歷一顆二叉樹，在相應(yīng)的指針域進(jìn)行操作）（2）二叉排序樹——（可以了解到二叉樹生成的過程）-12-（3）最優(yōu)二叉樹——（哈夫曼樹）：對于一組有確定權(quán)值的葉子節(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹（典型應(yīng)用：哈夫曼編碼）（4）平衡樹——它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。（防止退化為鏈表，

7、提高搜索效率）（5）排序樹——特點(diǎn)：所有結(jié)點(diǎn)“左小右大（6）字典樹——由字符串構(gòu)成的二叉排序樹（7）判定樹——特點(diǎn)：分支查找樹（例如12個球如何只稱3次便分出輕重）（8）帶權(quán)樹——特點(diǎn)：路徑帶權(quán)值（例如長度）二、二叉樹的應(yīng)用（一）二叉排序樹或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：?（1）若左子樹不為空，左子樹的所有結(jié)點(diǎn)的值均小于根的值；?（2）若右子樹不為空，右子樹的所有結(jié)點(diǎn)均大于根的值；?（3）它的左右子樹也分別為二叉排序樹。（二）二叉排序樹查找在二叉排序樹b中查找x的過程為：若b是空樹，則搜索失敗，否則：若x等于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；

8、否則：若x小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹；