第10章 非線性結構

1、第十章第十章 非線性結構非線性結構 本章內(nèi)容（樹形結構）本章內(nèi)容（樹形結構） 樹的基本概念 二叉樹的基本概念和性質(zhì) 二叉樹的存儲結構 二叉樹的遍歷 樹、森林與二叉樹的轉(zhuǎn)換 哈夫曼樹 樹的基本概念樹的基本概念 1. 樹的特點樹的特點 2. 樹的定義樹的定義 樹樹是是n(n0)個數(shù)據(jù)元素的有限集合。它滿足以下兩個數(shù)據(jù)元素的有限集合。它滿足以下兩 個條件：個條件： 有且僅有一個特定的稱為根的元素；有且僅有一個特定的稱為根的元素； 其余元素分為（其余元素分為（ 0）個互不相交的有限集）個互不相交的有限集 合合1、2、，其中每個集合又都是一棵樹并、，其中每個集合又都是一棵樹并 稱其為根的稱其為根的子樹子

2、樹。 樹形結構是一類非常重要的樹形結構是一類非常重要的 非線性結構，適合于描述數(shù)據(jù)元非線性結構，適合于描述數(shù)據(jù)元 素之間的層次關系素之間的層次關系 樹的常用術語舉例樹的常用術語舉例 是的是的雙親雙親，是的，是的子女子女，是從到的，是從到的邊邊。 l 、互為、互為兄弟兄弟，而和不是兄弟，而和不是兄弟 。 l ADIN是從結點到結點的一條是從結點到結點的一條路徑路徑，其，其長度長度為為 。 層數(shù)層數(shù)為的結點有，為的結點有，層數(shù)層數(shù)為的結點有、為的結點有、 。 樹的深度樹的深度為為 。 、的、的度度數(shù)分別為、數(shù)分別為、0；樹的度數(shù)樹的度數(shù)為為 。 、都是、都是樹葉樹葉，其余結點都是，其余結點都是分支

3、結點分支結點 。 森 林 雙親、子女、邊雙親、子女、邊:若結點是結點若結點是結點 的一棵子樹的根，則稱做的一棵子樹的根，則稱做 的的“雙親雙親”; 稱做的稱做的“子女子女 ”； 有序?qū)ΓQ做從到有序?qū)?，稱做從到 的的“邊邊” 。 兄弟兄弟：具有同一雙親的結點具有同一雙親的結點 。 路徑、路徑長度路徑、路徑長度：若樹中存在若樹中存在 著一個結點的序列著一個結點的序列12j ，使，使ki是是ki+1（）的雙）的雙 親，則稱該結點序列為從親，則稱該結點序列為從k1到到kj 的一條路徑；的一條路徑；路徑長度路徑長度等于等于 -，它是該路徑所經(jīng)過的邊，它是該路徑所經(jīng)過的邊 的數(shù)目的數(shù)目 。 結點的層數(shù)結

4、點的層數(shù)：根結點層數(shù)為根結點層數(shù)為 ，其余結點層數(shù)等于其雙親結，其余結點層數(shù)等于其雙親結 點層數(shù)加點層數(shù)加 。 樹的深度（高度）樹的深度（高度）：即樹中層數(shù)即樹中層數(shù) 最大的結點的層數(shù)最大的結點的層數(shù) 。 結點的度數(shù)、樹的度數(shù)結點的度數(shù)、樹的度數(shù)：一個結一個結 點子女的個數(shù)稱為該結點的點子女的個數(shù)稱為該結點的“度度 數(shù)數(shù)”。 樹中度數(shù)最大的結點的度數(shù)叫做樹中度數(shù)最大的結點的度數(shù)叫做 “樹的度數(shù)樹的度數(shù)” 。 樹葉、分支結點樹葉、分支結點：度數(shù)為度數(shù)為0的結的結 點叫做點叫做“樹葉樹葉” ；度數(shù)大于；度數(shù)大于0的的 結點叫做結點叫做“分支結點分支結點”或或“內(nèi)內(nèi) 結點結點” 。 森林森林：（0）

