1、第6章 樹(shù)和二叉樹(shù)張成文張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院北京郵電大學(xué)計(jì)算機(jī)學(xué)院6.1 6.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)6.2 6.2 二叉樹(shù)的類(lèi)型定義二叉樹(shù)的類(lèi)型定義6.36.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4 6.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷6.5 6.5 線索二叉樹(shù)線索二叉樹(shù)6.6 6.6 樹(shù)和森林樹(shù)和森林6.7 6.7 樹(shù)和森林的遍歷樹(shù)和森林的遍歷6.9 6.9 哈夫曼樹(shù)與哈夫曼編碼哈夫曼樹(shù)與哈夫曼編碼主要內(nèi)容6.8 6.8 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)ABCDEFGHIJMKL例如例如: : 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)1.1.定義定義: : 樹(shù)樹(shù)是是n(n0)n(

2、n0)個(gè)結(jié)點(diǎn)的有限集合個(gè)結(jié)點(diǎn)的有限集合T T。當(dāng)。當(dāng)n=0n=0時(shí)時(shí), ,稱(chēng)為空樹(shù)稱(chēng)為空樹(shù); ;當(dāng)當(dāng)n0n0時(shí)時(shí), ,該集合滿(mǎn)足如下條件該集合滿(mǎn)足如下條件: : (1) (1) 其中必有一個(gè)稱(chēng)為根其中必有一個(gè)稱(chēng)為根(root)(root)的特定結(jié)點(diǎn)的特定結(jié)點(diǎn), ,它沒(méi)它沒(méi)有直接前驅(qū)有直接前驅(qū), ,但有零個(gè)或多個(gè)直接后繼。但有零個(gè)或多個(gè)直接后繼。 (2) (2) 其余其余n-1n-1個(gè)結(jié)點(diǎn)可以劃分成個(gè)結(jié)點(diǎn)可以劃分成m(m0)m(m0)個(gè)互不相個(gè)互不相交的有限集交的有限集T T1 1,T,T2 2,T,T3 3, ,T,Tm m, ,其中其中T Ti i又是一棵樹(shù)又是一棵樹(shù), ,稱(chēng)為稱(chēng)為根根roo

3、troot的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)接前驅(qū), ,但有零個(gè)或多個(gè)直接后繼。但有零個(gè)或多個(gè)直接后繼。 一、樹(shù)一、樹(shù)(tree)的基本概念的基本概念:ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹(shù)根例如例如: : (1). 樹(shù)型圖示樹(shù)型圖示 (2).嵌套集合嵌套集合 (3).凹入凹入(書(shū)目書(shū)目) (4). 廣義表廣義表(用根作為表的名字寫(xiě)在表的左邊用根作為表的名字寫(xiě)在表的左邊)ABCDEFGHIJKLMA - B - E - K - L - F - C - G - D - H

4、- M - I - J -2. 樹(shù)的表示法樹(shù)的表示法:線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無(wú)前驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )最后最后一個(gè)一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素 (無(wú)后繼無(wú)后繼)多個(gè)多個(gè)葉子結(jié)點(diǎn)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素 ( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)一個(gè)后繼后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素 ( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)多個(gè)后繼后繼) )對(duì)比對(duì)比樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的度結(jié)點(diǎn)所擁有的子樹(shù)的數(shù)目。葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)度為零的結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)。孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)結(jié)

5、點(diǎn)的子樹(shù)的根稱(chēng)為結(jié)點(diǎn)的孩子。分枝結(jié)點(diǎn)分枝結(jié)點(diǎn)3.3.樹(shù)的相關(guān)術(shù)語(yǔ)樹(shù)的相關(guān)術(shù)語(yǔ)DHIJM雙親雙親結(jié)點(diǎn)是其孩子的雙親。祖先祖先從樹(shù)根到雙親的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的祖先。子孫子孫以結(jié)點(diǎn)為根的子樹(shù)的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子孫。兄弟兄弟同一父母的所有孩子互稱(chēng)兄弟。層次（層次（level） 樹(shù)根為第一層，其孩子為第二層，孫子為第三層，以此類(lèi)推。DHIJM有序樹(shù)有序樹(shù)結(jié)點(diǎn)各子樹(shù)從左至右是有秩序的樹(shù)稱(chēng)為有序樹(shù)。無(wú)序樹(shù)無(wú)序樹(shù)結(jié)點(diǎn)各子樹(shù)沒(méi)有秩序的樹(shù)稱(chēng)為無(wú)序樹(shù)。深度深度樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度。DHIJM樹(shù)的結(jié)點(diǎn)數(shù)樹(shù)的結(jié)點(diǎn)數(shù)n和分支數(shù)和分支數(shù)b的關(guān)系是的關(guān)系是:abcdefghijb=n-1任何一棵非空樹(shù)是一個(gè)二

