數(shù)據(jù)結(jié)構(gòu)樹與二叉樹課件

1、數(shù)據(jù)結(jié)構(gòu)樹與二叉樹1第第5章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）特點(diǎn)：特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。直接后繼。（一對多或（一對多或1:n1:n）5.1 樹的概述樹的概述5.2 二叉樹定義和性質(zhì)二叉樹定義和性質(zhì)5.3 遍歷二叉樹遍歷二叉樹5.4 線索二叉樹線索二叉樹5.5 樹和森林樹和森林5.6 哈夫曼及其應(yīng)用哈夫曼及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)樹與二叉樹25.1 樹的基本概念1. 樹的定義樹的定義2. 若干術(shù)語若干術(shù)語3. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)4.存儲結(jié)構(gòu)存儲結(jié)構(gòu)5. 樹的運(yùn)算樹的運(yùn)算數(shù)據(jù)結(jié)構(gòu)樹與二叉樹3注注

2、1：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。由一個(gè)或多個(gè)由一個(gè)或多個(gè)( (n0n0) )結(jié)點(diǎn)組成的有限集合結(jié)點(diǎn)組成的有限集合T T，有且，有且僅有僅有一個(gè)結(jié)點(diǎn)稱為根一個(gè)結(jié)點(diǎn)稱為根（rootroot），），當(dāng)當(dāng)n1n1時(shí)，其余的結(jié)時(shí)，其余的結(jié)點(diǎn)分為點(diǎn)分為m(m0)m(m0)個(gè)個(gè)互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹子樹 。數(shù)據(jù)結(jié)構(gòu)樹與二叉樹4樹的表示法主要有樹的表示法主要有5種：種：v 圖形表示法圖形表示法v 嵌套集合表示法嵌套集合表示法v 廣義表表示法廣義表表

3、示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)結(jié)構(gòu)樹與二叉樹5教師教師學(xué)生學(xué)生其他人員其他人員20022002級級20032003級級20042004級級20052005級級華科大武昌分校華科大武昌分校電信系電信系計(jì)算機(jī)系計(jì)算機(jī)系自控系自控系葉子葉子根根子樹子樹數(shù)據(jù)結(jié)構(gòu)樹與二叉樹6數(shù)據(jù)結(jié)構(gòu)樹與二叉樹7( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作為根作為由子樹森林組成的由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊datalink 1 link 2.link n麻煩問題：應(yīng)當(dāng)開設(shè)多少個(gè)

4、鏈域麻煩問題：應(yīng)當(dāng)開設(shè)多少個(gè)鏈域?數(shù)據(jù)結(jié)構(gòu)樹與二叉樹8(又稱目錄表示法又稱目錄表示法)數(shù)據(jù)結(jié)構(gòu)樹與二叉樹9左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟右兄弟數(shù)據(jù)結(jié)構(gòu)樹與二叉樹102. 若干術(shù)語若干術(shù)語即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)掛接的子樹數(shù)結(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)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）即度為即度為0的結(jié)點(diǎn)，即葉子的結(jié)點(diǎn)，即葉子即度不為即度不為0的結(jié)點(diǎn)（也稱為非終端結(jié)點(diǎn)）的結(jié)點(diǎn)（也稱為非終端結(jié)點(diǎn)）所有結(jié)點(diǎn)度中的最

5、大值（所有結(jié)點(diǎn)度中的最大值（Max各結(jié)點(diǎn)的度各結(jié)點(diǎn)的度）指所有結(jié)點(diǎn)中最大的層數(shù)（指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次各結(jié)點(diǎn)的層次）問：問：右上圖中的結(jié)點(diǎn)數(shù)右上圖中的結(jié)點(diǎn)數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4（有幾個(gè)直接后繼就是幾度，亦稱（有幾個(gè)直接后繼就是幾度，亦稱“次數(shù)次數(shù)”）ABCGEIDHFJFLK數(shù)據(jù)結(jié)構(gòu)樹與二叉樹11一對多（一對多（1:n1:n），），有多個(gè)直接后繼（如家譜樹、有多個(gè)直接后繼（如家譜樹、目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，且目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹子樹之間互不相交之間互不相交。 討論討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？樹是非線性

