數(shù)據(jù)結(jié)構(gòu)第6章 樹和二叉樹

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第第6章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用特點：特點：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼（直接后繼（1 1：n n）36.1 樹的基本概念1. 樹的定義樹的定義2 若干術(shù)語若干術(shù)語3. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)4.存儲結(jié)構(gòu)存儲結(jié)構(gòu)5. 樹的運算樹的運算41. 樹的定義樹的定義注注1：過去許多書籍中都定義樹

2、為過去許多書籍中都定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是樹樹”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即樹中還有樹。，即樹中還有樹。由一個或多個由一個或多個( (n0n0) )結(jié)點組成的有限集合結(jié)點組成的有限集合T T，有，有且僅有且僅有一個結(jié)點稱為根一個結(jié)點稱為根（rootroot），），當當n1n1時，其余的時，其余的結(jié)點分為結(jié)點分為m(m0)m(m0)個個互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，被稱作這個根的。每個集合本身又是棵樹，被稱作這個根的子樹子樹 。5樹的表

3、示法有幾種：樹的表示法有幾種：圖形表示法圖形表示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的示意圖這些表示法的示意圖參見教材參見教材P120P120樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義參參見教材見教材P118-119P118-1196圖形表示法：圖形表示法：教師教師學生學生其他人員其他人員20032003級級 20042004級級 20052005級級20062006級級河南大學河南大學物理系物理系計算機系計算機系化學系化學系葉子葉子根根子樹子樹7廣義表表示法廣義表表示法( A ( B ( E ( K, L ),

4、 F ), C ( G ), D ( H ( M ), I, J ) ) 根作為根作為由子樹森林組成的由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊datalink 1 link 2.link n麻煩問題：應當開設(shè)多少個鏈域麻煩問題：應當開設(shè)多少個鏈域?8左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )9 樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義（見教材（見教材P118-119P118-119）ADT Tree數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系

5、R:基本操作基本操作 P：ADT Tree若若D為空集，則稱為空樹；為空集，則稱為空樹；/允許允許n=0若若D中僅含一個數(shù)據(jù)元素，則中僅含一個數(shù)據(jù)元素，則R為空集；為空集；其他情況下的其他情況下的R存在二元關(guān)系：存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說明關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明關(guān)于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有15個個102. 若干術(shù)語若干術(shù)語即上層的那個結(jié)點即上層的那個結(jié)點(直接前驅(qū)直接前驅(qū))即下層結(jié)點的子樹的根即下層結(jié)點的子樹的根(直接后繼直接后繼)同一

6、雙親下的同層結(jié)點（孩子之間互稱兄弟）同一雙親下的同層結(jié)點（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點（但并非同一雙親）即雙親位于同一層的結(jié)點（但并非同一雙親）即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即該結(jié)點下層子樹中的任一結(jié)點即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點即根結(jié)點(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點即終端結(jié)點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數(shù)后的子樹個數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結(jié)點各子樹從左至右有序，不能互換

7、（左為第一）結(jié)點各子樹從左至右有序，不能互換（左為第一）結(jié)點各子樹可互換位置。結(jié)點各子樹可互換位置。112. 若干術(shù)語（續(xù)）若干術(shù)語（續(xù)）即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點掛接的子樹數(shù)結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度（有幾個直接后繼就是幾度，亦稱，亦稱“次數(shù)次數(shù)”）結(jié)點結(jié)點結(jié)點的度結(jié)點的度結(jié)點的層次結(jié)點的層次終端結(jié)點終端結(jié)點分支結(jié)點分支結(jié)點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEIDHFJMLK從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）即度為即度為0的結(jié)點，即葉子的結(jié)點，即葉子即度不為即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）的結(jié)點（也稱為內(nèi)部結(jié)點）所

8、有結(jié)點度中的最大值（所有結(jié)點度中的最大值（Max各結(jié)點的度各結(jié)點的度）指所有結(jié)點中最大的層數(shù)（指所有結(jié)點中最大的層數(shù)（Max各結(jié)點的層次各結(jié)點的層次）問：問：右上圖中的結(jié)點數(shù)右上圖中的結(jié)點數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4123. 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu) ( (特點特點) )： 一對多（一對多（1:n1:n），有多個直接后繼（如家譜），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，樹、目錄樹等等），但只有一個根結(jié)點，且且子樹之間互不相交子樹之間互不相交。 4. 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu) 討論討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？樹是非線性結(jié)構(gòu)，該怎樣存儲