6、元組任何一棵非空樹(shù)是一個(gè)二元組 Tree = (root,F)其中其中:root 被稱(chēng)為根結(jié)點(diǎn)被稱(chēng)為根結(jié)點(diǎn) F 被稱(chēng)為子樹(shù)森林被稱(chēng)為子樹(shù)森林森林森林(forest):是是m(m0)棵互不棵互不相交的樹(shù)的集合相交的樹(shù)的集合ArootBCDEFGHIJMKLF二叉樹(shù)二叉樹(shù)1 二叉樹(shù)的定義與基本操作二叉樹(shù)的定義與基本操作定義定義： 滿(mǎn)足以下兩個(gè)條件的樹(shù)稱(chēng)做二叉樹(shù)滿(mǎn)足以下兩個(gè)條件的樹(shù)稱(chēng)做二叉樹(shù)(Binary Tree): （1）每個(gè)結(jié)點(diǎn)的度都不大于）每個(gè)結(jié)點(diǎn)的度都不大于2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。 二叉樹(shù)或?yàn)榭諛?shù)空樹(shù), 或是由一個(gè)根結(jié)點(diǎn)根結(jié)點(diǎn)加上

7、兩兩棵棵分別稱(chēng)為左子樹(shù)左子樹(shù)和右子樹(shù)右子樹(shù)的、互不交的互不交的二叉二叉樹(shù)樹(shù)組成。注意注意:二叉樹(shù)是有序樹(shù)有序樹(shù),它的子樹(shù)有左右之分。二叉樹(shù)的度數(shù)不超過(guò)二二叉樹(shù)的度數(shù)不超過(guò)二,但度數(shù)不超過(guò)二的樹(shù)但度數(shù)不超過(guò)二的樹(shù)未必是二叉樹(shù)。未必是二叉樹(shù)。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)二叉樹(shù)的五種基本形態(tài)二叉樹(shù)的五種基本形態(tài):N空樹(shù)空樹(shù)只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左右子左右子樹(shù)均非樹(shù)均非空樹(shù)空樹(shù)用歸納法證明用歸納法證明: 歸納基歸納基: 歸納假設(shè)歸納假設(shè): 歸納證明歸納證明:i = 1 層時(shí)層時(shí),只有一個(gè)根結(jié)點(diǎn)只有一個(gè)根結(jié)點(diǎn): 2i-1 =

8、 20 = 1 命題成立命題成立;假設(shè)假設(shè) i-1 命題成立命題成立,即即: 第第i-1層至多有結(jié)點(diǎn)層至多有結(jié)點(diǎn)= 2i-1-1 = 2i-2 個(gè)個(gè); 二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù),則則第第i 層至多有結(jié)點(diǎn)層至多有結(jié)點(diǎn) = 2i-2 2 = 2i-1 個(gè)。個(gè)。2 二叉樹(shù)的重要特性二叉樹(shù)的重要特性性質(zhì)性質(zhì)1 :二叉樹(shù)第二叉樹(shù)第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。證明證明: 基于性質(zhì)基于性質(zhì)1, 深度為深度為 k 的二叉樹(shù)上的結(jié)點(diǎn)總數(shù)的的二叉樹(shù)上的結(jié)點(diǎn)總數(shù)的最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加，所以最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加，所以深度為深度

9、為 k 的二叉樹(shù)上含的二叉樹(shù)上含 結(jié)點(diǎn)數(shù)至多為：結(jié)點(diǎn)數(shù)至多為： 20+21+ +2k-1 = 2k-1 性質(zhì)性質(zhì) 2 : 深度為深度為 k 的二叉樹(shù)上至多含的二叉樹(shù)上至多含 2k-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)。證明證明:設(shè)設(shè) 二叉樹(shù)上結(jié)點(diǎn)總數(shù)：二叉樹(shù)上結(jié)點(diǎn)總數(shù)： n = n0 + n1 + n2再根據(jù)樹(shù)的性質(zhì)：再根據(jù)樹(shù)的性質(zhì)： b = n-1 = n0 + n1 + n2 - 1由有二叉樹(shù)分支總數(shù)：由有二叉樹(shù)分支總數(shù)： b = n1+2n2兩式右邊相等得兩式右邊相等得: n0 = n2 + 1 。性質(zhì)性質(zhì) 3 : 對(duì)任何一棵二叉樹(shù)對(duì)任何一棵二叉樹(shù),若它含有若它含有n0 個(gè)葉子結(jié)點(diǎn)、個(gè)葉子結(jié)點(diǎn)、n2

10、 個(gè)個(gè)度為度為 2 的結(jié)點(diǎn)的結(jié)點(diǎn), 則必存在關(guān)系式則必存在關(guān)系式:n0 = n2+1。也可以用歸納法證明也可以用歸納法證明兩類(lèi)兩類(lèi)特殊特殊的二叉樹(shù)的二叉樹(shù)滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)完全二叉樹(shù)完全二叉樹(shù) 滿(mǎn)二叉樹(shù) 在一個(gè)二叉樹(shù)中，若第i層的結(jié)點(diǎn)數(shù)為2i-1，則稱(chēng)此層的結(jié)點(diǎn)數(shù)是滿(mǎn)的，當(dāng)樹(shù)中的每一層都是滿(mǎn)的，則稱(chēng)此二叉樹(shù)為滿(mǎn)二叉樹(shù)。 即如果一個(gè)二叉樹(shù)中，除最下一層的各結(jié)點(diǎn)度數(shù)為0以外，其它各層結(jié)點(diǎn)的度數(shù)均等于2，則此二叉樹(shù)為滿(mǎn)二叉樹(shù)。 滿(mǎn)二叉樹(shù)的第一層有一個(gè)結(jié)點(diǎn)（即根結(jié)點(diǎn)），第二層有兩個(gè)結(jié)點(diǎn)，依此類(lèi)推。每一層的結(jié)點(diǎn)數(shù)都是上一層結(jié)點(diǎn)數(shù)的二倍。所以，在滿(mǎn)二叉樹(shù)的第i層共有2i-1個(gè)結(jié)點(diǎn)（i1），一個(gè)深度為h的滿(mǎn)二