6、結(jié)構(gòu)，該怎樣存儲？特點(diǎn)：特點(diǎn)：仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健Ｈ匀挥许樞虼鎯?、鏈?zhǔn)酱鎯Φ确绞健?數(shù)據(jù)結(jié)構(gòu)樹與二叉樹125.2 5.2 二叉樹二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “ “叉叉” ” 的樹？的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)； 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性?？梢宰C明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)（二叉樹的運(yùn)算見（二叉樹的運(yùn)算見5.3節(jié)）節(jié)）數(shù)據(jù)結(jié)構(gòu)樹與二叉樹13定義：定義：是是

7、n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:2） 基本特征基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。 基本形態(tài)：基本形態(tài)：一般的一般的樹有幾樹有幾種？種？數(shù)據(jù)結(jié)構(gòu)樹與二叉樹14討論討論1 1：第：第i i層的結(jié)點(diǎn)數(shù)最多是多少？層的結(jié)點(diǎn)數(shù)最多是多少？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制

8、性質(zhì)可輕松求出） 性質(zhì)性質(zhì)1: 1: 性質(zhì)性質(zhì)2: 2: 再提問：第再提問：第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？1 1討論討論2 2：深度為：深度為k k的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出）數(shù)據(jù)結(jié)構(gòu)樹與二叉樹15討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結(jié)點(diǎn)數(shù)有度的結(jié)點(diǎn)數(shù)有n n2 2個(gè)，個(gè)，則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0

9、=n2+1）二叉樹中全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)2 2度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)) )二叉樹中全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)nB+1 ( ( 總分支數(shù)根結(jié)點(diǎn)總分支數(shù)根結(jié)點(diǎn) ) ) （除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）總分支數(shù)總分支數(shù)B= n1+2n2 (1(1度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有1 1個(gè)直接后繼，個(gè)直接后繼，2 2度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有2 2個(gè)個(gè)) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1數(shù)據(jù)結(jié)構(gòu)樹與二叉樹162.2.深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為深度為的二叉

10、樹的結(jié)點(diǎn)總數(shù)，最多為 個(gè)。個(gè)。 ) )k-1k-1 ) log) log2 2k k ) ) k k ) )k k1. 1. 樹中各結(jié)點(diǎn)的度的最大值稱為樹的樹中各結(jié)點(diǎn)的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度DCC3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 ) )9 9 ) )8 8 ) ) ) )9 91 1課堂練習(xí)：課堂練習(xí)：數(shù)據(jù)結(jié)構(gòu)樹與二叉樹17滿二叉樹：滿二叉樹：一棵深度為一棵深度為k 且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。 （特點(diǎn)：每層都（特點(diǎn)：每層都“充滿充滿”了結(jié)點(diǎn)）了結(jié)點(diǎn)）完全二

11、叉樹：完全二叉樹：深度為深度為k 的的、有有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為深度為k 的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結(jié)的結(jié)點(diǎn)一一對應(yīng)。點(diǎn)一一對應(yīng)。AOBCGEKDJFIHNML深度為深度為4 4的滿二叉樹的滿二叉樹完全二叉樹完全二叉樹ABCGEIDHFJ為何要研究為何要研究這兩種特殊這兩種特殊形式？形式？完全二叉樹的特點(diǎn)是只有最后一層葉子不滿，完全二叉樹的特點(diǎn)是只有最后一層葉子不滿，且全部集中在左邊。但這其實(shí)是且全部集中在左邊。但這其實(shí)是順序二叉樹順序二叉樹的含義。而的含義。而圖論圖論中的中的“完全二叉樹完全二叉樹”是指是

12、指n1=0的情況。的情況。因?yàn)樗鼈冊陧樞虼鎯σ驗(yàn)樗鼈冊陧樞虼鎯Ψ绞较驴梢詮?fù)原！方式下可以復(fù)原！數(shù)據(jù)結(jié)構(gòu)樹與二叉樹18對于兩種特殊形式的二叉樹（對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹）, ,還特別具備以下還特別具備以下2 2個(gè)性質(zhì)：個(gè)性質(zhì)：證明：證明：根據(jù)性質(zhì)根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個(gè)結(jié)點(diǎn)，且個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點(diǎn)數(shù)的總結(jié)點(diǎn)數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，層滿二叉樹容量之間

