《小白學(xué)數(shù)據(jù)結(jié)構(gòu)》課件-第五章 樹

主講教師：1.樹與二叉樹什么是樹呢？樹樹的定義樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛洌╪=0）；或?yàn)榉强諛?，?duì)于非空樹T：(1)有且僅有一個(gè)稱之為根結(jié)點(diǎn)；(2)除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為m（m＞0）個(gè)互不相交的有限集T1,T2,...,Tm,其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree）。樹樹的基本術(shù)語（1）結(jié)點(diǎn)的度（2）樹的度（4）分支結(jié)點(diǎn)（3）葉子結(jié)點(diǎn)樹中結(jié)點(diǎn)擁有子樹的數(shù)量稱為結(jié)點(diǎn)的度樹中所有結(jié)點(diǎn)度的最大值稱為樹的度樹中度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)樹中度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)ABCDEFGH4B02D01FGHB、D、F、G、H五個(gè)結(jié)點(diǎn)——葉子結(jié)點(diǎn)ACEA、C、E三個(gè)結(jié)點(diǎn)——分支結(jié)點(diǎn)二叉樹二叉樹的五種基本形態(tài)(a)——空二叉樹(b)——僅有根結(jié)點(diǎn)的二叉樹(c)——右子樹為空的二叉樹(d)——左子樹為空的二叉樹(e)——左右子樹非空的二叉樹二叉樹的兩個(gè)基本特點(diǎn)（1）結(jié)點(diǎn)的度小于等于2（2）二叉樹是有序樹，左右子樹不能顛倒樹與二叉樹ABCDEGHF二叉樹ABCDEFGH樹一般的樹可以有多個(gè)子結(jié)點(diǎn)，而二叉樹每一個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)。二叉樹的結(jié)點(diǎn)是有順序的，分為左子樹和右子樹，一般的樹中結(jié)點(diǎn)的順序是無關(guān)的。(1)滿二叉樹

滿二叉樹第一層第二層第三層第四層137152456891011121314(2)完全二叉樹定義：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。深度——4結(jié)點(diǎn)——12個(gè)完全二叉樹滿二叉樹和完全二叉樹有什么區(qū)別？滿二叉樹和完全二叉樹滿二叉樹是完全二叉樹的一種特例，所以滿二叉樹也是完全二叉樹，但完全二叉樹不一定都是滿二叉樹。123456789101112131415123456789101112滿二叉樹/完全二叉樹完全二叉樹2.二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹的性質(zhì)性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)第一層第二層第三層第四層24835679101112131415二叉樹的性質(zhì)性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)深度42k-1=24-1=16-1=15至多有15個(gè)結(jié)點(diǎn)二叉樹的性質(zhì)性質(zhì)3:對(duì)于任何一棵二叉樹，若度為2的結(jié)點(diǎn)數(shù)有n2個(gè)，