11、叉樹(shù)的結(jié)點(diǎn)總數(shù)為2h-1。滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù): 深度為深度為 k 且含有且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)?？蓮母鶄€(gè)結(jié)點(diǎn)的二叉樹(shù)?？蓮母鸢磳幼陨系较聫淖笾劣覍?duì)結(jié)點(diǎn)連續(xù)編號(hào)。起按層自上到下從左至右對(duì)結(jié)點(diǎn)連續(xù)編號(hào)。123456789 10 11 12 13 14 15 完全二叉樹(shù) 如果一個(gè)二叉樹(shù)各層都是“滿(mǎn)”的，只是最下面一層從右邊起連續(xù)缺n個(gè)結(jié)點(diǎn)，這種二叉樹(shù)叫做完全二叉樹(shù)。 例如上圖的滿(mǎn)二叉樹(shù)，如果缺少?gòu)牡?1號(hào)至第15號(hào)結(jié)點(diǎn)，就是一個(gè)完全二叉樹(shù)。 設(shè)完全二叉樹(shù)的結(jié)點(diǎn)數(shù)為n，它與樹(shù)的深度之間的關(guān)系為： 2h-1-11，則其父結(jié)點(diǎn)編號(hào)為 。 2) 如果2in，則其左兒子結(jié)點(diǎn)編號(hào)為2i；若2in，則無(wú)左兒

12、子結(jié)點(diǎn)。 3) 如果（2i+1）n，則其右兒子結(jié)點(diǎn)編號(hào)為（2i+1）；反之，則無(wú)右兒子結(jié)點(diǎn)。2/ i完全二叉樹(shù)完全二叉樹(shù): 樹(shù)中所含的樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)中個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)中編號(hào)為編號(hào)為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。一一對(duì)應(yīng)。abcdefghij 性質(zhì)性質(zhì) 4 : 具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n +1 。證明證明: 設(shè)完全二叉樹(shù)的深度為設(shè)完全二叉樹(shù)的深度為 k 則根據(jù)性質(zhì)則根據(jù)性質(zhì)2得得 2k-1 -1 n 2k -1 則則 2k-1 n 2k 即即 k-1 log2 n 1 ,分兩種情況討論分兩種情況討論: (1) 設(shè)第設(shè)第

13、k (1k log2n )層第層第1個(gè)結(jié)點(diǎn)為個(gè)結(jié)點(diǎn)為 i,則則 i=2k-1其左其左孩子必為第孩子必為第k+1層第層第1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),編號(hào)為編號(hào)為2k =2i,若若2in則無(wú)則無(wú)左孩子左孩子;其右孩子必為第其右孩子必為第k+1層第層第2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), 編號(hào)為編號(hào)為2i+1,若若2i+1n 則無(wú)右孩子。則無(wú)右孩子。 (2) 設(shè)第設(shè)第k (1k log2n )層某個(gè)結(jié)點(diǎn)為層某個(gè)結(jié)點(diǎn)為i (2k-1i data); -data); /訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) PreOrderPreOrder(bt-LChild(bt-LChild); ); /遍歷左子樹(shù)遍歷左子樹(shù) PreOrderPreOrder(bt

14、-RChild(bt-RChild); ); /遍歷右子樹(shù)遍歷右子樹(shù) 2) 2) 中序遍歷中序遍歷void void InOrderInOrder(BiTree bt(BiTree bt) ) / /* *中序遍歷根指針為中序遍歷根指針為btbt的二叉樹(shù)的二叉樹(shù)* */ / if(bt if(bt!=NULL)!=NULL) InOrderInOrder(bt-LChild(bt-LChild); ); /遍歷左子樹(shù)遍歷左子樹(shù)Visit(btVisit(bt-data); -data); /訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)InOrderInOrder(bt-RChild(bt-RChild); ); /遍

15、歷右子樹(shù)遍歷右子樹(shù) 3) 3) 后序遍歷后序遍歷void void PostOrderPostOrder(BiTree bt(BiTree bt) ) / /* * 后序遍歷根指針為后序遍歷根指針為btbt的二叉樹(shù)的二叉樹(shù) * */ / if(bt if(bt!=NULL)!=NULL) PostOrderPostOrder(bt-LChild(bt-LChild); ); /遍歷左子樹(shù)遍歷左子樹(shù)PostOrderPostOrder(bt-RChild(bt-RChild); ); /遍歷右子樹(shù)遍歷右子樹(shù)Visit(btVisit(bt-data); -data); /訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) 按