13、，即即2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n2n2k k三邊同時(shí)取對數(shù)，于是有：三邊同時(shí)取對數(shù)，于是有：k-1logk-1log2 2nk n1)f=n*fact(n-1); else f=1; return(f); 用遞歸形式格外簡單！用遞歸形式格外簡單！回憶回憶1 1：二叉樹結(jié)點(diǎn)二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義：的數(shù)據(jù)類型定義：則三種遍歷算法可寫出則三種遍歷算法可寫出: :數(shù)據(jù)結(jié)構(gòu)樹與二叉樹28LDR(node *root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rc

14、hild); return(0);LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; DLR( node *root )if (root !=NULL) /非空二叉樹非空二叉樹 printf(“%d”,root-data); /訪問訪問D DDLR(root-lchild); /遞歸遍歷左子樹遞歸

15、遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 數(shù)據(jù)結(jié)構(gòu)樹與二叉樹29對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過上，每個(gè)結(jié)點(diǎn)經(jīng)過3次次。AFEDCBG第第1次次經(jīng)過時(shí)訪問，是經(jīng)過時(shí)

16、訪問，是先根先根遍歷遍歷第第2次次經(jīng)過時(shí)訪問，是經(jīng)過時(shí)訪問，是中根中根遍歷遍歷第第3次次經(jīng)過時(shí)訪問，是經(jīng)過時(shí)訪問，是后根后根遍歷遍歷2. 2. 二叉樹遍歷的時(shí)間效率和空間效率二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率時(shí)間效率: : /每個(gè)結(jié)點(diǎn)只訪問一次每個(gè)結(jié)點(diǎn)只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間精確值：樹深為精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個(gè)輔助單元個(gè)輔助單元數(shù)據(jù)結(jié)構(gòu)樹與二叉樹30用空格字符表示用空格字符表示無孩子無孩子或指針或指針為空為空注：注：要實(shí)現(xiàn)遍歷運(yùn)算，必須先把二叉樹存入電腦內(nèi)要實(shí)現(xiàn)遍歷運(yùn)算，必須先把二叉樹存入電腦內(nèi)怎樣

17、建樹？怎樣建樹？例：將下面的二叉樹以二叉鏈表形式存入計(jì)算例：將下面的二叉樹以二叉鏈表形式存入計(jì)算機(jī)內(nèi)。機(jī)內(nèi)?？紤]考慮1 1：輸入結(jié)點(diǎn)時(shí)怎樣表示輸入結(jié)點(diǎn)時(shí)怎樣表示“無孩子無孩子”？考慮考慮2 2：以何種遍歷方式來輸入和建樹？以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：將二叉樹按先序遍歷次序輸入：A B C D E G F 以先序遍歷最為合適，以先序遍歷最為合適，讓每個(gè)結(jié)點(diǎn)都能及時(shí)讓每個(gè)結(jié)點(diǎn)都能及時(shí)被連接到位。被連接到位。數(shù)據(jù)結(jié)構(gòu)樹與二叉樹31建樹算法：建樹算法：Status CreateBiTree( BiTree &T ) /構(gòu)造二叉樹構(gòu)造二叉樹T Tscanf(“%c”,

18、&ch);if(ch=)T=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹構(gòu)造右子樹 return OK; /CreateBiTree輸入序列：輸入序列： A B C D E G F 數(shù)據(jù)結(jié)構(gòu)樹與二叉樹32問：問：用二叉鏈表法（用二叉鏈表法（l_child, r_child）存儲包含）存儲包含n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的

19、指針區(qū)域中會有多少個(gè)二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有多少個(gè)空空指針？指針？思考：思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？ 我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。線索，以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個(gè)個(gè)。分析：分析：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n個(gè)鏈域個(gè)鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。除根結(jié)點(diǎn)外，二叉樹中每