則葉子數(shù)n0必定為n2＋1（即n0=n2+1）二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)二叉樹的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元，以層次的順序存放二叉樹的數(shù)據(jù)元素，結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含了結(jié)點(diǎn)之間的關(guān)系。二叉樹的存儲(chǔ)結(jié)構(gòu)(2)鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)的存儲(chǔ)效率不高有大量的空間浪費(fèi)很多存儲(chǔ)單元并沒有存儲(chǔ)數(shù)據(jù)鏈?zhǔn)酱鎯?chǔ)二叉樹的存儲(chǔ)結(jié)構(gòu)(2)鏈?zhǔn)酱鎯?chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)至少包含三個(gè)域：①數(shù)據(jù)域②左指針域（左孩子域）③右指針域（右孩子域）數(shù)據(jù)域左指針域右指針域3.二叉樹的遍歷二叉樹的遍歷指從根結(jié)點(diǎn)出發(fā)，順著某一條搜索路徑訪問二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)的均被訪問一次，而且僅被訪問一次。二叉樹的遍歷先序遍歷后序遍歷中序遍歷層序遍歷二叉樹的遍歷①先序遍歷如果二叉樹為空，那么我們就不訪問，否則我們?cè)L問根結(jié)點(diǎn)然后我們先序遍歷左子樹。左子樹遍歷完后，我們?cè)偃ハ刃虮闅v右子樹，按照根左右的順序。這顆二叉樹的先序遍歷的序列是：A-B-C-D-E-F-G-H二叉樹的遍歷②后序遍歷后序遍歷按照左右根的順序。先遞歸后序遍歷的左子樹，然后再訪問它的右子樹，最后訪問根結(jié)點(diǎn)。這顆二叉樹的后序遍歷的序列是：D-E-C-B-H-G-F-A二叉樹的遍歷③中序遍歷中序遍歷算法按照左根右的順序這顆二叉樹的中序遍歷的序列是：B-D-C-E-A-F-H-G二叉樹的遍歷④層序遍歷按層從上到下，每層按一定順序?qū)涞慕Y(jié)點(diǎn)進(jìn)行遍歷，一般情況下，每一層按照自左至右的順序訪問。這顆二叉樹的層序遍歷的序列是：A-B-F-C-G-D-E-H4.樹、森林與二叉樹的轉(zhuǎn)換一棵樹：無最大子結(jié)點(diǎn)數(shù)量限制二叉樹：最大子結(jié)點(diǎn)數(shù)量為2樹與二叉樹結(jié)構(gòu)的不同樹與二叉樹的轉(zhuǎn)換方法使用鏈表存儲(chǔ)所有樹的結(jié)點(diǎn)，然后在鏈表中進(jìn)行組織層序遍歷對(duì)樹中的每個(gè)結(jié)點(diǎn)進(jìn)行遞歸，逐步轉(zhuǎn)換為二叉樹遞歸樹與二叉樹的轉(zhuǎn)換方法特定結(jié)構(gòu)轉(zhuǎn)換的目的CAB樹與二叉樹的轉(zhuǎn)換方法CDEFGHIAB加線操作：連接樹中所有相鄰兄弟去線操作：刪除其他多余連線旋轉(zhuǎn)操作：將整棵樹順時(shí)針旋轉(zhuǎn)45°一棵樹轉(zhuǎn)換為二叉樹樹與二叉樹的轉(zhuǎn)換方法CDEFGHIAB一棵樹轉(zhuǎn)換為二叉樹加線操作：連接樹中所有相鄰兄弟去線操作：刪除其他多余連線旋轉(zhuǎn)操作：將整棵樹順時(shí)針旋轉(zhuǎn)45°森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換將樹中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹01從第二棵二叉樹始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子02將重新組織后的二叉樹返回作為結(jié)果03步驟可能需要修改森林與二叉樹的轉(zhuǎn)換練習(xí)：將下圖所示的森林轉(zhuǎn)換為二叉樹先將森林中的每棵樹轉(zhuǎn)換為二叉樹選中軸心，將樹順時(shí)針旋轉(zhuǎn)45°ABCDEFGHIKLNMOJ森林與二叉樹的轉(zhuǎn)換ABCDEFGHIKLNMOJ練習(xí)：將下圖所示的森林轉(zhuǎn)換為二叉樹先將森林中的每棵樹轉(zhuǎn)換為二叉樹選中軸心，將樹順時(shí)針旋轉(zhuǎn)45°將二叉樹依次連接起來森林與二叉樹的轉(zhuǎn)換練習(xí)：將下圖所示的森林轉(zhuǎn)換為二叉樹先將森林中的每棵樹轉(zhuǎn)換為二叉樹選中軸心，將樹順時(shí)針旋轉(zhuǎn)45°將二叉樹依次連接起來ABCDEFGHIKLNMOJ5.哈夫曼樹用于數(shù)據(jù)壓縮哈夫曼樹的定義acbd將頻率高的數(shù)據(jù)項(xiàng)分配的編碼長度更短有效的減少了編碼后數(shù)據(jù)的長度哈夫曼樹的優(yōu)點(diǎn)哈夫曼樹基本術(shù)語acbd5724哈夫曼樹的定義哈夫曼樹又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹。路徑長度：

