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

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

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

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

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

二叉樹的存儲方法順序存儲鏈式存儲節省結點的指針空間便于訪問孩子結點和雙親結點順序存儲的優點堆的基本操作向上調整將添加的新結點進行向上調整，直到調整的合適的位置滿足堆的性質向下調整基本操作【例】：堆（Heap）的插入——示意圖小根堆往小根堆中插入節點8小根堆第一次向上調整小根堆第二次向上調整小根堆第三次向上調整小根堆調整完成基本操