20、一個(gè)結(jié)點(diǎn)除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親有且僅有一個(gè)雙親（直接前驅(qū)），所以只會有（直接前驅(qū)），所以只會有n n1 1個(gè)結(jié)點(diǎn)的鏈域存放指針，指個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。向非空子女結(jié)點(diǎn)（即直接后繼）。數(shù)據(jù)結(jié)構(gòu)樹與二叉樹33思考：思考：二叉鏈表空間效率這么低，能否利用這些空二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？閑區(qū)存放有用的信息或線索？我們可以用它來存放當(dāng)前結(jié)點(diǎn)的我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后直接前驅(qū)和后繼繼等線索，以加快查找速度。等線索，以加快查找速度。用二叉鏈表法存儲包含用二叉鏈表法存儲包含n n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的

21、指個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有針區(qū)域中會有n+1n+1個(gè)空指針。個(gè)空指針。這就是這就是線索二叉樹線索二叉樹（Threaded Binary Tree）數(shù)據(jù)結(jié)構(gòu)樹與二叉樹345.4 線索二叉樹線索二叉樹（Threaded Binary Tree）二叉樹中容易找到結(jié)點(diǎn)的二叉樹中容易找到結(jié)點(diǎn)的左右孩子左右孩子信息，但該結(jié)點(diǎn)的直信息，但該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在某種遍歷過程中接前驅(qū)和直接后繼只能在某種遍歷過程中動態(tài)動態(tài)獲得。獲得。先依先依遍歷規(guī)則遍歷規(guī)則把每個(gè)結(jié)點(diǎn)對應(yīng)的把每個(gè)結(jié)點(diǎn)對應(yīng)的前驅(qū)前驅(qū)和和后繼線索后繼線索預(yù)存預(yù)存起起來，這叫做來，這叫做“線索化線索化”。意義：從意義：從任一結(jié)點(diǎn)任

22、一結(jié)點(diǎn)出發(fā)都能快速找到其前驅(qū)和后繼，且出發(fā)都能快速找到其前驅(qū)和后繼，且不必借助堆棧。不必借助堆棧。 對二叉樹進(jìn)行某種遍歷之后，將得到一個(gè)線性有序的序列。對二叉樹進(jìn)行某種遍歷之后，將得到一個(gè)線性有序的序列。例如對某二叉樹的例如對某二叉樹的中序遍歷中序遍歷結(jié)果是結(jié)果是B D C E A F H GB D C E A F H G，意味著，意味著已將該樹轉(zhuǎn)為線性排列，顯然其中結(jié)點(diǎn)已將該樹轉(zhuǎn)為線性排列，顯然其中結(jié)點(diǎn)具有唯一前驅(qū)和唯一后具有唯一前驅(qū)和唯一后繼。繼。在此前提下，那在此前提下，那n+1個(gè)空鏈域才可能裝得下個(gè)空鏈域才可能裝得下“線索線索”。討論討論1 1：二叉樹是二叉樹是1:21:2的非線性結(jié)構(gòu)

23、，其直接后繼可能不止一的非線性結(jié)構(gòu)，其直接后繼可能不止一個(gè)，如何存放？個(gè)，如何存放？討論討論2.2.如何獲得這種如何獲得這種“直接前驅(qū)直接前驅(qū)”或或“直接后繼直接后繼”？有何意？有何意義？義？數(shù)據(jù)結(jié)構(gòu)樹與二叉樹35 每個(gè)結(jié)點(diǎn)增加兩個(gè)域：每個(gè)結(jié)點(diǎn)增加兩個(gè)域：fwd和和bwd；存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預(yù)存這類信息？有兩種解決方法：如何預(yù)存這類信息？有兩種解決方法： 與原有的左右孩子指針域與原有的左右孩子指針域“復(fù)用復(fù)用”，充分利用那，充分利用那n+1個(gè)空鏈域。個(gè)空鏈域。規(guī)規(guī) 定：定：1）若結(jié)點(diǎn)有左子樹，則）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；指向其左孩子； 否則