9、？仍然有順序存儲、鏈式存儲等方式。仍然有順序存儲、鏈式存儲等方式。 13討論討論3：樹的樹的鏈式存儲鏈式存儲方案應該怎樣制定？方案應該怎樣制定？可規(guī)定為：可規(guī)定為：從上至下、從左至右從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存。將樹的結(jié)點依次存入內(nèi)存。重大缺陷：復原困難（不能唯一復原就沒有實用價值）。重大缺陷：復原困難（不能唯一復原就沒有實用價值）。討論討論2：樹的樹的順序存儲順序存儲方案應該怎樣制定？方案應該怎樣制定？可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。細節(jié)問題：細節(jié)問題：樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？ 即應

10、該設(shè)計成即應該設(shè)計成“等長等長”還是還是“不等長不等長”？缺點：缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）； 不等長結(jié)構(gòu)太復雜（要定義好多種結(jié)構(gòu)類型）。不等長結(jié)構(gòu)太復雜（要定義好多種結(jié)構(gòu)類型）。解決思路：解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。一般的樹轉(zhuǎn)化為簡單樹。145. 樹的運算樹的運算 要明確：要明確：1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)。算很難實現(xiàn)。2. 二叉樹的運算仍然是插入、刪除、修改、查找、二叉樹的運算仍然是

11、插入、刪除、修改、查找、排序等，但這些操作必須建立在排序等，但這些操作必須建立在對樹結(jié)點能夠?qū)浣Y(jié)點能夠“遍歷遍歷”的基礎(chǔ)上！的基礎(chǔ)上?。ū闅v遍歷指每個結(jié)點都被訪問且僅訪問一次，指每個結(jié)點都被訪問且僅訪問一次，不遺漏不重復）。不遺漏不重復）。本章重點：二叉樹的表示和實現(xiàn)本章重點：二叉樹的表示和實現(xiàn)156.2 6.2 二叉樹二叉樹為何要重點研究每結(jié)點最多只有兩個為何要重點研究每結(jié)點最多只有兩個 “ “叉叉” ” 的樹？的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強； 可以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性?？梢宰C明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性

12、。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)（二叉樹的運算（二叉樹的運算見見6.3節(jié)節(jié)）16定義：定義：是是n（n0）個結(jié)點的有限集合，由一個根結(jié)點以及兩）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為棵互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1：2） 基本特征基本特征: 每個結(jié)點最多只有兩棵子樹（不存在度大于每個結(jié)點最多只有兩棵子樹（不存在度大于2 2的結(jié)點）；的結(jié)點）； 左子樹和右子樹次序不能顛倒（有序樹）。左子樹和右子樹次序不能顛倒（有序樹）?；?/p>

13、形態(tài)：基本形態(tài)： 5種種/2種種17二叉樹的抽象數(shù)據(jù)類型定義二叉樹的抽象數(shù)據(jù)類型定義（見教材（見教材P P121-122121-122）ADT BinaryTree數(shù)據(jù)對象數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:基本操作基本操作 P：ADT BinaryTree若若D=，則，則R= ；若若D，則，則R= H；存在二元關(guān)系：；存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說明關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明關(guān)于數(shù)據(jù)元素的說明 /關(guān)于左子樹和右子樹的說明關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少

14、有至少有20個個18討論討論1 1：第：第i i層的結(jié)點數(shù)至多是多少？層的結(jié)點數(shù)至多是多少？ （利用二進制性質(zhì)可輕松求出）（利用二進制性質(zhì)可輕松求出） 性質(zhì)性質(zhì)1: 1: 在二叉樹的第在二叉樹的第i i層上至多有層上至多有個結(jié)點（個結(jié)點（i0i0）。）。性質(zhì)性質(zhì)2: 2: 深度為深度為k k的二叉樹至多有的二叉樹至多有個結(jié)點（個結(jié)點（k0k0）。）。2 2i-1i-1個個提問：第提問：第i i層上至少有層上至少有 個結(jié)點？個結(jié)點？1 1討論討論2 2：深度為：深度為k k的二叉樹，至多有多少個結(jié)點？的二叉樹，至多有多少個結(jié)點？ （利用二進制性質(zhì)可輕松求出）（利用二進制性質(zhì)可輕松求出）2 2k

