第6章樹和二叉樹

1、 本章中主要介紹下列內(nèi)容：本章中主要介紹下列內(nèi)容： l 樹的定義樹的定義 l 二叉樹的定義、存儲結(jié)構(gòu)二叉樹的定義、存儲結(jié)構(gòu) l 二叉樹的遍歷二叉樹的遍歷 l 樹和二叉樹的轉(zhuǎn)換樹和二叉樹的轉(zhuǎn)換 l 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 6.1 6.1 樹的定義樹的定義 一、一、 定義定義 樹樹: n個結(jié)點(diǎn)的有限集合（個結(jié)點(diǎn)的有限集合（n0） 。 n=0，空樹空樹； n0 有且僅有一個結(jié)點(diǎn)被稱為有且僅有一個結(jié)點(diǎn)被稱為根根（無前驅(qū)） 其余結(jié)點(diǎn)被分為其余結(jié)點(diǎn)被分為m（m 0）個互不相交的）個互不相交的 子集子集T1、T2、Tm，其中每個子集又是一棵樹，其中每個子集又是一棵樹,并并 稱為根的稱為根的子樹子樹

2、。 AE F G H I J K L M B C D A (a) (b)(c) E F G H I J K L M B C D A 二、樹的表示二、樹的表示 1、樹形表示法、樹形表示法 2、文氏圖表示法、文氏圖表示法 （嵌套集合表示法）（嵌套集合表示法） 3、凹入表示法、凹入表示法 4、廣義表表示法、廣義表表示法 （嵌套括號表示法）（嵌套括號表示法） 結(jié)點(diǎn)的結(jié)點(diǎn)的度度 樹的度樹的度 終端結(jié)點(diǎn)（終端結(jié)點(diǎn)（葉子葉子） 非終端結(jié)點(diǎn)非終端結(jié)點(diǎn) 孩子孩子結(jié)點(diǎn)結(jié)點(diǎn) 雙親雙親結(jié)點(diǎn)結(jié)點(diǎn) 子孫子孫結(jié)點(diǎn)結(jié)點(diǎn) 祖先祖先結(jié)點(diǎn)結(jié)點(diǎn) 結(jié)點(diǎn)的結(jié)點(diǎn)的層次層次 堂兄弟堂兄弟 樹的樹的深度深度（高度高度） 有序樹有序樹、無序樹無

3、序樹 如果樹中每棵子樹從左向右的排列擁有 一定的順序，不得互換，則稱為有序樹，否則稱為無 序樹。 森林森林 是是m（m0）棵互不相交的樹的集合。）棵互不相交的樹的集合。 E F G H I J K L M B C D A 三、基本術(shù)語三、基本術(shù)語 一、一、 定義定義 （1）每個結(jié)點(diǎn)最多有兩棵子樹（度）每個結(jié)點(diǎn)最多有兩棵子樹（度2） （2）子樹有左右之分。）子樹有左右之分。 二叉樹的二叉樹的5種形態(tài)：種形態(tài)： (b)(c) (d) (e) (a) 【性質(zhì)性質(zhì)1】 在二叉樹的在二叉樹的第第i層層上，最多有上，最多有2i-1個結(jié)點(diǎn)個結(jié)點(diǎn) （i1）。）。 i=1i=1時，時，2 2i-1 i-1=2

4、=21-1 1-1=2 =20 0=1 =1 成立。成立。 假設(shè)第假設(shè)第i-1i-1層上最多有層上最多有2 2i-2 i-2個結(jié)點(diǎn)。 個結(jié)點(diǎn)。 那么第那么第i i層最多有層最多有2 2i-2 i-2* *2=2 2=2i-1 i-1個結(jié)點(diǎn)。 個結(jié)點(diǎn)。 所以命題成立。所以命題成立。 二、二、 性質(zhì)性質(zhì) 由性質(zhì)由性質(zhì)1 1可以得出，可以得出，1 1至至K K層各層最多的結(jié)點(diǎn)個數(shù)分別為：層各層最多的結(jié)點(diǎn)個數(shù)分別為： 2 20 0,2,21 1,2,22 2,2,23 3,.,2,.,2K-1 K-1。這是一個以 。這是一個以2 2為比值的等比數(shù)列，前為比值的等比數(shù)列，前 n n項(xiàng)之和的計算公式為：項(xiàng)