24、，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點(diǎn)有右子樹，則）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則，rchild指向其直接后繼指向其直接后繼(即線索即線索) 。datalchildrchildfwdbwddatalchildrchild缺點(diǎn)：空間效率太低！缺點(diǎn)：空間效率太低！問題：計(jì)算機(jī)如何問題：計(jì)算機(jī)如何判斷是孩子指針還判斷是孩子指針還是線索指針？是線索指針？如何區(qū)別？如何區(qū)別？數(shù)據(jù)結(jié)構(gòu)樹與二叉樹36lchildLTagdataRTag rchild約定約定:當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示正常正常情況情況;當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?/p>

25、1時(shí)時(shí),表示表示線索線索情況情況.前驅(qū)前驅(qū)(后繼后繼)左左(右右)孩子孩子為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：問：問：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整個(gè)樹。堆棧（遞歸）也能遍歷整個(gè)樹。各各1bit1bit數(shù)據(jù)結(jié)構(gòu)樹與二叉樹371. 有關(guān)線索二叉樹的幾個(gè)術(shù)語：有關(guān)線索二叉樹的幾個(gè)術(shù)語： 線索鏈表：線索鏈表： 線線 索：索：線索二叉樹：線索二叉樹： 線線 索索 化：化：用用含含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表的結(jié)點(diǎn)樣式所構(gòu)成的二叉

26、鏈表指向結(jié)點(diǎn)前驅(qū)和后繼的指針指向結(jié)點(diǎn)前驅(qū)和后繼的指針加上線索的二叉樹加上線索的二叉樹對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索使其變?yōu)榫€索二叉樹的過程二叉樹的過程yyyyyy線索化過程就是在遍歷過程中修改空指針的過程：線索化過程就是在遍歷過程中修改空指針的過程：將空的將空的lchildlchild改為結(jié)點(diǎn)的直接前驅(qū)；改為結(jié)點(diǎn)的直接前驅(qū)；將空的將空的rchildrchild改為結(jié)點(diǎn)的直接后繼。改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況正常情況”）數(shù)據(jù)結(jié)構(gòu)樹與二叉樹38dataAGEIDJHCFBltag0011110101rt

27、ag0001010111AGEIDJHCFB例：例：帶了帶了兩個(gè)標(biāo)志兩個(gè)標(biāo)志的某的某先序遍歷先序遍歷結(jié)果如下表所示，結(jié)果如下表所示，請畫出對應(yīng)的二叉樹。請畫出對應(yīng)的二叉樹。A數(shù)據(jù)結(jié)構(gòu)樹與二叉樹39ABCGEIDHFroot懸空？懸空？ NILNIL懸空？懸空？ NILNIL解：解：對該二叉樹中序遍歷的結(jié)果為對該二叉樹中序遍歷的結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)一個(gè)頭結(jié)點(diǎn)例例1 1：畫出以下二叉樹對應(yīng)的畫出以下二叉樹對應(yīng)的中序中序線索二叉樹。線索二叉樹。

28、2. 2. 線索二叉樹的生成線索二叉樹的生成線索化線索化線索化過程就是在遍歷過線索化過程就是在遍歷過程中修改空指針的過程程中修改空指針的過程數(shù)據(jù)結(jié)構(gòu)樹與二叉樹4000A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：數(shù)據(jù)結(jié)構(gòu)樹與二叉樹41線索二叉樹的生成算法線索二叉樹的生成算法（遞歸算法見教材）遞歸算法見教材）實(shí)質(zhì)：實(shí)質(zhì)：在遍歷二叉樹的過程中修改空指針，添加前驅(qū)或后繼在遍歷二叉樹的過程中修改空指針，添加前驅(qū)

29、或后繼的線索，使之成為線索二叉樹。的線索，使之成為線索二叉樹。為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，需要設(shè)置兩個(gè)指針：為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，需要設(shè)置兩個(gè)指針：p指針指針當(dāng)前結(jié)點(diǎn)之指針；當(dāng)前結(jié)點(diǎn)之指針；pre指針指針當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)指針。當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)指針。設(shè)計(jì)技巧設(shè)計(jì)技巧：依某種順序：依某種順序遍歷二叉樹，對每個(gè)結(jié)點(diǎn)遍歷二叉樹，對每個(gè)結(jié)點(diǎn)p，判斷其左指，判斷其左指針是否為空，以及其針是否為空，以及其前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的右指針是否為空。右指針是否為空。每次只修改前驅(qū)結(jié)點(diǎn)的右指針（后繼）和本結(jié)點(diǎn)的左指針（前每次只修改前驅(qū)結(jié)點(diǎn)的右指針（后繼）和本結(jié)點(diǎn)的左指針（前驅(qū)），參見算法。