在二叉樹中結(jié)點(diǎn)到根結(jié)點(diǎn)路徑的邊數(shù)。帶權(quán)路徑長度權(quán)值×路徑長度=樹的帶權(quán)路徑長度：所有結(jié)點(diǎn)的帶權(quán)路徑長度之和，記作WPL。例題計(jì)算cdab4257acbd5724adbc5724例：計(jì)算下圖二叉樹的WPL例題計(jì)算cdab4257WPL=4×2例：計(jì)算下圖二叉樹的WPL+7×3+5×3+2×1=46例題計(jì)算cdabacbd5724WPL=4×2+7×3+5×3+2×1=46WPL=7×2例：計(jì)算下圖二叉樹的WPL5724+5×2+2×2+4×2=36例題計(jì)算acbd5724adbc5724WPL=7×2+5×2+2×2+4×2=36WPL=35？例：計(jì)算下圖二叉樹的WPLcdab5724WPL=4×2+7×3+5×3+2×1=46哈夫曼樹的概念根據(jù)一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹，其中帶權(quán)路徑長度最小的二叉樹就是哈夫曼樹。構(gòu)建方法哈夫曼樹的構(gòu)建方法一、創(chuàng)建一個(gè)空的哈夫曼樹，然后將所有的葉子結(jié)點(diǎn)的權(quán)值存儲(chǔ)在一個(gè)有序的隊(duì)列中。二、選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)，合并成一個(gè)新的二叉樹，并將根結(jié)點(diǎn)權(quán)值設(shè)為兩個(gè)結(jié)點(diǎn)權(quán)值之和。三、將加入隊(duì)列中，重復(fù)步驟二，直到隊(duì)列中只剩下一個(gè)結(jié)點(diǎn)為止。這個(gè)結(jié)點(diǎn)即為哈夫曼樹的根結(jié)點(diǎn)。哈夫曼樹的構(gòu)建方法例：W={5，29，7，8，14，23，3，11}53111429782371114298823141529811231519291423………….哈夫曼樹的構(gòu)建方法81553871001119142923295842有效地利用數(shù)據(jù)的頻率信息使得編碼后的數(shù)據(jù)更加緊湊哈夫曼樹的優(yōu)勢(shì)頻繁出現(xiàn)不常出現(xiàn)短編碼長編碼可以使用更少的比特表示相同的數(shù)據(jù)對(duì)編碼數(shù)據(jù)的頻率信息進(jìn)行分析將這些信息表示為二叉樹根據(jù)樹的構(gòu)造方法對(duì)各個(gè)葉子結(jié)點(diǎn)分配編碼哈夫曼編碼哈夫曼編碼的生成應(yīng)用文件壓縮圖像壓縮音頻壓縮6.堆（heap）樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)樹通常用于表示層次關(guān)系樹的定義

堆的定義二叉堆具有最大堆性質(zhì)和最小堆性質(zhì)堆中結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值堆1023172631644835455964594845313517231026最大堆10483145352317645926最小堆45173126643548102359堆具有樹的遞歸性質(zhì)，還具有額外的最大堆/最小堆的性質(zhì)堆45173126643548102359堆完全二叉樹堆是一顆完全二叉樹，可以用二叉樹的存儲(chǔ)方式來表示堆

二叉樹的存儲(chǔ)方法順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)節(jié)省結(jié)點(diǎn)的指針空間便于訪問孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)順序存儲(chǔ)的優(yōu)點(diǎn)堆的基本操作向上調(diào)整將添加的新結(jié)點(diǎn)進(jìn)行向上調(diào)整，直到調(diào)整的合適的位置滿足堆的性質(zhì)向下調(diào)整基本操作【例】：堆（Heap）的插入——示意圖小根堆往小根堆中插入節(jié)點(diǎn)8小根堆第一次向上調(diào)整小根堆第二次向上調(diào)整小根堆第三次向上調(diào)整小根堆調(diào)整完成基本操