16、層次遍歷的算法按層次遍歷的算法LevelOrderTraverse(BiTree T) if (T) InitQueue(Q); EnQueue(Q, T); /根結(jié)點(diǎn)的指針T入隊(duì)列 while ( ! QueueEmpty (Q) ) DeQueue(Q, p); /從隊(duì)頭取一個(gè)指針 Visit(p-data); if (p-lchild) EnQueue(Q, p-lchild); if (p-rchild) EnQueue(Q, p-rchild); /LevelOrderTraverseAB CD ETEABCD 利用遍歷結(jié)果確定二叉樹(shù)問(wèn)題 先序序列+中序序列 中序序列+后序序列 先序

17、序列+后序序列 (x) 利用遍歷結(jié)果確定二叉樹(shù)問(wèn)題思考：層序+先序/中序/后序 能否確定？如何做？ 僅知二叉樹(shù)的先序序列僅知二叉樹(shù)的先序序列 abcdefgabcdefg 不能唯一不能唯一確定一棵二叉樹(shù)確定一棵二叉樹(shù), ,如果如果同時(shí)同時(shí)已知二叉樹(shù)的中序序已知二叉樹(shù)的中序序列列 cbdaegfcbdaegf,則會(huì)如何？則會(huì)如何？ 由先序和中序序列確定由先序和中序序列確定二叉樹(shù)樹(shù)二叉樹(shù)的先序序列二叉樹(shù)的先序序列二叉樹(shù)的中序序列二叉樹(shù)的中序序列 左子樹(shù)左子樹(shù)左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)右子樹(shù)右子樹(shù)根根根根a b c d e f gc b d a e g f例如例如: :aab bccddeeffgg

18、abcdefg先序序列中序序列四四、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) (先序遍歷先序遍歷)2、求二叉樹(shù)的深度、求二叉樹(shù)的深度(后序遍歷后序遍歷)1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想算法基本思想: : 先序(或中序或后序)遍歷二叉樹(shù),在遍歷過(guò)程中查找葉子結(jié)點(diǎn),并計(jì)數(shù)。因此需在遍歷算法中增添一個(gè)“計(jì)數(shù)計(jì)數(shù)”的參的參數(shù)數(shù), ,并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為:若是葉子若是葉子, ,則計(jì)數(shù)器增則計(jì)數(shù)器增1 1。練習(xí)：練習(xí)：/ /* * LeafCount LeafCount保存葉子結(jié)點(diǎn)數(shù)目的全局變量保存葉子

19、結(jié)點(diǎn)數(shù)目的全局變量, ,調(diào)用之調(diào)用之前初始化值為前初始化值為0 0 * */ /void leaf(BiTreevoid leaf(BiTree root) root) if(root if(root!=NULL)!=NULL) leaf(root-LChild leaf(root-LChild);); leaf(root-RChild leaf(root-RChild);); if(root-LChild=NULL&root-RChild if(root-LChild=NULL&root-RChild=NULL)=NULL) LeafCount LeafCount+;+; 2

20、、求二叉樹(shù)的深度、求二叉樹(shù)的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹(shù)深度的定義可知從二叉樹(shù)深度的定義可知,二叉樹(shù)的深度二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加應(yīng)為其左、右子樹(shù)深度的最大值加1。按后序。按后序遍歷編寫(xiě)遍歷編寫(xiě)深度函數(shù)深度函數(shù), 先分別求得左、右子樹(shù)的先分別求得左、右子樹(shù)的深度深度,再將其中再將其中訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn)的操作改為的操作改為: 深度深度=左、右子樹(shù)深度最大值左、右子樹(shù)深度最大值+1 首先分析二叉樹(shù)的深度和它的左、右子首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。樹(shù)深度之間的關(guān)系。練習(xí)：練習(xí)：int PostDepth(BiTree btin

21、t PostDepth(BiTree bt) ) int int hl,hr,max; hl,hr,max; if(bt if(bt=NULL) return(0=NULL) return(0); /); /空樹(shù)返回空樹(shù)返回0 0 hl=PostDepth(bt-LChild hl=PostDepth(bt-LChild);/);/求左子樹(shù)的深度求左子樹(shù)的深度 hr=PostDepth(bt-RChildhr=PostDepth(bt-RChild);/);/求右子樹(shù)的深度求右子樹(shù)的深度 max=hlhr?hl:hrmax=hlhr?hl:hr; /; /求左右子樹(shù)深度較大者求左右子樹(shù)深度較大

22、者 return(max+1); / return(max+1); / 返回樹(shù)的深度返回樹(shù)的深度 后序遍歷求二叉樹(shù)的深度后序遍歷求二叉樹(shù)的深度abcdef 基本概念基本概念 如何對(duì)二叉樹(shù)線索化？如何對(duì)二叉樹(shù)線索化？ 查找結(jié)點(diǎn)查找結(jié)點(diǎn)p p的前驅(qū)的前驅(qū) / /后繼結(jié)點(diǎn)后繼結(jié)點(diǎn) 線索鏈表的遍歷算法線索鏈表的遍歷算法6.5 線索二叉樹(shù)線索二叉樹(shù)一、一、基本概念基本概念遍歷二叉樹(shù)的結(jié)果是得到結(jié)點(diǎn)線性序列。遍歷二叉樹(shù)的結(jié)果是得到結(jié)點(diǎn)線性序列。例如:先序先序序列序列: : A B C D E F G H K中序中序序列序列: : B D C A H G K F E后序后序序列序列: : D C B H K