30、驅(qū)），參見算法。若若p-lchildNULL, ,則則p-Ltag=1;p-Ltag=1;p-lchildp-lchildpre;pre; /p/p的前驅(qū)線索應(yīng)存的前驅(qū)線索應(yīng)存p p結(jié)點(diǎn)的左邊結(jié)點(diǎn)的左邊若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;1;pre-rchild=ppre-rchild=p; /pre /pre的后繼線索應(yīng)存的后繼線索應(yīng)存prepre結(jié)點(diǎn)的右邊結(jié)點(diǎn)的右邊數(shù)據(jù)結(jié)構(gòu)樹與二叉樹423. 3. 線索二叉樹的遍歷線索二叉樹的遍歷（無需堆棧）（無需堆棧）對于線索二叉樹的遍歷，只要找到序列中的對于線索二叉樹的遍歷，只要找到序列中的第一個(gè)第一個(gè)結(jié)結(jié)點(diǎn)，然

31、后點(diǎn)，然后依次訪問結(jié)點(diǎn)的后繼依次訪問結(jié)點(diǎn)的后繼直到后繼為空為止。直到后繼為空為止。（因?yàn)榻⒕€索時(shí)已遍歷一次，相當(dāng)于線性化了?。ㄒ?yàn)榻⒕€索時(shí)已遍歷一次，相當(dāng)于線性化了?。╇y點(diǎn)：難點(diǎn)：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，直接找到其后繼的，當(dāng)標(biāo)志為當(dāng)標(biāo)志為0 0時(shí)，則需要通過一時(shí)，則需要通過一定運(yùn)算才能找到它的后繼。定運(yùn)算才能找到它的后繼。以以中根線索二叉樹中根線索二叉樹為例：為例：當(dāng)當(dāng)RTag=1時(shí)，直接后繼指針就在其時(shí)，直接后繼指針就在其rchild域內(nèi)；域內(nèi)；當(dāng)當(dāng)RTag=0時(shí)，直接后繼是當(dāng)前結(jié)點(diǎn)時(shí)，直接后繼是當(dāng)前結(jié)點(diǎn)的結(jié)點(diǎn)的結(jié)點(diǎn)；請

32、注意中序遍歷規(guī)則是請注意中序遍歷規(guī)則是LDR，數(shù)據(jù)結(jié)構(gòu)樹與二叉樹435.5 樹和森林1.樹和森林的存儲方式樹和森林的存儲方式2.樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換3. 樹和森林的遍歷樹和森林的遍歷數(shù)據(jù)結(jié)構(gòu)樹與二叉樹441. 1. 樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 1 1、用雙親表示法存儲、用雙親表示法存儲思路：思路：用一組用一組連續(xù)空間連續(xù)空間來存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)來存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中結(jié)點(diǎn)中附設(shè)一個(gè)指示器附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在鏈表中的，指示

33、其雙親結(jié)點(diǎn)在鏈表中的位置。位置。parentdata結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)dataparent1樹結(jié)構(gòu)樹結(jié)構(gòu) 23n數(shù)據(jù)結(jié)構(gòu)樹與二叉樹45RABCDEFGHK-1000例例1: 雙親表示法雙親表示法缺點(diǎn)：求結(jié)點(diǎn)的孩子缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)時(shí)需要遍歷整個(gè)結(jié)構(gòu)1136668976543210數(shù)據(jù)結(jié)構(gòu)樹與二叉樹46思路：思路：對對n n個(gè)結(jié)點(diǎn)分別設(shè)立個(gè)結(jié)點(diǎn)分別設(shè)立n n個(gè)孩子鏈表，結(jié)點(diǎn)為個(gè)孩子鏈表，結(jié)點(diǎn)為表頭；表頭； 再將再將n n個(gè)表頭用數(shù)組存放個(gè)表頭用數(shù)組存放起來，形成一個(gè)起來，形成一個(gè)混合結(jié)構(gòu)混合結(jié)構(gòu)。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表