5、棵互不相交）棵互不相交 的樹的集合稱為森林的樹的集合稱為森林 。 二叉樹的基本概念二叉樹的基本概念 二叉樹二叉樹是（是（0）個結點的有限集合。它或者是空集）個結點的有限集合。它或者是空集 （0），或者由一個根結點及兩棵互不相交的、分別稱為這），或者由一個根結點及兩棵互不相交的、分別稱為這 個根的左子樹和右子樹的二叉樹組成。個根的左子樹和右子樹的二叉樹組成。 1.二叉二叉樹的定義樹的定義 2. 二叉樹五種基本形態(tài)二叉樹五種基本形態(tài) 二叉樹可以是空，而樹不能為空。二叉樹可以是空，而樹不能為空。 二叉樹中任意結點的度數(shù)不超過二叉樹中任意結點的度數(shù)不超過2，而樹無此限制。，而樹無此限制。 二叉樹的子樹

6、有左、右之分，樹的子樹是相同的。二叉樹的子樹有左、右之分，樹的子樹是相同的。 3.樹和二叉樹的差別樹和二叉樹的差別 二叉樹的性質(zhì)二叉樹的性質(zhì) 性質(zhì)性質(zhì) 二叉樹第層上的結點數(shù)目最多為二叉樹第層上的結點數(shù)目最多為2i（ 0）。）。 性質(zhì)性質(zhì) 深度為的二叉樹至多有深度為的二叉樹至多有2k+1-1個結點（個結點（ 0）。）。 性質(zhì)性質(zhì) 在任意一棵二叉樹中，若終端結點的個數(shù)為在任意一棵二叉樹中，若終端結點的個數(shù)為n0、度數(shù)為的、度數(shù)為的 結結 點的個數(shù)為點的個數(shù)為n2，則，則n0=n2+1。 1. 二叉樹的性質(zhì)二叉樹的性質(zhì) 2. 兩種特殊的二叉樹兩種特殊的二叉樹 滿二叉樹滿二叉樹 完全二叉樹完全二叉樹

7、完全二叉樹性質(zhì)完全二叉樹性質(zhì) 性質(zhì)性質(zhì)4 具有個結點的完全二叉樹的深度為具有個結點的完全二叉樹的深度為 log2n 性質(zhì)性質(zhì)5 若對一棵有個結點的完全二叉樹，按自頂向下、同層由左到右順序依次若對一棵有個結點的完全二叉樹，按自頂向下、同層由左到右順序依次 為其每個結點從為其每個結點從0開始編號，則對編號為的結點開始編號，則對編號為的結點ki（0 n-1）則有：）則有： 若若 0，則，則ki雙親結點的編號為雙親結點的編號為 (i-1)/2 若若= 0，則，則ki是根結點。是根結點。 若若2i+1n，則，則ki左子女結點的編號是左子女結點的編號是2i+1，否則，否則ki無左子女。無左子女。 若若2i

8、+2n，則，則ki右子女結點的編號為右子女結點的編號為2i+2，否則，否則ki無右子女。無右子女。 二叉樹的存儲結構二叉樹的存儲結構 對完全二叉樹，利用性質(zhì)對完全二叉樹，利用性質(zhì)5，將其所有結點按編號順序依次存儲在一維數(shù)組里。，將其所有結點按編號順序依次存儲在一維數(shù)組里。 對一般二叉樹，需要加上一些并不存在的對一般二叉樹，需要加上一些并不存在的“虛結點虛結點”，轉(zhuǎn)換為完全二叉樹的形式，轉(zhuǎn)換為完全二叉樹的形式 。 1. 順序存儲結構順序存儲結構 完全二叉樹完全二叉樹 一般的二叉樹一般的二叉樹 二叉樹的存儲結構二叉樹的存儲結構 2. 鏈式存儲結構鏈式存儲結構 鏈式存儲時結點的結構鏈式存儲時結點的結