23、 G F E A可用結(jié)點(diǎn)中可用結(jié)點(diǎn)中空指針域空指針域指向線性序列中的指向線性序列中的“前驅(qū)前驅(qū)”和和“后繼后繼”ABCDEFGHK練習(xí)：練習(xí)：與其相應(yīng)的二叉樹(shù),稱(chēng)作 “線索二叉樹(shù)線索二叉樹(shù)”包含 “線索” 的存儲(chǔ)結(jié)構(gòu),稱(chēng)作 “線索鏈表線索鏈表”先序先序序列:A B C D E F G H K D C B E D 利用結(jié)點(diǎn)中存儲(chǔ)null的指針域指針域指向該線性序列中的“前驅(qū)”和“后繼”, 該指針指針?lè)Q作“線索線索”。二叉樹(shù)中存null的指針域共有結(jié)點(diǎn)數(shù)+1個(gè)Ltag=0 LChild域指向其左子樹(shù)域指向其左子樹(shù)(指針指針 Link) Ltag=1 LChild域指向其域指向其“前驅(qū)前驅(qū)” (線索

24、線索 Thread) Rtag=0 RChild域指向其右子樹(shù)域指向其右子樹(shù)(指針指針 Link) Rtag=1 RChild域指向其域指向其“后繼后繼”(線索線索 Thread) 如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)構(gòu)成一個(gè)鏈表如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)構(gòu)成一個(gè)鏈表,該鏈表稱(chēng)作該鏈表稱(chēng)作“線索鏈表線索鏈表”。LChildLtagDataRtagRChild 為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下圖所示：點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下圖所示： 在中序遍歷過(guò)程中修改當(dāng)前結(jié)點(diǎn)的在中序遍歷過(guò)程中修改當(dāng)前結(jié)點(diǎn)的左、右空指針域左、右空指針域,以保存該結(jié)點(diǎn)

25、的以保存該結(jié)點(diǎn)的“前驅(qū)前驅(qū)”和和“后繼后繼”信息。此過(guò)程稱(chēng)為對(duì)二叉樹(shù)信息。此過(guò)程稱(chēng)為對(duì)二叉樹(shù)的線索化。遍歷過(guò)程中的線索化。遍歷過(guò)程中, 附設(shè)指針附設(shè)指針p指向指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)當(dāng)前訪問(wèn)的結(jié)點(diǎn), 指針指針pre指向它的前驅(qū)。指向它的前驅(qū)。二、如何對(duì)二叉樹(shù)線索化？二、如何對(duì)二叉樹(shù)線索化？ABCDEnullnull中序序列： BDAECvoid Inthread(BiTree btvoid Inthread(BiTree bt) ) /對(duì)對(duì)btbt進(jìn)行中序線索化進(jìn)行中序線索化/公有變量公有變量prepre始終指向剛訪問(wèn)過(guò)的結(jié)點(diǎn)始終指向剛訪問(wèn)過(guò)的結(jié)點(diǎn), ,初值為初值為NULLNULL if(bt if

26、(bt!=NULL)!=NULL) Inthread(bt-LChild Inthread(bt-LChild); ); /線索化左子樹(shù)線索化左子樹(shù) if(bt-LChildif(bt-LChild=NULL)=NULL) bt-Ltag=1; bt-LChile bt-Ltag=1; bt-LChile=pre; =pre; /置前驅(qū)線索置前驅(qū)線索 if(pre!=NULL & pre-RChildif(pre!=NULL & pre-RChild=NULL)=NULL) pre-Rtag=1; pre-RChild=bt pre-Rtag=1; pre-RChild=bt;

27、/置后繼線索置后繼線索 pre=btpre=bt； Inthread(bt-RChildInthread(bt-RChild); ); /線索化右子樹(shù)線索化右子樹(shù) （1）中序線索二叉樹(shù)）中序線索二叉樹(shù) p的后繼 若p-RTag=1，則p-rchild即為所求； 若p-RTag=0，則從其右子沿著左鏈走到LTag=1 的那個(gè)結(jié)點(diǎn)就是。 p的前驅(qū) 若p-LTag=1，則p-lchild即為所求； 若p-LTag=0，則從其左子沿著右鏈走到RTag=1 的那個(gè)結(jié)點(diǎn)就是。pL D RLDRLDR三、查找結(jié)點(diǎn)三、查找結(jié)點(diǎn)p的前驅(qū)的前驅(qū) /后繼結(jié)后繼結(jié)點(diǎn)點(diǎn)（2）后序線索二叉樹(shù)）后序線索二叉樹(shù) p的前驅(qū) 若