34、示法存儲、用孩子表示法存儲bc數(shù)據(jù)結(jié)構(gòu)樹與二叉樹47思路：思路：用二叉鏈表用二叉鏈表來表示樹，但鏈表中的兩個(gè)指針來表示樹，但鏈表中的兩個(gè)指針域含義不同。域含義不同。 左指針指向該結(jié)點(diǎn)的第一個(gè)孩子；左指針指向該結(jié)點(diǎn)的第一個(gè)孩子； 右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild3 3、用孩子、用孩子兄弟表示法存儲兄弟表示法存儲指向左孩子指向左孩子指向右兄弟指向右兄弟數(shù)據(jù)結(jié)構(gòu)樹與二叉樹48abecdfhgbacedfgh問：問：樹樹二叉樹的二叉樹的“連線連線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)” ” 如如何由計(jì)算機(jī)自動實(shí)現(xiàn)？何由計(jì)算機(jī)自動實(shí)現(xiàn)？答：

35、答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。例如例如：數(shù)據(jù)結(jié)構(gòu)樹與二叉樹492. 樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：step1: step1: 將樹中同一結(jié)點(diǎn)的兄弟相連將樹中同一結(jié)點(diǎn)的兄弟相連; ;加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)討論討論1 1：樹如何轉(zhuǎn)為二叉樹？：樹如何轉(zhuǎn)為二叉樹？孩子孩子兄弟兄弟表示法表示法step2: step2: 保留結(jié)點(diǎn)的最左孩子連線，保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；刪除其它孩子連線；step3: step3: 將同一孩子的連線繞左孩子將同一孩子的連線繞左孩子旋轉(zhuǎn)旋轉(zhuǎn)4545度角。度角。數(shù)據(jù)結(jié)構(gòu)樹與二叉樹50

36、方法：方法：加加線線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例：樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左數(shù)據(jù)結(jié)構(gòu)樹與二叉樹51討論討論2 2：二叉樹怎樣還原為樹？：二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽∧娌僮?，把所有右孩子變?yōu)樾值埽?abdefhgic數(shù)據(jù)結(jié)構(gòu)樹與二叉樹52法一：法一： 各森林先各自轉(zhuǎn)為二叉樹；各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個(gè)二叉樹的右子樹上。依次連到前一個(gè)二叉樹的右子樹上。討論討論3 3：森林如何轉(zhuǎn)為二叉樹？：森林如何轉(zhuǎn)為二叉樹？即即F=TF=T1 1, T, T2 2, ,T

37、, ,Tm m B=root, LB, RB B=root, LB, RB法二：法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材，兩種方法都有轉(zhuǎn)換示意圖）（參見教材，兩種方法都有轉(zhuǎn)換示意圖）法一和法二得到的二叉法一和法二得到的二叉樹是完全相同的、惟一樹是完全相同的、惟一的、的、數(shù)據(jù)結(jié)構(gòu)樹與二叉樹53ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉(zhuǎn)二叉樹舉例：森林轉(zhuǎn)二叉樹舉例：（采用法二）（采用法二）兄弟相連兄弟相連 長兄為父長兄為父頭樹為根頭樹為根 孩子靠左孩子靠左數(shù)據(jù)結(jié)構(gòu)樹與二叉樹54BCDEFGHJI討論討論4 4：二叉樹如何還原為森林？：二叉樹如何

38、還原為森林？要點(diǎn)：要點(diǎn)：把最右邊的子樹變?yōu)樯郑溆嘤易訕渥優(yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯?，其余右子樹變?yōu)樾值?即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, ,T, ,Tm m ABCDEFGHJIEFABCDGHJI數(shù)據(jù)結(jié)構(gòu)樹與二叉樹555.65.6 Huffman Huffman樹及其應(yīng)用樹及其應(yīng)用一、一、HuffmanHuffman樹樹二、二、HuffmanHuffman編碼編碼最優(yōu)二叉樹最優(yōu)二叉樹HuffmanHuffman樹樹HuffmanHuffman編碼編碼帶權(quán)路徑帶權(quán)路徑長度最短長度最短的樹的樹不等長編碼不等長編碼是通信是