5、之和的計算公式為： q qaa S n n 1 *1 其中其中 a1a1為第一項(xiàng)，為第一項(xiàng)，anan為第為第n n項(xiàng)，項(xiàng)，q q為比值?？梢缘脼楸戎怠？梢缘?到，該數(shù)列前到，該數(shù)列前K K項(xiàng)之和為：項(xiàng)之和為： 12 21 2* 1 2 0 2 K K 【性質(zhì)性質(zhì)2】 深度為深度為K的二叉樹最多有的二叉樹最多有2K-1個結(jié)點(diǎn)（個結(jié)點(diǎn)（K1）。）。 滿二叉樹滿二叉樹：深度為深度為K K，且有，且有2 2K K-1-1個結(jié)點(diǎn)。個結(jié)點(diǎn)。 完全二叉樹完全二叉樹：除最后一層外，其余層都是滿的，最后除最后一層外，其余層都是滿的，最后 一層或滿或在右邊缺少連續(xù)若干個結(jié)點(diǎn)。一層或滿或在右邊缺少連續(xù)若干個結(jié)點(diǎn)。

6、8 9 10 11 12 13 14 15 4 5 6 7 2 3 1 8 9 10 4 5 6 7 2 3 1 8 9 10 11 12 4 5 6 7 2 3 1 【性質(zhì)【性質(zhì)3 3】 具有具有n n個結(jié)點(diǎn)的完全二叉樹的深度為個結(jié)點(diǎn)的完全二叉樹的深度為 loglog2 2n n +1+1。 證明：假設(shè)其深度為證明：假設(shè)其深度為K K，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2 2可以得出：可以得出： 2 2K-1 K-1-1n2 -1n2K K-1-1 將不等式兩端加將不等式兩端加1 1得：得： 2 2K-1 K-1n2 n2K K 將不等式中的三項(xiàng)同取以將不等式中的三項(xiàng)同取以2 2為底的對數(shù)得到：為底的對

7、數(shù)得到： K-1logK-1log2 2n Kn K 整理后得到：整理后得到：loglog2 2n Klogn 1i1，其，其雙親結(jié)點(diǎn)為雙親結(jié)點(diǎn)為 i/2i/2 。 （2 2）如）如 2in2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i沒有左孩子；否則其沒有左孩子；否則其左孩子為左孩子為2i2i。 （3 3）如果）如果2i+1n2i+1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i沒有右孩子；否則其沒有右孩子；否則其右孩子為右孩子為 2i+12i+1。 【性質(zhì)性質(zhì)5】 對于任對于任 一棵二叉樹，如果葉子結(jié)點(diǎn)一棵二叉樹，如果葉子結(jié)點(diǎn) 數(shù)為數(shù)為n0，度，度 為為2的結(jié)點(diǎn)的結(jié)點(diǎn) 數(shù)為數(shù)為n2，則，則n0=n2+1。 證明：假設(shè)度為證明：假

8、設(shè)度為1 1的結(jié)點(diǎn)個數(shù)為的結(jié)點(diǎn)個數(shù)為n n1 1 則結(jié)點(diǎn)總數(shù)則結(jié)點(diǎn)總數(shù)n=nn=n0 0+n+n1 1+n+n2 2 （1 1） 總的分支數(shù)為總的分支數(shù)為n-1n-1 分支都是由度為分支都是由度為1 1或度為或度為2 2的結(jié)點(diǎn)發(fā)出的，的結(jié)點(diǎn)發(fā)出的， 故：故：n-1=nn-1=n1 1+2n+2n2 2 （2 2） 由（由（1 1）、（）、（2 2）式得到：）式得到：n n0 0=n=n2 2+1+1。 1.1. 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 適用于完全二叉樹適用于完全二叉樹 存儲形式為：以編號為地址存儲。編號為存儲形式為：以編號為地址存儲。編號為i的結(jié)點(diǎn)存入的結(jié)點(diǎn)存入 一維數(shù)組的第一維數(shù)組的第i個