28、p-LTag=1，則p-lchild即為所求； 若p-LTag=0， 則若p-RTag=0， 則p-rchild即為所求 若p-RTag=1， 則p-lchild即為所求 p的后繼 與雙親結(jié)點(diǎn)有關(guān)，因二叉鏈表中沒(méi)有指向雙親結(jié)點(diǎn)的指針，就可能需通過(guò)二叉樹(shù)的后序遍歷才可確定，因而后序線索二叉樹(shù)在此問(wèn)題上并不比普通二叉樹(shù)有效。（3）先序線索二叉樹(shù)）先序線索二叉樹(shù) 與后序線索二叉樹(shù)對(duì)偶p中序線索二叉樹(shù)可以方便地查找一個(gè)結(jié)點(diǎn)的前驅(qū)中序線索二叉樹(shù)可以方便地查找一個(gè)結(jié)點(diǎn)的前驅(qū)/ /后繼結(jié)點(diǎn)。后繼結(jié)點(diǎn)。L R DLRD四、線索鏈表的遍歷算法四、線索鏈表的遍歷算法 由于在線索鏈表中添加了遍歷中得到的由于在線索鏈

29、表中添加了遍歷中得到的“前驅(qū)前驅(qū)”和和“后繼后繼”的信息的信息,從而簡(jiǎn)化了遍歷從而簡(jiǎn)化了遍歷的算法。的算法。 在線索樹(shù)上遍歷在線索樹(shù)上遍歷,只要先找到第一個(gè)結(jié)點(diǎn)只要先找到第一個(gè)結(jié)點(diǎn),然后依次找結(jié)點(diǎn)的后繼直到后繼為空時(shí)為止。然后依次找結(jié)點(diǎn)的后繼直到后繼為空時(shí)為止。例如例如: 對(duì)中序線索化鏈表的遍歷算法對(duì)中序線索化鏈表的遍歷算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) 在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼左子樹(shù)上處于左子樹(shù)上處于最左下最左下(ltag=1無(wú)左子樹(shù)無(wú)左子樹(shù))的結(jié)點(diǎn)。的結(jié)點(diǎn)。若若 rtag=1 無(wú)右子樹(shù)無(wú)右子樹(shù), 則為則為后繼線索所指結(jié)點(diǎn)后繼線索所指結(jié)點(diǎn);否則為否

30、則為對(duì)其右子樹(shù)進(jìn)行中序遍歷時(shí)的第一個(gè)結(jié)點(diǎn)。對(duì)其右子樹(shù)進(jìn)行中序遍歷時(shí)的第一個(gè)結(jié)點(diǎn)。 0 A A 0 0 B B 1 1 C C 1 1 D D 0 1 E E 1 bt遍歷中序線索樹(shù)遍歷中序線索樹(shù)6.6樹(shù)和森林樹(shù)和森林 樹(shù)轉(zhuǎn)換為二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù) 1)在兄弟間加一連線 2)對(duì)每一結(jié)點(diǎn)，去掉它與孩子的連線(最左子除外) 3)以根為軸心將整棵樹(shù)順時(shí)針轉(zhuǎn)450 A B C DE F G*ABECFDG特點(diǎn)：無(wú)右子樹(shù)左支是孩子右支是兄弟數(shù)據(jù)結(jié)構(gòu)-第六章 樹(shù)和二叉樹(shù)66森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù) 1)先將森林里的每一棵樹(shù)轉(zhuǎn)換成一棵二叉樹(shù) 2)從最后一棵樹(shù)開(kāi)始，把后一棵樹(shù)的作為前一棵樹(shù)的根的右子 A

31、 E G B C D F H I 二叉樹(shù)轉(zhuǎn)換為樹(shù)二叉樹(shù)轉(zhuǎn)換為樹(shù)/森林森林 ABEC F G D HI6.7樹(shù)和森林的遍歷樹(shù)和森林的遍歷一、樹(shù)的遍歷一、樹(shù)的遍歷: 有兩種搜索路徑有兩種搜索路徑先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷: 若樹(shù)不空若樹(shù)不空,則先訪問(wèn)根結(jié)點(diǎn)則先訪問(wèn)根結(jié)點(diǎn),然后依次先根然后依次先根遍歷各棵子樹(shù)。遍歷各棵子樹(shù)。 若樹(shù)不空若樹(shù)不空,則先依次后根遍歷各棵子樹(shù)則先依次后根遍歷各棵子樹(shù),然然后訪問(wèn)根結(jié)點(diǎn)。后訪問(wèn)根結(jié)點(diǎn)。ABCDFGEIHJ 先根遍歷時(shí)頂點(diǎn)的先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序訪問(wèn)次序:A B E H I J C D F G 后根遍歷時(shí)頂點(diǎn)的后根遍歷時(shí)頂點(diǎn)的訪

32、問(wèn)次序訪問(wèn)次序:H I J E B C F G D AABECDGHIJF 后根遍歷對(duì)應(yīng)二叉后根遍歷對(duì)應(yīng)二叉樹(shù)中序訪問(wèn)次序樹(shù)中序訪問(wèn)次序:H I J E B C F G D AABCDFGEIHJ1森林中第一棵樹(shù)森林中第一棵樹(shù)的根結(jié)點(diǎn)的根結(jié)點(diǎn); ;2森林中第一棵森林中第一棵樹(shù)的子樹(shù)森林樹(shù)的子樹(shù)森林; ;3森林中其它樹(shù)構(gòu)森林中其它樹(shù)構(gòu)成的森林。成的森林。森林由三部分構(gòu)成森林由三部分構(gòu)成: B C D E F GH I J1. 先序遍歷先序遍歷:二、二、森林的遍歷森林的遍歷 若森林不空若森林不空,則則訪問(wèn)訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷先序遍歷森林中第一棵樹(shù)的子樹(shù)森林森林