15、k-1-1提問：深度為提問：深度為k k時至少有時至少有 個結(jié)點？個結(jié)點？k k19討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結(jié)點數(shù)之間有關(guān)系嗎？的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結(jié)點數(shù)有度的結(jié)點數(shù)有n n2 2個，個，則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2+1）二叉樹中全部結(jié)點數(shù)二叉樹中全部結(jié)點數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結(jié)點數(shù)度結(jié)點數(shù)2 2度結(jié)點數(shù)度結(jié)點數(shù)) )二叉樹中全部結(jié)點數(shù)二叉樹中全部結(jié)點數(shù)nB+1 ( ( 總分支數(shù)根結(jié)點總分支數(shù)根結(jié)點

16、 ) ) （除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）（除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）總分支數(shù)總分支數(shù)B= n1+2n2 (1(1度結(jié)點必有度結(jié)點必有1 1個直接后繼，個直接后繼，2 2度結(jié)點必有度結(jié)點必有2 2個個) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1實際意義：實際意義：葉子數(shù)葉子數(shù)2 2度結(jié)點數(shù)度結(jié)點數(shù)1 1ABCGEIDHFJ20對于兩種特殊形式的二叉樹（對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹），），還特別具備以下還特別具備以下2 2個性質(zhì)：個性質(zhì)：性質(zhì)性質(zhì)4: 4: 具有具有n n個結(jié)點的完全二叉樹的深

17、度必為個結(jié)點的完全二叉樹的深度必為loglog2 2nn1 1性質(zhì)性質(zhì)5: 5: 對完全二叉樹，若從上至下、從左至右編號，對完全二叉樹，若從上至下、從左至右編號，則編號為則編號為i 的結(jié)點，其左孩子編號必為的結(jié)點，其左孩子編號必為2i，其右孩子編號，其右孩子編號必為必為2i1；其雙親的編號必為；其雙親的編號必為i/2（i1 時為根時為根, ,除外除外）。）。 證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個結(jié)點，且完全二叉樹個結(jié)點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點數(shù)的定義是與同深度的滿二叉樹前面編號相

18、同，即它的總結(jié)點數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，即層滿二叉樹容量之間，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三邊同時取對數(shù)，于是有：三邊同時取對數(shù)，于是有：k-1logk-1log2 2nk n1)f=n*fact(n-1); else f=1; return(f); 34先序遍歷算法先序遍歷算法DLR( liuyu *root )if (root !=NULL) /非空二叉樹非空二叉樹 printf(“%d”,root-data); /訪問訪問D DDLR(root-lchild); /遞歸遍歷左子樹遞