9、分量中。個分量中。 D E F G B C H A 0 1 2 3 4 5 6 7 A B C D E F G H 三、存儲結(jié)構(gòu)三、存儲結(jié)構(gòu) 對于非完全二叉樹，需要將空缺的位置用特定的符號填補(bǔ)。對于非完全二叉樹，需要將空缺的位置用特定的符號填補(bǔ)。 若空缺結(jié)點(diǎn)較多，將造成空間利用率的下降。若空缺結(jié)點(diǎn)較多，將造成空間利用率的下降。 D G B C H A 0 1 2 3 4 5 6 7 A B C D G H 二叉鏈表二叉鏈表 結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： lchild data rchild 其中，其中，lchild和和rchild是分別指向該結(jié)點(diǎn)左孩是分別指向該結(jié)點(diǎn)左孩 子和右孩子的指針，子和右孩子的

10、指針，data是數(shù)據(jù)元素的內(nèi)容。是數(shù)據(jù)元素的內(nèi)容。 2.2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 三叉鏈表三叉鏈表 lchild data parent rchild 結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： P127 圖圖6.8 G H D E F B C A T D E F B C G H A 二叉鏈表的類型定義：二叉鏈表的類型定義： typedef struct bitnode Elemtype data; struct bitnode *lchild,*rchlid; Bitnode,*Bitree; 二叉鏈表二叉鏈表 結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： lchild data rchild 其中，其中，lchild和和rchi

11、ld是分別指向該結(jié)點(diǎn)左孩是分別指向該結(jié)點(diǎn)左孩 子和右孩子的指針，子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。是數(shù)據(jù)元素的內(nèi)容。 2.2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 三叉鏈表三叉鏈表 lchild data parent rchild 結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： P127 圖圖6.8 G H D E F B C A T D E F B C G H A 二叉鏈表的類型定義：二叉鏈表的類型定義： typedef struct bitnode Elemtype data; struct bitnode *lchild,*rchlid; Bitnode,*Bitree; 遍歷：按某種次序遍歷：按某種次序“訪問

12、訪問”二叉樹中的每個結(jié)點(diǎn)一次且僅二叉樹中的每個結(jié)點(diǎn)一次且僅 訪問一次的過程。訪問一次的過程。 訪問：可以是輸出、比較、更新、查看元素內(nèi)容等等操作。訪問：可以是輸出、比較、更新、查看元素內(nèi)容等等操作。 關(guān)鍵：訪問結(jié)點(diǎn)的次序。關(guān)鍵：訪問結(jié)點(diǎn)的次序。 6.3.1 6.3.1 遍歷二叉樹遍歷二叉樹 子任務(wù)子任務(wù) 訪問根訪問根 遍歷左子樹遍歷左子樹 遍歷右子樹遍歷右子樹 （1 1）先序（先根）遍歷：）先序（先根）遍歷： 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷左子樹 先序遍歷右子樹先序遍歷右子樹 （2 2）中序（中根）遍歷：）中序（中根）遍歷： 中序遍歷左子樹中序遍歷左子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 中序遍

13、歷右子樹中序遍歷右子樹 （3 3）后序（后根）遍歷：）后序（后根）遍歷： 后序遍歷左子樹后序遍歷左子樹后序遍歷右子樹后序遍歷右子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) G H D E F B C A 先序序列：先序序列：ABDGCEFH 中序序列：中序序列：DGBAECHF 后序序列：后序序列：GDBEHFCA 前綴表示（波蘭式）、中綴表示、后綴表示（逆波蘭式）前綴表示（波蘭式）、中綴表示、后綴表示（逆波蘭式） 例：已知某例：已知某二叉樹先序序列是二叉樹先序序列是ABDEFGCHI，中序序列是，中序序列是 DBFEGAHIC，請寫出它的后序序列。，請寫出它的后序序列。 表達(dá)式：表達(dá)式：a+b*(c-d)-e/