9、構 二叉樹的遍歷二叉樹的遍歷 先序遍歷先序遍歷 若二叉樹非空，訪問根結點，先序遍歷左子樹，先序遍歷右子樹若二叉樹非空，訪問根結點，先序遍歷左子樹，先序遍歷右子樹 中序遍歷中序遍歷 若二叉樹非空，中序遍歷左子樹，訪問根結點，中序遍歷右子樹若二叉樹非空，中序遍歷左子樹，訪問根結點，中序遍歷右子樹 后序遍歷后序遍歷 若二叉樹非空，后序遍歷左子樹，后序遍歷右子樹，訪問根結點若二叉樹非空，后序遍歷左子樹，后序遍歷右子樹，訪問根結點 層次遍歷層次遍歷 按層數(shù)由小到大、同一層從左到右順序依次訪問二叉樹的各個結點按層數(shù)由小到大、同一層從左到右順序依次訪問二叉樹的各個結點 先序訪問序列先序訪問序列 ： 中序訪問

10、序列中序訪問序列 ： 后序訪問序列后序訪問序列 ： 層次訪問序列層次訪問序列 ： GDEBFCA ABDGECF DGBEAFC ABCDEFG 如何根據(jù)遍歷序列得到一顆二叉樹？如何根據(jù)遍歷序列得到一顆二叉樹？ n由先序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài)由先序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài) n由后序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài)由后序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài) n由層序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài)由層序遍歷和中序遍歷序列，可以得出該二叉樹的形態(tài) n其他情況下，其他情況下，不能不能得出該二叉樹的形態(tài)。如，由先序遍歷和得出該二叉樹的形態(tài)

11、。如，由先序遍歷和 后序遍歷序列，后序遍歷序列，不能不能得出該二叉樹的形態(tài)得出該二叉樹的形態(tài) 先序遍歷序列：先序遍歷序列： 中序遍歷序列：中序遍歷序列： ABDGECF DGBEAFC 例：例： 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 將樹轉(zhuǎn)換成二叉樹將樹轉(zhuǎn)換成二叉樹： 在所有的兄弟之間加一條連線；在所有的兄弟之間加一條連線； 對每個結點，除了保留與最左邊子女的連線外，去掉與其他對每個結點，除了保留與最左邊子女的連線外，去掉與其他 子女連線；子女連線； 將保留下來的邊作為左子樹的邊，兄弟間的連線作為右子樹將保留下來的邊作為左子樹的邊，兄弟間的連線作為右子樹 的邊。的邊。 樹、森林到二叉樹

12、的轉(zhuǎn)換樹、森林到二叉樹的轉(zhuǎn)換 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 將一個森林轉(zhuǎn)換成二叉樹：將一個森林轉(zhuǎn)換成二叉樹： 先將森林中的每一棵樹變?yōu)槎鏄洌缓髮⒏鞫鏄涞母Y先將森林中的每一棵樹變?yōu)槎鏄?，然后將各二叉樹的根結 點看成兄弟，用線把它們連到一起，經(jīng)整理后可得到相應的二點看成兄弟，用線把它們連到一起，經(jīng)整理后可得到相應的二 叉樹。叉樹。 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 （續(xù)）（續(xù)） 若結點是其雙親的左子女，則把的右子女、右子女的若結點是其雙親的左子女，則把的右子女、右子女的 右子女右子女都與連線，最后去掉所有雙親到右子女的連線。都與連線，最后去掉所有雙親到右子女的

13、連線。 二叉樹到樹、森林的轉(zhuǎn)換二叉樹到樹、森林的轉(zhuǎn)換 哈夫曼樹基本概念哈夫曼樹基本概念 擴充二叉樹的定義：擴充二叉樹的定義： 假設假設W0，W1，Wn-1是個實數(shù)的集合，是個實數(shù)的集合， 其中其中Wi0（0-）。若是一棵有個葉結點）。若是一棵有個葉結點 的二叉樹，而且將的二叉樹，而且將W0，W1，Wn-1分別賦給的分別賦給的 個葉結點作為它們的權，則稱是權值為個葉結點作為它們的權，則稱是權值為W0，W1， ，Wn-1的的擴充二叉樹擴充二叉樹。帶有權值的葉結點叫做擴充二叉。帶有權值的葉結點叫做擴充二叉 樹的樹的外結點外結點，其余的分支結點叫做，其余的分支結點叫做內(nèi)結點內(nèi)結點。 哈夫曼樹基本概念哈