19、歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 中序遍歷算法中序遍歷算法LDR(x*root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍歷算法后序遍歷算法LRD (x*root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);結(jié)點數(shù)據(jù)類型自定義結(jié)點數(shù)據(jù)類型自定義typedef stru

20、ct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 35對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過上，每個結(jié)點經(jīng)過3次次。AFEDCBG第第1次經(jīng)過時

21、訪問先序遍歷次經(jīng)過時訪問先序遍歷第第2次經(jīng)過時訪問中序遍歷次經(jīng)過時訪問中序遍歷第第3次經(jīng)過時訪問后序遍歷次經(jīng)過時訪問后序遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結(jié)點只訪問一次每個結(jié)點只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元?。﹤€輔助單元！）36例：例：【嚴題集【嚴題集6.42】編寫遞歸算法，計算二叉編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。樹中葉子結(jié)點的數(shù)目。 思路：思路：輸出葉子結(jié)點比較簡單，用任何一種遍

22、歷算法，凡輸出葉子結(jié)點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。 DLR(liuyu *root) /采用中序遍歷的遞歸算法采用中序遍歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成非空二叉樹條件，還可寫成if(root)if(root) if(!root-lchild&!root-rchild) /是葉子結(jié)點則統(tǒng)計并打印是葉子結(jié)點則統(tǒng)計并打印 sum+; printf(%dn,root-data); DLR(root-lchild); /遞歸遍歷左子樹，直到葉子處；遞歸遍

23、歷左子樹，直到葉子處； DLR(root-rchild); /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 37注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹 （結(jié)點值陸續(xù)從鍵盤輸入，用（結(jié)點值陸續(xù)從鍵盤輸入，用DLR為宜為宜）Bintree createBTpre( ) Bintree T; char ch;scanf(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintree )malloc(sizeof(BinTNode);T-data=c

24、h;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎樣建樹？見教材怎樣建樹？見教材P131P131程序。程序。38習題討論：習題討論： 算法思路：算法思路：只查各結(jié)點后繼鏈表指針，若左只查各結(jié)點后繼鏈表指針，若左( (右右) )孩子的左孩子的左( (右右) )指針非空，則層次數(shù)加指針非空，則層次數(shù)加1 1；否則函數(shù)返回。；否則函數(shù)返回。技巧：技巧：遞歸時應當遞歸時應當從葉子開始向上計數(shù)，層深者保留。從葉子開始向上計數(shù)，層深者保留。否則否則不易確定層數(shù)。不易確定層數(shù)。 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上

25、到下，從左到右，則利用隊列利用隊列存放存放各子樹結(jié)點的指針是個好辦法，而不必拘泥于遞歸算法。各子樹結(jié)點的指針是個好辦法，而不必拘泥于遞歸算法。技巧：技巧：當根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩當根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，子出隊時又令它的左右孩子結(jié)點入隊，由此便可產(chǎn)生按由此便可產(chǎn)生按層次輸出的效果。層次輸出的效果。 A B CD E39算法思路：算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套嵌套”規(guī)規(guī)則，必用堆棧?？芍苯佑脛t，必用堆棧。可直接用whilewhile語句和語句和push/poppush/p

26、op操作。操作。參見教參見教材材P130-131P130-131程序。程序。 算法思路：算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況獨存在的情況( (前前k-1k-1層都是滿的，且第層都是滿的，且第k k層左邊也滿）層左邊也滿）。技巧技巧: :按層序遍歷方式，先把所有結(jié)點按層序遍歷方式，先把所有結(jié)點（不管當前結(jié)點是否有（不管當前結(jié)點是否有左右孩子）左右孩子）都入隊列都入隊列. .若為完全二叉樹若為完全二叉樹, ,則層序遍歷時得到的則層序遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列肯定是一個連續(xù)的不包含空指針的序列. .如果序列中出

27、現(xiàn)了空如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。指針，則說明不是完全二叉樹。40【嚴題集【嚴題集6.31】 證明：由一棵二叉樹的先序序列和中序證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。序列可唯一確定這棵二叉樹。 例：例：已知一棵二叉樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序序列分別是分別是BDCEAFHG 和和 DECBHGFA，請畫出這棵二叉樹。，請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結(jié)點必在后序序列尾部由后序遍歷特征，根結(jié)點必在后序序列尾部（即（即A A）；由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是由中序遍歷特征，根結(jié)點必在其中間，而且其

28、左部必全部是左子樹子孫左子樹子孫（即（即BDCEBDCE），其右部必全部是右子樹子孫，其右部必全部是右子樹子孫（即（即FHGFHG）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹可確定子樹可確定B B為為A A的左孩子，根據(jù)的左孩子，根據(jù)HGFHGF子串可確定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。41中序遍歷：中序遍歷：B D C E A F H G后序遍歷：后序遍歷：D E C B H G F A（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF42問：問：用二叉鏈表法（用二叉鏈表法（l_child, r_ch

29、ild）存儲包含）存儲包含n個結(jié)點的個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有多少個空指針？二叉樹，結(jié)點的指針區(qū)域中會有多少個空指針？分析：分析：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結(jié)點的二叉樹，結(jié)點必有個結(jié)點的二叉樹，結(jié)點必有2n個鏈域個鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。除根結(jié)點外，二叉樹中每一個結(jié)點除根結(jié)點外，二叉樹中每一個結(jié)點有且僅有一個雙親有且僅有一個雙親（直接前驅(qū)），所以只會有（直接前驅(qū)），所以只會有n n1 1個結(jié)點的鏈域存放指針，指個結(jié)點的鏈域存放指針，指向非空子女結(jié)點（即直接后繼）。向非空子女結(jié)點（即直接后繼）。思考：思考：二叉鏈表空間效率這么低，能否

30、利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？我們可以用它來存放當前結(jié)點的直接前驅(qū)和后繼等線索，我們可以用它來存放當前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個個。n+143二、線索二叉樹線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結(jié)點的左右孩子信息，普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后遍歷后對應的有關(guān)前驅(qū)和后繼對應的有關(guān)前

31、驅(qū)和后繼預存預存起來，則從起來，則從第第一個結(jié)點一個結(jié)點開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法：兩種解決方法：增加兩個域：增加兩個域：fwd和和bwd；存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預存這類信息？如何預存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H GB D C E A F H G，實際上，實際上已將二叉已將二叉樹轉(zhuǎn)為樹轉(zhuǎn)為線性排列線性排列，顯然具有唯一前驅(qū)和唯一后繼。，顯然具有唯一前驅(qū)和唯一后繼。1. 1. 定義定義 2. 2. 生成生成 3. 3. 遍歷遍歷利用空鏈域（利用空鏈域（n+1個空

32、鏈域）個空鏈域）44規(guī)定：規(guī)定：1）若結(jié)點有左子樹，則）若結(jié)點有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點有右子樹，則）若結(jié)點有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為區(qū)別兩種不同情況，特增加兩個標志域（各為區(qū)別兩種不同情況，特增加兩個標志域（各1bit)lchilddatarchild約定約定:當當Tag域為域為0時時,表示表示正常正常情況情況;當當Tag域為域為1時時,表示表示線索線索情況情況.右孩子或后繼右孩子

33、或后繼左孩子或前驅(qū)左孩子或前驅(qū)LTagRTag45附：有關(guān)線索二叉樹的幾個術(shù)語：附：有關(guān)線索二叉樹的幾個術(shù)語： 線索鏈表：線索鏈表：用用含含Tag的結(jié)點樣式所構(gòu)成的二叉鏈表的結(jié)點樣式所構(gòu)成的二叉鏈表 線線 索：索：指向結(jié)點前驅(qū)和后繼的指針指向結(jié)點前驅(qū)和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹 線線 索索 化：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程叉樹的過程討論：討論：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當前結(jié)點的前驅(qū)和后繼，不用能方便找出當前結(jié)點的前驅(qū)和后繼，不用堆棧也能遍歷整個

34、樹。堆棧也能遍歷整個樹。46data AGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：例：某某先序遍歷先序遍歷結(jié)果如下表所示，請畫出對應的結(jié)果如下表所示，請畫出對應的二叉樹。二叉樹。（多帶了兩個標志！）（多帶了兩個標志?。?72. 2. 線索二叉樹的生成線索二叉樹的生成線索化過程就是線索化過程就是在遍歷過程中修改空指針在遍歷過程中修改空指針的過程：的過程：將空的將空的l lchildchild改為結(jié)點的直接前驅(qū)；改為結(jié)點的直接前驅(qū)；將空的將空的r rchildchild改為結(jié)點的直接后繼。改為結(jié)點的直接后繼。非空指針呢？仍然指向孩子結(jié)點（稱為

35、非空指針呢？仍然指向孩子結(jié)點（稱為“正常情況正常情況”）48ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：為避免懸空為避免懸空態(tài)，應增設(shè)態(tài)，應增設(shè)一個頭結(jié)點一個頭結(jié)點例例1 1：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。4900A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root

36、0對應的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：對應的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：50例例2 2：【 2000年計算機系考研題】年計算機系考研題】給定如圖所示給定如圖所示二叉樹二叉樹T T，請畫出與其對應的中序線索二叉樹。，請畫出與其對應的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL51線索二叉樹的生成算法線索二叉樹的生成算法（算

37、法算法6.6, 見教材見教材P134）目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后 繼。繼。注解：為方便添加結(jié)點的前驅(qū)或后繼，需要設(shè)置兩個指針：注解：為方便添加結(jié)點的前驅(qū)或后繼，需要設(shè)置兩個指針： p指針指針當前結(jié)點之指針；當前結(jié)點之指針； pre指針指針前驅(qū)結(jié)點之指針。前驅(qū)結(jié)點之指針。技巧：技巧：當結(jié)點當結(jié)點p的左的左/右域為空右域為空時，只改寫它的左域（裝入前驅(qū)時，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點來填寫。，而其右域（后繼）留給下一結(jié)點來填寫。 或者說，當前結(jié)點的指針或者說，當前結(jié)點的指針p應當送到

38、前驅(qū)結(jié)點的空右域中。應當送到前驅(qū)結(jié)點的空右域中。若若p-lchildNULL, ,則則p-Ltag=1;p-Ltag=1;p-lp-lchildchildpre; ; /p/p的前驅(qū)結(jié)點指針的前驅(qū)結(jié)點指針pre存入左空域存入左空域若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;pre-rchild=p; /p存入其前驅(qū)結(jié)點存入其前驅(qū)結(jié)點pre的右的右空域空域523. 3. 線索二叉樹的遍歷線索二叉樹的遍歷理論上，只要找到序列中的理論上，只要找到序列中的第一個結(jié)點第一個結(jié)點，然后，然后依次訪依次訪問結(jié)點的后繼問結(jié)點的后繼直到后繼為空時結(jié)束。直到后繼為空時結(jié)束。在線索化

39、二叉樹中，并不是每個結(jié)點都能直接找到其在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，后繼的，當標志為當標志為0 0時，時，R_child=R_child=右孩子地址指針，并非后繼！右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。需要通過一定運算才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：對葉子結(jié)點（對葉子結(jié)點（RTag=1），直接后繼指針就在其），直接后繼指針就在其rchild域內(nèi)；域內(nèi)；對其他結(jié)點（對其他結(jié)點（RTag=0），直接后繼是其），直接后繼是其右子樹最左下的結(jié)點右子樹最左下的結(jié)點；（因為中序遍歷規(guī)則是（因為中序遍歷規(guī)則是LDR，）53程序注解程

40、序注解 (非遞歸，且不用棧非遞歸，且不用棧）：）：P=T-lchild; /從頭結(jié)點進入到根結(jié)點；從頭結(jié)點進入到根結(jié)點；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍歷起點先找到中序遍歷起點 if(!visit(p-data) return ERROR; /若起點值為空則出錯告警若起點值為空則出錯告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標志，則直接提取若有后繼標志，則直接提取p-rchild中線索并中線索并訪問后繼結(jié)點；訪問后繼結(jié)點；p=p-rchild; /當前結(jié)點

41、右域不空當前結(jié)點右域不空或或已經(jīng)找好了后繼已經(jīng)找好了后繼，則一律從，則一律從結(jié)點的右子樹開始重復結(jié)點的右子樹開始重復 的全部過程。的全部過程。Return OK;線索二叉樹的線索二叉樹的中序中序遍歷算法遍歷算法（算法算法6.5, 參見教材參見教材P134）LTag=0RTag=154算法流程：算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演演示示程程序序55提前介紹：二叉樹的應用提前介紹

42、：二叉樹的應用平衡樹平衡樹排序樹排序樹字典樹字典樹判定樹判定樹帶權(quán)樹帶權(quán)樹最優(yōu)樹最優(yōu)樹特點：左右子樹深度差特點：左右子樹深度差 1特點：特點：“左小右大左小右大”（見實驗二的方案（見實驗二的方案1）由字符串構(gòu)成的二叉樹排序樹由字符串構(gòu)成的二叉樹排序樹例如，例如，12個球只稱個球只稱3次分出輕重次分出輕重特點：路徑長度帶權(quán)值特點：路徑長度帶權(quán)值 帶權(quán)路徑長度最短的樹，又稱帶權(quán)路徑長度最短的樹，又稱 Huffman樹，用途之一是通信中的壓縮編碼。樹，用途之一是通信中的壓縮編碼。566.4 樹和森林1. 樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換2. 樹和森林的存儲方式樹和森林的存儲方式3. 樹和

43、森林的遍歷樹和森林的遍歷571. 樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：step1: step1: 將樹中同一結(jié)點的兄弟相連將樹中同一結(jié)點的兄弟相連; ;step2: step2: 保留結(jié)點的最左孩子連線，刪除其它孩保留結(jié)點的最左孩子連線，刪除其它孩子連線；子連線；step3: step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)將同一孩子的連線繞左孩子旋轉(zhuǎn)4545度角。度角。加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)討論討論1 1：樹如何轉(zhuǎn)為二叉樹？：樹如何轉(zhuǎn)為二叉樹？58方法：方法：加加線線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例：樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連兄弟相連

44、長兄為父長兄為父孩子靠左孩子靠左59討論討論2 2：二叉樹怎樣還原為樹？：二叉樹怎樣還原為樹？abeidfhgc要點：把所有右孩子變?yōu)樾值?！要點：把所有右孩子變?yōu)樾值埽?abeidfhgc60法一：法一： 各森林先各自轉(zhuǎn)為二叉樹；各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個二叉樹的右子樹上。依次連到前一個二叉樹的右子樹上。討論討論3 3：森林如何轉(zhuǎn)為二叉樹？：森林如何轉(zhuǎn)為二叉樹？法二：法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材（參見教材P138P138圖圖6.176.17，兩種方法都有轉(zhuǎn)換示意圖），兩種方法都有轉(zhuǎn)換示意圖）即即F=TF=T1 1, T, T2 2, ,

45、T, ,Tm m B=root, LB, RB B=root, LB, RB61ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉(zhuǎn)二叉樹舉例：森林轉(zhuǎn)二叉樹舉例：（法二）（法二）兄弟相連兄弟相連 長兄為父長兄為父孩子靠左孩子靠左 頭根為根頭根為根 62討論討論4 4：二叉樹如何還原為森林？：二叉樹如何還原為森林？要點：要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯?，其余右子樹變?yōu)樾值?ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, ,T, ,T