14、f （1）先序遍歷）先序遍歷 void preorder(Bitree T) if (T) visit(*T); preorder(T-lchild); preorder(T-rchild); 遞歸算法遞歸算法 （2）中序遍歷）中序遍歷 void inorder(Bitree T) if (T) inorder(T-lchild); visit(*T); inorder(T-rchild); （3）后序遍歷）后序遍歷 void postorder(Bitree T) if (T) postorder(T-lchild); postorder(T-rchild); visit(*T); 按層次遍

15、歷二叉樹按層次遍歷二叉樹 按層次遍歷該二叉樹的序列為：按層次遍歷該二叉樹的序列為： ABCDEFGH G H D E F B C A 算法舉例算法舉例 1. 1. 輸入一個二叉樹的先序序列，構(gòu)造二叉鏈表。輸入一個二叉樹的先序序列，構(gòu)造二叉鏈表。 為了保證唯一地構(gòu)造出所希望的二叉樹，在鍵入這棵為了保證唯一地構(gòu)造出所希望的二叉樹，在鍵入這棵 樹的先序序列時，需要在所有空二叉樹的位置上填補(bǔ)一樹的先序序列時，需要在所有空二叉樹的位置上填補(bǔ)一 個特殊的字符，比如，個特殊的字符，比如，#。在算法中，需要對每個輸入。在算法中，需要對每個輸入 的字符進(jìn)行判斷，如果對應(yīng)的字符是的字符進(jìn)行判斷，如果對應(yīng)的字符是#