33、中第一棵樹(shù)的子樹(shù)森林;先序遍歷先序遍歷森林中森林中(除第一棵樹(shù)之外除第一棵樹(shù)之外)其其 余樹(shù)構(gòu)成的森林。余樹(shù)構(gòu)成的森林。即即:依次從左至右依次從左至右對(duì)森林中的對(duì)森林中的 每一棵樹(shù)每一棵樹(shù)進(jìn)行進(jìn)行先根遍歷先根遍歷。. 中序遍歷中序遍歷: 若森林不空若森林不空,則則中序遍歷中序遍歷森林中第一棵樹(shù)的子樹(shù)森林森林中第一棵樹(shù)的子樹(shù)森林;訪問(wèn)訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)森林中第一棵樹(shù)的根結(jié)點(diǎn);中序遍歷中序遍歷森林中森林中(除第一棵樹(shù)之外除第一棵樹(shù)之外)其其 余樹(shù)構(gòu)成的森林。余樹(shù)構(gòu)成的森林。即即:依次從左至右依次從左至右對(duì)森林中的對(duì)森林中的 每一棵樹(shù)每一棵樹(shù)進(jìn)行進(jìn)行后根遍歷后根遍歷。3. 后序遍歷后序遍歷:

34、 若森林不空若森林不空,則則后序遍歷后序遍歷森林中第一棵樹(shù)的子樹(shù)森林森林中第一棵樹(shù)的子樹(shù)森林;后序遍歷后序遍歷森林中森林中(除第一棵樹(shù)之外除第一棵樹(shù)之外)其其 余樹(shù)構(gòu)成的森林。余樹(shù)構(gòu)成的森林。訪問(wèn)訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷先序遍歷森林森林的訪問(wèn)次序的訪問(wèn)次序:A B C D E F G H I J中序遍歷中序遍歷森林森林的訪問(wèn)次序的訪問(wèn)次序:B C D A F E I H J G A E GB C D F H J IAEBCDFGHJI后序遍歷后序遍歷森林森林的訪問(wèn)次序的訪問(wèn)次序:D C B F I J H G E A 樹(shù)和森林的遍歷和二叉樹(shù)和森林的遍歷和二叉樹(shù)

35、遍歷的對(duì)應(yīng)關(guān)系樹(shù)遍歷的對(duì)應(yīng)關(guān)系 ？先根遍歷先根遍歷后根遍歷后根遍歷樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷后序遍歷后序遍歷后序遍歷后序遍歷6.8樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)多重鏈表表示法多重鏈表表示法 結(jié)點(diǎn)結(jié)構(gòu) data child1 child2 childm 數(shù)據(jù)域 指針域 (m: 樹(shù)的度)#define TREE_DEGREE 100typedef struct MultiTNode TElemType data; struct MultiTNode * ptrTREE_DEGREEMultiTNode, * Multi

36、Tree;雙親表示法雙親表示法 用順序存儲(chǔ)（一維數(shù)組）存儲(chǔ)樹(shù)的信息 結(jié)點(diǎn)序號(hào) data parent 0 A -1 1 B 0 2 C 0 3 D 2 4 E 2 5 F 20 A1 B 2 C3 D 4 E 5 F#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置和結(jié)點(diǎn)數(shù)PTree;孩子鏈表表示法孩子鏈表表示法 順序（一維數(shù)組）+單鏈表 結(jié)點(diǎn)下標(biāo) data firstc

37、hild 0 A 1 2 1 B 2 C 3 4 5 3 D 4 E 5 F #define MAX_TREE_SIZE 100typedef struct CTNode /孩子結(jié)點(diǎn) int child; struct CTNode * next；CTNode, * ChildPtr;typedef struct /向量結(jié)點(diǎn) TElemType data; ChildPtr firstchild;CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int r, n; /根的位置和結(jié)點(diǎn)數(shù)CTree;0 A1 B 2 C3 D 4 E 5 F結(jié)點(diǎn)結(jié)構(gòu) f

38、ch data nsib fch: 指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn) nsib: 指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)孩子兄弟表示法孩子兄弟表示法(二叉鏈表表示法二叉鏈表表示法) A B C D E FTA BC D E F 訪問(wèn)某個(gè)結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)訪問(wèn)某個(gè)結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)：從fch鏈找到第一個(gè)孩子，沿第一 個(gè)孩子的nsib鏈找第二個(gè)孩子， ，直至nsib鏈為空。typedef struct CSNode TElemType data; struct CSNode * fch,*nsib;CSNode, * CSTree ;帶右鏈的先根序表示法帶右鏈的先根序表示法主體順序按樹(shù)的先根序遍歷，右鏈指向兄弟。帶