14、夫曼樹基本概念 例如：權值集合例如：權值集合2，4，6，8，則可構造出以下擴充，則可構造出以下擴充 二叉樹。二叉樹。 哈夫曼樹基本概念哈夫曼樹基本概念 WPL= 其中，為外結點數(shù)，其中，為外結點數(shù)，Wi為外結點所帶的權值；為外結點所帶的權值；li為為 從根結點到外結點的路徑長度。從根結點到外結點的路徑長度。 i n i l 1 0 i W (a) WPL=40 (b) WPL=50(c) WPL=38 2擴充二叉樹的帶權路徑長度擴充二叉樹的帶權路徑長度（）（） 哈夫曼樹基本概念哈夫曼樹基本概念 （續(xù)）（續(xù)） 3最優(yōu)二叉樹最優(yōu)二叉樹 通常，把權值取為通常，把權值取為W0，W1，Wn-1的所有擴的

15、所有擴 充二叉樹中為最小的擴充二叉樹稱為充二叉樹中為最小的擴充二叉樹稱為最優(yōu)二叉樹最優(yōu)二叉樹。 4哈夫曼樹哈夫曼樹 利用哈夫曼提出的方法構造出的最優(yōu)二叉樹稱為利用哈夫曼提出的方法構造出的最優(yōu)二叉樹稱為哈夫哈夫 曼樹曼樹。 哈夫曼樹基本概念哈夫曼樹基本概念 （續(xù)）（續(xù)） 5哈夫曼樹構造方法哈夫曼樹構造方法 由給定的個權值由給定的個權值W0，W1，Wn-1構造含有棵構造含有棵 擴充二叉樹的森林，森林中的每棵二叉樹都只有一個根結擴充二叉樹的森林，森林中的每棵二叉樹都只有一個根結 點，且每個根結點都取一個各不相同的點，且每個根結點都取一個各不相同的Wi作為權值；作為權值； 用森林中根結點的權值為最小和

16、次小的兩棵二叉樹作為用森林中根結點的權值為最小和次小的兩棵二叉樹作為 左、右子樹構造出一棵新的二叉樹，并將新二叉樹的根結點左、右子樹構造出一棵新的二叉樹，并將新二叉樹的根結點 的權值取為左、右子樹根結點權值之和；的權值取為左、右子樹根結點權值之和； 從森林中刪去作為新二叉樹左、右子樹的兩棵二叉樹，從森林中刪去作為新二叉樹左、右子樹的兩棵二叉樹， 將新構造的二叉樹加入到森林中；將新構造的二叉樹加入到森林中； 重復步驟重復步驟和和，直到中僅剩下一棵二叉樹為止。，直到中僅剩下一棵二叉樹為止。 哈夫曼樹的構造哈夫曼樹的構造 問題問題 ASCII編碼是等長編碼編碼是等長編碼 如果字符X不常用，為什么還用

17、同樣的長 度對它進行編碼呢？ 如：如： a：01000001 b： 01000010 Huffman Huffman編碼就是一種可變長度的編碼，廣泛廣泛 用于各種數(shù)據(jù)壓縮技術中。用于各種數(shù)據(jù)壓縮技術中。 哈夫曼樹的應用哈夫曼樹的應用 哈夫曼編碼哈夫曼編碼 例例 設電文字符集為設電文字符集為 a，b，c，d，e，f ，各字符發(fā)送頻率是，各字符發(fā)送頻率是 6，2，3，3，4，9 ，要求用，要求用0、1為各個字符進行編碼，使報為各個字符進行編碼，使報 文總長度最短。文總長度最短。 各字符的哈夫曼編碼是各字符的哈夫曼編碼是 a：01 b：000 c：001 d：100 e：101 f：11 以字符發(fā)送頻率為權值構造哈夫曼樹以字符發(fā)送頻率為權值構造哈夫曼樹 哈夫曼哈夫曼編碼的特點編碼的特點 霍夫曼編碼的思想是，對于出現(xiàn)頻率高的字符，霍夫曼編碼