16、，則在相應(yīng)的位，則在相應(yīng)的位 置上構(gòu)造一棵空二叉樹；否則，創(chuàng)建一個新結(jié)點(diǎn)。整個置上構(gòu)造一棵空二叉樹；否則，創(chuàng)建一個新結(jié)點(diǎn)。整個 算法結(jié)構(gòu)以先序遍歷遞歸算法為基礎(chǔ)，二叉樹中結(jié)點(diǎn)之算法結(jié)構(gòu)以先序遍歷遞歸算法為基礎(chǔ)，二叉樹中結(jié)點(diǎn)之 間的指針連接是通過指針參數(shù)在遞歸調(diào)用返回時完成。間的指針連接是通過指針參數(shù)在遞歸調(diào)用返回時完成。 void create(Bitree if (ch=#) T=NULL; /構(gòu)造空樹構(gòu)造空樹 else T=(Bitree)malloc(sizeof(Bitnode); /構(gòu)造新構(gòu)造新 結(jié)點(diǎn)結(jié)點(diǎn) T-data=ch; create(T-lchild ); /構(gòu)造左子樹構(gòu)造左

17、子樹 create(T-rchild ); /構(gòu)造右子樹構(gòu)造右子樹 2. 2. 計算一棵二叉樹的葉子結(jié)點(diǎn)數(shù)目計算一棵二叉樹的葉子結(jié)點(diǎn)數(shù)目 void countleaf(Bitree T, int if (!T-lchild countleaf(T-rchild, n); 3 3 求二叉樹的深度求二叉樹的深度 這個操作使用后序遍歷比較符合人們求解二叉樹深度這個操作使用后序遍歷比較符合人們求解二叉樹深度 的思維方式。首先分別求出左右子樹的深度，在此基礎(chǔ)上的思維方式。首先分別求出左右子樹的深度，在此基礎(chǔ)上 得出該棵樹的深度，即左右子樹較大的深度值加得出該棵樹的深度，即左右子樹較大的深度值加1。 vo

18、id depth(Bitree T,int else depth(T-lchild, dep1); depth(T-rchild, dep2); dep=dep1dep2?dep1+1:dep2+1; 6.3.2 線索二叉樹結(jié)構(gòu)線索二叉樹結(jié)構(gòu) 線索：指向其在某種遍歷次序下的前驅(qū)或后繼結(jié)點(diǎn)的指針線索：指向其在某種遍歷次序下的前驅(qū)或后繼結(jié)點(diǎn)的指針 （放在空的（放在空的lchildlchild和和rchildrchild域）。域）。 線索二叉樹：加上線索的二叉樹。線索二叉樹：加上線索的二叉樹。 G H D E F B C A 結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)： ltag lchild data rchild rt

19、ag LtagLtag= = 0 lchild 指向左孩子指向左孩子 1 lchild 指向前驅(qū)指向前驅(qū) rtagrtag= = 0 rchild 指向右孩子指向右孩子 1 rchild 指向后繼指向后繼 1.1.先序后繼的求解先序后繼的求解 2.2.中序后繼的求解中序后繼的求解 data parent 一、雙親表示法一、雙親表示法 時間復(fù)雜度時間復(fù)雜度 找雙親找雙親 找根找根 找孩子找孩子 6.4.1 6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu) O（1） O（d） O（n） 由于每個結(jié)點(diǎn)的孩子個數(shù)不定，所以一般用孩子鏈由于每個結(jié)點(diǎn)的孩子個數(shù)不定，所以一般用孩子鏈 表表示。表表示。 二二. . 孩子

20、表示法孩子表示法 其中，其中，firstchild指向該結(jié)點(diǎn)的第一個孩子，指向該結(jié)點(diǎn)的第一個孩子，nextsibling 指向該結(jié)點(diǎn)的下一個兄弟，指向該結(jié)點(diǎn)的下一個兄弟，data是數(shù)據(jù)元素內(nèi)容。是數(shù)據(jù)元素內(nèi)容。 firstchild data nextsibling 三三. . 孩子兄弟表示法（二叉鏈表表示法）孩子兄弟表示法（二叉鏈表表示法） H I J E F G B C D A T 二樹的二叉鏈表的類型定義：二樹的二叉鏈表的類型定義： typedef struct CSnode Elemtype data; struct CSnode *firstlchild,*nextsibling;

21、CSnode,*CStree; 以二叉鏈表作中介以二叉鏈表作中介 1. 樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹 第一個孩子的指針看作是二叉樹中的左孩子指針，將指向下一個兄弟的第一個孩子的指針看作是二叉樹中的左孩子指針，將指向下一個兄弟的 指針看作孩子右指針時，就是一棵二叉樹了。指針看作孩子右指針時，就是一棵二叉樹了。 6.4.2 6.4.2 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 一、一、 樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換 特點(diǎn)：一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有右孩子。特點(diǎn)：一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有右孩子。 2. 二叉樹轉(zhuǎn)換成樹二叉樹轉(zhuǎn)換成樹 這個過程實(shí)際上是樹轉(zhuǎn)換成二叉樹的逆過程這個過程

22、實(shí)際上是樹轉(zhuǎn)換成二叉樹的逆過程 二、二、 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 把森林中所有樹的根結(jié)點(diǎn)看作兄弟關(guān)系，并對其中的每把森林中所有樹的根結(jié)點(diǎn)看作兄弟關(guān)系，并對其中的每 棵樹依依地進(jìn)行轉(zhuǎn)換。棵樹依依地進(jìn)行轉(zhuǎn)換。 1. 森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹 這個過程是森林轉(zhuǎn)換成二叉樹的逆過程。這個過程是森林轉(zhuǎn)換成二叉樹的逆過程。 2. 二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林 6.4.3 6.4.3 樹的遍歷樹的遍歷 1. 先根遍歷先根遍歷 （1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) （2）依次先根遍歷樹的各子樹）依次先根遍歷樹的各子樹 遍歷序列：遍歷序列： A B E K F C G L D H I J 一、一

23、、 樹的遍歷樹的遍歷 A BCD EFGHIJ KL 2. 后根遍歷后根遍歷 （1）依次后序遍歷樹的各子樹）依次后序遍歷樹的各子樹 （2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 遍歷序列：遍歷序列： K E F B L G C H I J D A 3. 層序遍歷層序遍歷 遍歷序列：遍歷序列： A B C D E F G H I J K L A BCD EFGHIJ KL 后根遍歷一棵樹等價于中序遍歷該樹對應(yīng)的二叉樹后根遍歷一棵樹等價于中序遍歷該樹對應(yīng)的二叉樹 A BCD EFGHIJ 先根：先根： B C D E FG H I J A 后根：后根： 注意：注意： 先根遍歷一棵樹等價于先序遍歷該樹對應(yīng)的二叉樹先

24、根遍歷一棵樹等價于先序遍歷該樹對應(yīng)的二叉樹 A B E F C G D H I J E F B G C H I J D A 先根：先根： void preroot(CStree T) if (T) visit(T); preroot(T-firstchild); preroot(T-nextsibling); 后根：后根： void postroot(CStree T) if (T) postroot(T-firstchild); visit(T); postroot(T-nextsibling); 1. 先序遍歷先序遍歷 F=T1，T2， T3，.，Tm （1）訪問）訪問T1的根的根root

25、1 （2）先序遍歷）先序遍歷root1的子樹森林的子樹森林 （3）先序遍歷）先序遍歷F=T2，T3，.，Tm 遍歷序列：遍歷序列： B E K F C G L D H I J 二、二、 森林的遍歷森林的遍歷 BCD EFGHIJ KL 2. 中序遍歷中序遍歷 F=T1，T2， T3，.，Tm （1）中序遍歷）中序遍歷root1的子樹森林的子樹森林 （2）訪問）訪問T1的根的根root1 （3）中序遍歷）中序遍歷F=T2，T3，.，Tm 遍歷序列：遍歷序列： K E F B L G C H I J D BCD EFGHIJ KL BCD EFGHIJ 先序：先序： B C D E FG H I

26、J B E F C G D H I J E F B G C H I J D 注意：注意： 先序遍歷森林等價于先序遍歷該森林對應(yīng)的二叉樹先序遍歷森林等價于先序遍歷該森林對應(yīng)的二叉樹 中序遍歷森林等價于中序遍歷該森林對應(yīng)的二叉樹中序遍歷森林等價于中序遍歷該森林對應(yīng)的二叉樹 中序：中序： 6.6.1 最優(yōu)二叉樹（哈夫曼樹）最優(yōu)二叉樹（哈夫曼樹） 一、基本概念一、基本概念 路徑：路徑：一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支 路徑長度：路徑長度：路徑上的分支數(shù)目路徑上的分支數(shù)目 樹的路徑長度樹的路徑長度：根到每一結(jié)點(diǎn)的路徑長度之和：根到每一結(jié)點(diǎn)的路徑長度之和 G H D E F B

27、 C A 結(jié)點(diǎn)帶權(quán)路徑長度結(jié)點(diǎn)帶權(quán)路徑長度：結(jié)點(diǎn)權(quán)值：結(jié)點(diǎn)權(quán)值*結(jié)點(diǎn)到根的路徑長度之和結(jié)點(diǎn)到根的路徑長度之和 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和：葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和 n i iiLwWPL 1 假設(shè)有假設(shè)有6個權(quán)值分別為個權(quán)值分別為3，6，9，10，7，11，以這，以這6 個權(quán)值作為葉子結(jié)點(diǎn)的權(quán)值可以構(gòu)造出如下所示二叉樹：個權(quán)值作為葉子結(jié)點(diǎn)的權(quán)值可以構(gòu)造出如下所示二叉樹： 3 6 7 9 10 11 WPL1=(10+11)*2+(3+6+7+9)*3=117 11 3 6 7 9 10 WPL2=3*1+6*2+7*3+9*4+(10+11)*5=177 3

28、 11 10 9 7 6 WPL3=11*1+10*2+9*3+7*4+(6+3)*5=131 特點(diǎn)：特點(diǎn)：權(quán)越大的葉子離根越近權(quán)越大的葉子離根越近 給定一組權(quán)值給定一組權(quán)值ww1 1,w,w2 2 , ,w ,wn n,結(jié)點(diǎn)結(jié)點(diǎn)i i的權(quán)值為的權(quán)值為w wi i， 用這用這n n個結(jié)點(diǎn)作葉子結(jié)點(diǎn)構(gòu)造二叉樹，其中個結(jié)點(diǎn)作葉子結(jié)點(diǎn)構(gòu)造二叉樹，其中WPLWPL最最 小的二叉樹稱為哈夫曼樹。小的二叉樹稱為哈夫曼樹。 哈夫曼樹的定義：哈夫曼樹的定義： 給定一組權(quán)值給定一組權(quán)值ww1 1,w,w2 2 , ,w ,wn n 1 . 構(gòu)造一個森林構(gòu)造一個森林T1,T2,.,Tn，Ti(i=1,2, .,n

29、) 只有一根結(jié)點(diǎn)，只有一根結(jié)點(diǎn)， 權(quán)值為權(quán)值為wi i； 2. 在在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹作左右子樹構(gòu)造中選取兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹作左右子樹構(gòu)造 一棵新二叉樹，新二叉樹的根結(jié)點(diǎn)權(quán)值為這兩棵樹根的權(quán)一棵新二叉樹，新二叉樹的根結(jié)點(diǎn)權(quán)值為這兩棵樹根的權(quán) 值之和；值之和； 3 將上面選擇的這兩棵根權(quán)值最小的二叉樹從將上面選擇的這兩棵根權(quán)值最小的二叉樹從F中刪除，并中刪除，并 將新構(gòu)造的二叉樹加入到將新構(gòu)造的二叉樹加入到F中；中； 4. 重復(fù)上面重復(fù)上面2和和3，直到，直到F中只有一棵二叉樹為止。這棵二叉中只有一棵二叉樹為止。這棵二叉 樹就是哈夫曼樹。樹就是哈夫曼樹。 二、二、 構(gòu)造哈

30、夫曼樹構(gòu)造哈夫曼樹 假設(shè)有一組權(quán)值假設(shè)有一組權(quán)值5,29,7,8,14,23,3,11，下面我們將利用這組權(quán)值演示構(gòu)，下面我們將利用這組權(quán)值演示構(gòu) 造哈夫曼樹的過程。造哈夫曼樹的過程。 第一步：以這第一步：以這8個權(quán)值作為根結(jié)點(diǎn)的權(quán)值構(gòu)造具有個權(quán)值作為根結(jié)點(diǎn)的權(quán)值構(gòu)造具有8棵樹的森林棵樹的森林 5 29 7 8 14 23 3 11 第二步：從中選擇兩個根的權(quán)值最小的樹第二步：從中選擇兩個根的權(quán)值最小的樹3，5作為左右子樹作為左右子樹 構(gòu)造一棵新樹，并將這兩棵樹從森林中刪除，并將新樹添加進(jìn)去構(gòu)造一棵新樹，并將這兩棵樹從森林中刪除，并將新樹添加進(jìn)去 3 5 29 7 8 14 23 11 8 第

31、三步：重復(fù)第二步過程，選擇第三步：重復(fù)第二步過程，選擇7、8，直到森林中只有一棵樹為止，直到森林中只有一棵樹為止 29 14 23 11 7 8 15 3 5 8 選擇選擇8、11 29 14 23 11 7 8 15 3 5 8 29 14 23 7 8 15 3 5 8 11 19 選擇選擇14、15 29 23 7 8 15 3 5 8 11 19 14 29 選擇選擇19、23 29 7 8 15 14 29 3 5 8 11 19 42 23 選擇選擇29、29 3 5 8 11 19 42 2329 7 8 1514 29 58 選擇選擇42、58 3 5 8 11 19 42 2329 7 8 1514 29 58 100 29 7 8 15 14 29 3 5 8 11 19 42 23 編碼時需要遵守兩個原則： （1）譯碼后必須具有唯一性； （2）發(fā)送的二進(jìn)制編碼盡可能地短。 1. 1. 等長編碼等長編碼 若現(xiàn)在有一段電文為：若現(xiàn)在有一段電文為：ABACCDAABACCDA，字符集只含有，字符集只含有4 4個字個字 符符A A，B B，C C，D D，用兩位二進(jìn)制表示的編碼，分別為，用兩位二進(jìn)制表示的編碼，分別為0000，0101， 1010，1111。則應(yīng)發(fā)送序列：。則應(yīng)發(fā)送序列：00100101