39、左鏈的層次序列表示法帶左鏈的層次序列表示法A B E C D F G0 4 0 5 0 7 01 2 3 4 5 6 7A B C D E F G2 5 0 6 0 0 01 2 3 4 5 6 7主體順序按樹(shù)的層次遍歷，左鏈指向孩子。ABCEFGD6.9 哈夫曼樹(shù)與哈夫曼樹(shù)與 哈夫曼編碼哈夫曼編碼 電文的字符集電文的字符集(a,b,c,d,e),它們?cè)陔娢闹谐霈F(xiàn)它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為的頻度分別為(5,6,2,9,7)。問(wèn)：如何對(duì)字符集編碼，使得問(wèn)：如何對(duì)字符集編碼，使得譯碼時(shí)不會(huì)錯(cuò)譯碼時(shí)不會(huì)錯(cuò)電文總長(zhǎng)最短？電文總長(zhǎng)最短？ 例：電文字符編碼例：電文字符編碼9527166713290000

40、111100b01e10d110a111c 編碼編碼:右分支右分支:1左分支左分支:0得到各葉結(jié)得到各葉結(jié)點(diǎn)的點(diǎn)的編碼表編碼表 葉結(jié)點(diǎn)代表葉結(jié)點(diǎn)代表 (a,b,c,d,e), 權(quán)值為權(quán)值為(5,6,2,9,7);建立建立哈文曼編碼，如上圖。比如：電文哈文曼編碼，如上圖。比如：電文dadebedbca的碼文的碼文:10110100100011000111110。 最優(yōu)前綴編碼不等長(zhǎng)但譯碼時(shí)不會(huì)錯(cuò)最優(yōu)前綴編碼不等長(zhǎng)但譯碼時(shí)不會(huì)錯(cuò)電文總長(zhǎng)最短。電文總長(zhǎng)最短。哈夫曼編碼哈夫曼編碼樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度定義為：定義為： PL=樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 結(jié)點(diǎn)的路徑長(zhǎng)度結(jié)點(diǎn)

41、的路徑長(zhǎng)度定義為：定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度定義為：定義為： 結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)值結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)值(正數(shù)正數(shù))的乘積。的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度定義為：定義為： 樹(shù)中所有樹(shù)中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度的帶權(quán)路徑長(zhǎng)度之和即之和即結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中：記作：kknkkklwlwwpl1術(shù)語(yǔ)術(shù)語(yǔ)最優(yōu)樹(shù)：最優(yōu)樹(shù)：由給定的n 個(gè)帶權(quán)葉子結(jié)點(diǎn)所構(gòu)成的所有 m 叉樹(shù)中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最帶權(quán)路徑長(zhǎng)度取最小值小值的樹(shù)，稱(chēng)為“最優(yōu)樹(shù)最優(yōu)樹(shù)”。最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)(哈夫曼樹(shù)

42、哈夫曼樹(shù))：帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度WPL最最小的二叉樹(shù)。小的二叉樹(shù)。 顯然顯然, 在最優(yōu)二叉樹(shù)中沒(méi)有度數(shù)為在最優(yōu)二叉樹(shù)中沒(méi)有度數(shù)為 1的結(jié)點(diǎn)的結(jié)點(diǎn); 再根據(jù)二叉樹(shù)性質(zhì)：再根據(jù)二叉樹(shù)性質(zhì)：任何二叉樹(shù)任何二叉樹(shù), 若它含若它含n0 個(gè)葉個(gè)葉結(jié)點(diǎn)、結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)的結(jié)點(diǎn), 則必存在關(guān)系式：則必存在關(guān)系式： n0 = n2+1。 由此得出結(jié)論：由此得出結(jié)論：含含 n個(gè)葉子結(jié)個(gè)葉子結(jié)點(diǎn)的最優(yōu)二叉樹(shù)的總結(jié)點(diǎn)數(shù)為點(diǎn)的最優(yōu)二叉樹(shù)的總結(jié)點(diǎn)數(shù)為 2* *n- -1 。例例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè) 葉子結(jié)點(diǎn)的二叉樹(shù)。abcd7524dcab2475abcd7524WP

43、L=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35基本思想基本思想 使權(quán)值大的結(jié)點(diǎn)靠近根結(jié)點(diǎn)。 (1)根據(jù)給定的根據(jù)給定的 n 個(gè)權(quán)值個(gè)權(quán)值 w1, w2, , wn ,構(gòu)造構(gòu)造 n 棵二叉樹(shù)的集合棵二叉樹(shù)的集合 F = T1, T2, , Tn， 其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；如何構(gòu)造最優(yōu)二叉樹(shù)如何構(gòu)造最優(yōu)二叉樹(shù)(哈夫曼樹(shù)哈夫曼樹(shù)) (哈夫曼算法哈夫曼算法) ： 在在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵中選取

44、其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)二叉樹(shù),分別作為左、右子樹(shù)構(gòu)造一棵新的二分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)叉樹(shù),并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；(2)從從F中刪去這兩棵樹(shù)中刪去這兩棵樹(shù),并加入剛生成的新樹(shù)；并加入剛生成的新樹(shù)； 重復(fù)重復(fù) (2) 和和 (3) ,直至直至 F 中只含一棵樹(shù)為止。中只含一棵樹(shù)為止。(3)(4)87 14142935 111123111100010001108 815151919292942425858100100例例例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 2314871529291487152911358