46、m m 632. 2. 樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用雙親表示法來存儲、用雙親表示法來存儲思路：思路：用一組用一組連續(xù)空間連續(xù)空間來存儲樹的結(jié)點，同時在每個來存儲樹的結(jié)點，同時在每個結(jié)點中結(jié)點中附設(shè)一個指示器附設(shè)一個指示器，指示其雙親結(jié)點在鏈表中的，指示其雙親結(jié)點在鏈表中的位置。位置。parentsdata結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)dataparents1樹結(jié)構(gòu)樹結(jié)構(gòu) 23n64缺點：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。缺點：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。012345678

47、12233ABCDEFGHI-1001例例1: 雙親表示法雙親表示法65思路：將每個結(jié)點的孩子排列起來，形成一個帶表頭思路：將每個結(jié)點的孩子排列起來，形成一個帶表頭（裝父結(jié)點）的線性表（裝父結(jié)點）的線性表（n n個結(jié)點要設(shè)立個結(jié)點要設(shè)立n n個鏈表）；個鏈表）；再將再將n n個表頭用數(shù)組存放起來，這樣就形成一個混合個表頭用數(shù)組存放起來，這樣就形成一個混合結(jié)構(gòu)。結(jié)構(gòu)。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表示法來存儲、用孩子表示法來存儲bc66思路：思路：用二叉鏈表來表示樹，但鏈表中的兩個用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。指針域含義不同