39、通信中最經(jīng)中最經(jīng)典的壓典的壓縮編碼縮編碼數(shù)據(jù)結(jié)構(gòu)樹與二叉樹56一、最優(yōu)二叉樹一、最優(yōu)二叉樹（HuffmanHuffman樹）樹）路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權(quán)路徑長度帶權(quán)路徑長度：樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：HuffmanHuffman樹樹：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。路徑上的分支數(shù)目。從樹根到從樹根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長度之和。的路徑長度之和。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積（結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積（WPLWPL）若干術(shù)語：若干術(shù)語：debacf g樹中所有樹中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)

40、的帶權(quán)路徑長度之和的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。帶權(quán)路徑長度最小的樹。aeae的路徑長度的路徑長度樹長度樹長度2 21010HuffmanHuffman常譯為常譯為赫夫曼赫夫曼、霍夫曼霍夫曼、哈夫曼哈夫曼等等Weighted Path LengthWeighted Path Length數(shù)據(jù)結(jié)構(gòu)樹與二叉樹57樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度如何計(jì)算？如何計(jì)算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：經(jīng)典之例：WPL=WPL=WPL=Huffman樹是樹是WPL WPL 最小的樹最小的

41、樹樹中所有葉子結(jié)樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長點(diǎn)的帶權(quán)路徑長度之和度之和364635數(shù)據(jù)結(jié)構(gòu)樹與二叉樹581. 1. 構(gòu)造構(gòu)造Huffman樹的基本思想：樹的基本思想：設(shè)有設(shè)有4 4個(gè)字符個(gè)字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4， 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長編碼：等長編碼（如二進(jìn)制編碼）（如二進(jìn)制編碼）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，則：，則：WPLWPL1 12bit2bit(7(75 52 24 4）3636法

42、法2 2：不等長編碼：不等長編碼（如（如HuffmanHuffman編碼）編碼）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，則：，則：明確：要實(shí)現(xiàn)明確：要實(shí)現(xiàn)HuffmanHuffman編碼，就要先構(gòu)造編碼，就要先構(gòu)造HuffmanHuffman樹樹討論：討論：HuffmanHuffman樹有什么用？樹有什么用？權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。WPLWPL最小的樹最小的樹頻度高的信息頻度高的信息用短碼，反之用短碼，反之用長碼，傳輸用長碼，傳輸效率肯定高！效率肯定高！信息高效傳輸信息高效傳輸WPL

43、WPL2 2= =1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535數(shù)據(jù)結(jié)構(gòu)樹與二叉樹592. 2. 構(gòu)造構(gòu)造HuffmanHuffman樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：怎樣證明它就是怎樣證明它就是WPL最小的最優(yōu)二叉樹？最小的最優(yōu)二叉樹？ 參考參考信源編碼信源編碼數(shù)據(jù)結(jié)構(gòu)樹與二叉樹60step1step1：在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是合并中，總是合并當(dāng)前值最小當(dāng)前值最小的兩個(gè)權(quán)的兩個(gè)權(quán)具體操作步驟：具體操作步驟：a. 初始初始方框表示外結(jié)點(diǎn)方框表示外結(jié)點(diǎn)（葉子，字符）（葉子，字符）圓框

44、表示內(nèi)結(jié)點(diǎn)（合并圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）后的權(quán)值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 11數(shù)據(jù)結(jié)構(gòu)樹與二叉樹61step2step2：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=WPL=1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535（小于等長碼的（小于等長碼的WPL=36WPL=36）HuffmanHuffman編碼也編碼也HuffmanHuffman樹樹 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤數(shù)據(jù)結(jié)構(gòu)樹與二叉樹62二、二、HuffmanHuffman編碼編碼由于由于哈夫曼樹的哈夫曼樹的WPLWPL最小，說明編碼所需要的比特?cái)?shù)最少。這最小，說明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于