48、。左指針指向該結(jié)點的第一個孩子；左指針指向該結(jié)點的第一個孩子；右指針指向該結(jié)點的下一個兄弟結(jié)點。右指針指向該結(jié)點的下一個兄弟結(jié)點。nextsiblingdatafirstchild3 3、用孩子兄弟表示法來存儲、用孩子兄弟表示法來存儲指向左孩子指向左孩子指向右兄弟指向右兄弟67abecdfhgbacedfgh問：問：樹樹二叉樹的二叉樹的“連線連線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)” ” 如如何由計算機自動實現(xiàn)？何由計算機自動實現(xiàn)？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。 例如例如：68 先序遍歷先序遍歷F若森林為空，返回；若森林為空，返回；F訪問森林中第一棵樹的根結(jié)點；訪問森

49、林中第一棵樹的根結(jié)點；F先序遍歷第一棵樹中根結(jié)點的子樹森林；先序遍歷第一棵樹中根結(jié)點的子樹森林；F先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 中序遍歷中序遍歷F若森林為空，返回；若森林為空，返回；F中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；F訪問第一棵樹的根結(jié)點；訪問第一棵樹的根結(jié)點；F中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷森林的遍歷ABCDEFGHJI69路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權(quán)路徑長度帶權(quán)路徑長度：樹的帶權(quán)路

50、徑長度樹的帶權(quán)路徑長度：霍霍 夫夫 曼曼 樹樹：6.5 Huffman6.5 Huffman樹及其應用樹及其應用一、最優(yōu)二叉樹（一、最優(yōu)二叉樹（霍夫曼霍夫曼樹）樹）由一結(jié)點到另一結(jié)點間的分支所構(gòu)成由一結(jié)點到另一結(jié)點間的分支所構(gòu)成路徑上的分支數(shù)目路徑上的分支數(shù)目從樹根到從樹根到每一結(jié)點每一結(jié)點的路徑長度之和。的路徑長度之和。結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積預備知識：若干術(shù)語預備知識：若干術(shù)語debacf g樹中所有樹中所有葉子結(jié)點葉子結(jié)點的帶權(quán)路徑長度之和的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。帶權(quán)路徑長度最小的樹。aeae的路徑長度的路徑長度樹長度樹長度2

51、2101070HuffmanHuffman樹簡介：樹簡介：樹的帶權(quán)路徑長度如何計算？樹的帶權(quán)路徑長度如何計算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 35哈夫曼樹則是：哈夫曼樹則是：WPL WPL 最小的樹。最小的樹。Huffman樹樹Weighted Path LengthWeighted Path Length71構(gòu)造霍夫曼樹的基本思想：構(gòu)造霍夫曼樹的基本思想：構(gòu)造構(gòu)造HuffmanHuffman樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：7

52、2設(shè)有設(shè)有4 4個字符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2, 7,5,2, 4 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長編碼等長編碼。例如用二進制編碼來實現(xiàn)。例如用二進制編碼來實現(xiàn)。 取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111怎樣實現(xiàn)怎樣實現(xiàn)HuffmanHuffman編碼？編碼？法法2 2：不等長編碼不等長編碼，例如用哈夫曼編碼來實現(xiàn)。，例如用哈夫曼編碼來實現(xiàn)。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=

53、, n=111111最快的編碼是哪個？最快的編碼是哪個？是非等長的是非等長的HuffmanHuffman碼！碼！先要構(gòu)造先要構(gòu)造HuffmanHuffman樹！樹！73操作要點操作要點1 1：對權(quán)值的合并、刪除與替換對權(quán)值的合并、刪除與替換在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是合并中，總是合并當前值最小當前值最小的兩個權(quán)的兩個權(quán)構(gòu)造構(gòu)造HuffmanHuffman樹的步驟：樹的步驟：注：方框表示外結(jié)點（葉子，字符對應的權(quán)值），注：方框表示外結(jié)點（葉子，字符對應的權(quán)值）， 圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。74操作要點操作要點2 2：按左按左0 0

54、右右1 1對對HuffmanHuffman樹的所有分支編號！樹的所有分支編號！d da ai in n1 11 11 10 00 00 0HuffmanHuffman編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=1bitWPL=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特點：每一碼都不是另一碼的前綴，絕不會錯譯特點：每一碼都不是另一碼的前綴，絕不會錯譯! ! 稱為前綴碼稱為前綴碼HuffmanHuffman樹樹 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤75例例2

55、2（嚴題集（嚴題集6.266.26）：假設(shè)用于通信的電文僅由假設(shè)用于通信的電文僅由8 8個字母個字母 a, a, b, c, d, e, f, g, hb, c, d, e, f, g, h 構(gòu)成，它們在電文中出現(xiàn)的概率分別構(gòu)成，它們在電文中出現(xiàn)的概率分別為為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這試為這8 8個字母設(shè)計哈夫曼編碼。個字母設(shè)計哈夫曼編碼。如果用如果用0 07 7的二進制編碼方案的二進制編碼方案又如何？又如何？霍夫曼霍夫曼編碼

56、的基本思想是：概率大的字符用短碼，概率小的用編碼的基本思想是：概率大的字符用短碼，概率小的用長碼。由于長碼。由于霍夫曼樹的霍夫曼樹的WPLWPL最小，說明編碼所需要的比特數(shù)最最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應用于網(wǎng)絡(luò)通信中。少。這種編碼已廣泛應用于網(wǎng)絡(luò)通信中。解：解：先將概率放大先將概率放大100100倍，以方便構(gòu)造哈夫曼樹。倍，以方便構(gòu)造哈夫曼樹。權(quán)值集合權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得

57、到哈夫曼樹。76w4=19, 21, w4=19, 21, 28,28, 32 32為清晰起見，重新排序為為清晰起見，重新排序為: :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 21, 32 6, 7, 10, 19, 21, 32w2=7, 10, w2=7, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼樹哈夫曼樹77對應的哈夫曼編碼