《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第5章

第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的存儲(chǔ)結(jié)構(gòu)5.4二叉樹的遍歷5.5樹和森林5.6線索二叉樹5.7二叉樹的應(yīng)用

5.1樹的基本概念

定義1

樹(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合T，它滿足如下兩個(gè)條件：

(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)，它沒有前趨；

(2)其余的結(jié)點(diǎn)可分成m個(gè)互不相交的有限集合T1，T2，

…，Tm，其中每個(gè)集合又是一棵樹，并稱為根的子樹。

將n=0時(shí)的空集合定義為空樹(有的書上將n=1的集合定義為空樹)。圖5-1學(xué)校的教學(xué)組織機(jī)構(gòu)圖

5.2二叉樹

定義2

二叉樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱做這個(gè)根的左子樹和右子樹的二叉樹構(gòu)成。

由二叉樹的定義可以給出二叉樹的五種基本形態(tài)，如圖5-2所示。當(dāng)n=0時(shí)得到空二叉樹；n=1時(shí)得到僅有一個(gè)根結(jié)點(diǎn)的二叉樹；當(dāng)根結(jié)點(diǎn)的右子樹為空時(shí)，得到一個(gè)僅有左子樹的二叉樹；當(dāng)根結(jié)點(diǎn)的左子樹為空時(shí)，得到一個(gè)僅有右子樹的二叉樹；當(dāng)左、右子樹均非空時(shí)，得到一般的二叉樹。圖5-2二叉樹的基本形態(tài)圖5-3滿二叉樹、完全二叉樹和一般二叉樹

性質(zhì)1

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。

證明：可用數(shù)學(xué)歸納法予以證明。

當(dāng)i=1時(shí)，有2i-1=20=1，同時(shí)第一層上只有一個(gè)根結(jié)點(diǎn)，故命題成立。

設(shè)當(dāng)i=k時(shí)成立，即第k層上至多有2k-1個(gè)結(jié)點(diǎn)。

當(dāng)i=k+1時(shí)，由于二叉樹的每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，因此第k+1層上至多有2

2k-1=2k個(gè)結(jié)點(diǎn)。故命題成立。

性質(zhì)2

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。

(5-1)

證明：性質(zhì)1給出了二叉樹每一層中含有的最大結(jié)點(diǎn)數(shù)，深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為2k-1個(gè)。故命題成立。

性質(zhì)3

對(duì)任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

證明：設(shè)度為1的結(jié)點(diǎn)數(shù)為n1，則一棵二叉樹的結(jié)點(diǎn)總數(shù)為

n=n0+n1+n2

(5-2)

除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)進(jìn)入的分支(邊)，設(shè)B為分支總數(shù)，則n=B+1。又考慮到分支是由度為1和2的結(jié)點(diǎn)發(fā)出的，故有B=2n2+n1，即

n=2n2+n1+1 (5-3)

比較式(5-1)與式(5-2)可得n0=n2+1。命題成立。

性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為?

lbn

?+?1或?

lb(n?+?1)

。

注：

x

表示不大于x的最大整數(shù)；

x

表示不小于x的最小整數(shù)。

證明：由完全二叉樹的定義可知，一個(gè)k層的完全二叉樹的前k-1層共有2k-1-1個(gè)結(jié)點(diǎn)，第k層上還有若干結(jié)點(diǎn)，所以結(jié)點(diǎn)總數(shù)n滿足關(guān)系：

2k-1-1＜n≤2k-1

(5-4)

可推出2k-1≤n＜2k，取對(duì)數(shù)后可得k?-?1≤lbn＜k。因?yàn)閗為整數(shù)，所以有k-1?=?

lbn

，即k=?

lbn

?+?1。同樣利用(5-3)式有2k-1＜n+1≤2k，取對(duì)數(shù)得k-1＜lb(n+1)≤k，因而k=?

lb(n+1)

。命題成立。

5.3二叉樹的存儲(chǔ)結(jié)構(gòu)

5.3.1順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)是將二叉樹的所有結(jié)點(diǎn)，按照一定的順序化方式，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)的順序?qū)⒎从吵鼋Y(jié)點(diǎn)之間邏輯關(guān)系。

圖5-4完全二叉樹的結(jié)點(diǎn)編號(hào)圖5-5和表5-2給出了一般二叉樹構(gòu)成完全二叉樹并用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的示例。其中方形結(jié)點(diǎn)為虛結(jié)點(diǎn)，并用符號(hào)@表示結(jié)點(diǎn)值。圖5-5一般二叉樹的結(jié)點(diǎn)編號(hào)5.3.2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)是二叉樹的一種自然鏈接方法。在一定的條件下，鏈?zhǔn)酱鎯?chǔ)可節(jié)省存儲(chǔ)單元。因?yàn)槎鏄涞拿總€(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，所以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來存儲(chǔ)二叉樹時(shí)，每個(gè)結(jié)點(diǎn)應(yīng)至少包括三個(gè)域：結(jié)點(diǎn)數(shù)據(jù)域(data)、左孩子指針域(lchild)和右孩子指針域(rchild)。二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)點(diǎn)邏輯結(jié)構(gòu)如圖5-6所示。圖5-6二叉樹鏈?zhǔn)酱鎯?chǔ)的結(jié)點(diǎn)結(jié)構(gòu)圖5-7鏈表存儲(chǔ)結(jié)構(gòu)5.3.3二叉樹的建立

二叉樹的建立是指如何在內(nèi)存中建立二叉樹存儲(chǔ)結(jié)構(gòu)。二叉樹順序存儲(chǔ)結(jié)構(gòu)的建立比較簡(jiǎn)單，只須將二叉樹各個(gè)結(jié)點(diǎn)的(信息)值按原有的邏輯關(guān)系送入相應(yīng)的向量單元中即可。

建立二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法有多種，它們依賴于按照何種形式來輸入二叉樹的邏輯結(jié)構(gòu)信息。一種常見的算法是按照完全二叉樹的層次順序，依次輸入結(jié)點(diǎn)信息來建立二叉鏈表。對(duì)于一般二叉樹，首先必須通過添加若干個(gè)虛結(jié)點(diǎn)使其成為完全二叉樹，然后建立二叉鏈表。

5.4二叉樹的遍歷

5.4.1二叉樹的深度優(yōu)先遍歷

1.先序遍歷算法

先序遍歷算法的遍歷過程是，若二叉樹非空，執(zhí)行以下操作：

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。圖5-8二叉樹的遍歷過程圖5-9算法執(zhí)行過程示意圖

2.中序遍歷算法

中序遍歷算法的遍歷過程是，若二叉樹非空，執(zhí)行以下操作：

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。

3.后序遍歷算法

后序遍歷算法的遍歷過程是，若二叉樹非空，執(zhí)行以下操作：

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。5.4.2二叉樹的廣度優(yōu)先遍歷

二叉樹的廣度優(yōu)先遍歷又稱為按層次遍歷。這種遍歷方式是先遍歷二叉樹的第一層結(jié)點(diǎn)，然后遍歷第二層結(jié)點(diǎn)，……最后遍歷最下層的結(jié)點(diǎn)。而對(duì)每一層的遍歷是按從左至右的方式進(jìn)行的。5.4.3深度優(yōu)先遍歷的非遞歸算法

前面描述的三種深度優(yōu)先遍歷算法都是用遞歸方式給出的。雖然遞歸算法比較緊湊，結(jié)構(gòu)清晰，但它的運(yùn)行效率比較低，通常可讀性也較差；同時(shí)并非所有程序設(shè)計(jì)語(yǔ)言都允許遞歸，因此有時(shí)需要將一個(gè)遞歸算法轉(zhuǎn)化為等價(jià)的非遞歸算法。5.4.4從遍歷序列恢復(fù)二叉樹

前面討論了由二叉樹得到遍歷序列的問題，下面將討論這個(gè)問題的逆問題，即在已知結(jié)點(diǎn)遍歷序列的條件下，恢復(fù)相應(yīng)二叉樹的問題。在已知一棵任意二叉樹的先序遍歷序列和中序遍歷序列，或者已知中序遍歷序列和后序遍歷序列的條件下，可以唯一地確定這棵二叉樹。除了特殊的情況，不能用先序遍歷序列和后序遍歷序列來確定對(duì)應(yīng)的二叉樹。圖5-10由先序和中序序列構(gòu)造二叉樹的過程5.4.5遍歷算法的應(yīng)用

1.統(tǒng)計(jì)一棵二叉樹中的葉子結(jié)點(diǎn)數(shù)

因?yàn)槿~子結(jié)點(diǎn)是二叉樹中那些左孩子和右孩子均不存在的結(jié)點(diǎn)，所以可在二叉樹的遍歷過程中，對(duì)這種特殊結(jié)點(diǎn)進(jìn)行計(jì)數(shù)，來完成葉子結(jié)點(diǎn)數(shù)的統(tǒng)計(jì)。這個(gè)統(tǒng)計(jì)可在任何一種遍歷方式下給出。下面給出一種統(tǒng)計(jì)一棵二叉樹葉子結(jié)點(diǎn)數(shù)的遞歸統(tǒng)計(jì)算法。一棵樹的葉子數(shù)目等于它的左子樹葉子數(shù)加上右子樹葉子數(shù)的總和。而當(dāng)一個(gè)結(jié)點(diǎn)沒有左子樹也沒有右子樹的時(shí)候，即為葉子結(jié)點(diǎn)。其計(jì)算表達(dá)式如下：

2.求二叉樹深度

二叉樹的深度是二叉樹中結(jié)點(diǎn)層次的最大值。可通過先序遍歷來計(jì)算二叉樹中每個(gè)結(jié)點(diǎn)的層次，其中的最大值即為二叉樹的深度。下面給出一種計(jì)算二叉樹深度的遞歸計(jì)算的

算法。在二叉樹中，取左子樹深度和右子樹深度中數(shù)值較大的深度加1，就得到了二叉樹的深度。其計(jì)算表達(dá)式如下：

3.表達(dá)式與二叉樹的關(guān)系

表達(dá)式有三種表達(dá)方式：前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式。這三種表達(dá)式分別對(duì)應(yīng)其表達(dá)式樹的先序遍歷、中序遍歷和后序遍歷。我們平常一般使用的是中綴表達(dá)式如a*(((b+c)*(d*e))+f)，與之對(duì)應(yīng)的后綴表達(dá)式為abc+de**f+*，

下面主要討論由后綴表達(dá)式生成表達(dá)式樹的方法。由后綴表達(dá)式生成表達(dá)式樹算法的主要思想是：

(1)維護(hù)一個(gè)操作數(shù)棧。

(2)掃描后綴表達(dá)式，如果碰到操作數(shù)，則生成操作數(shù)結(jié)點(diǎn)入棧；若為操作符，則生成操作符結(jié)點(diǎn)，并將棧中頭兩個(gè)元素出棧，作為操作符結(jié)點(diǎn)的左右子樹(注意：先出棧的為右子樹，后出棧的為左子樹)，然后將新生成的樹作為操作數(shù)結(jié)點(diǎn)入棧。

(3)重復(fù)(2)的操作直到后綴表達(dá)式結(jié)束為止。若后綴表達(dá)式語(yǔ)法正確，棧中將僅剩一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)就是表達(dá)式樹。

5.5樹和森林

本節(jié)將討論樹的存儲(chǔ)表示，并建立森林與二叉樹的對(duì)應(yīng)關(guān)系。一般樹的表示方法如圖5-11所示。圖5-11樹的表示5.5.1樹的存儲(chǔ)結(jié)構(gòu)

樹可以用多種形式的存儲(chǔ)結(jié)構(gòu)來表示，經(jīng)常用到的有以下三種方法。

1．雙親表示法

在樹中，每個(gè)結(jié)點(diǎn)的雙親是唯一的。利用這個(gè)性質(zhì)，可在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)存儲(chǔ)其雙親結(jié)點(diǎn)的地址信息。

2．孩子表示法

由于樹中每個(gè)結(jié)點(diǎn)的子樹數(shù)目不盡相同，因此在采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示樹時(shí)，每個(gè)結(jié)點(diǎn)內(nèi)要設(shè)置多少個(gè)指向其孩子的指針是難以確定的。若以整個(gè)樹的度k來設(shè)置指針，則在n個(gè)結(jié)點(diǎn)的樹中，其空指針域的數(shù)目是k*n-(n-1)=n(k-1)+1,這將造成極大的空間浪費(fèi)。若每個(gè)結(jié)點(diǎn)按其實(shí)際的孩子個(gè)數(shù)設(shè)置指針，并在結(jié)點(diǎn)內(nèi)設(shè)置度數(shù)域degree來表示該結(jié)點(diǎn)所包含的指針數(shù)，則各結(jié)點(diǎn)不等長(zhǎng)，雖然節(jié)省了存儲(chǔ)空間，但會(huì)給運(yùn)算帶來不便。圖5-12孩子和雙親孩子表示法

3．孩子兄弟表示法

在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域first和next，即可得到樹的孩子兄弟表示法。例如，圖5-11中樹的孩子兄弟表示法如圖5-13所示。這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是，它和二叉樹的二叉鏈表表示完全一樣，因此，可利用二叉樹的算法來實(shí)現(xiàn)對(duì)樹的操作。圖5-13孩子兄弟表示法5.5.2樹、森林和二叉樹之間的轉(zhuǎn)換

樹、森林和二叉樹之間有對(duì)應(yīng)關(guān)系，它們之間可以互相進(jìn)行轉(zhuǎn)換，即任何一個(gè)森林或一棵樹可以唯一地轉(zhuǎn)換成一棵二叉樹；而任意一棵二叉樹也能唯一地對(duì)應(yīng)于一個(gè)森林或一棵樹。這種轉(zhuǎn)換是具有唯一性的。將一棵樹轉(zhuǎn)換為二叉樹的方法是：

(1)在兄弟之間增加一條連線。

(2)對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其左孩子的連線外，應(yīng)除去與其他孩子之間的連線。

(3)以樹的根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針旋轉(zhuǎn)45°。

圖5-14給出了一棵樹轉(zhuǎn)換為二叉樹的過程。從轉(zhuǎn)換結(jié)果可以看出，任何一棵樹轉(zhuǎn)化為對(duì)應(yīng)的二叉樹后，二叉樹的右子樹為空。圖5-14樹轉(zhuǎn)換成二叉樹將一棵二叉樹轉(zhuǎn)換成樹的規(guī)則是：

(1)若結(jié)點(diǎn)X是雙親Y的左孩子，則把X的右孩子，右孩子的右孩子……都與Y用連線相連。

(2)去掉原有的雙親到右孩子的連線。

圖5-15給出了一棵二叉樹轉(zhuǎn)化為樹的過程。圖5-15二叉樹轉(zhuǎn)換成樹將一個(gè)森林轉(zhuǎn)換成二叉樹的方法是：先將森林中的每一棵樹轉(zhuǎn)換為二叉樹；再將第一棵樹的根作為轉(zhuǎn)換后二叉樹的根，第一棵樹的左子樹作為轉(zhuǎn)換后二叉樹根的左子樹，第二棵樹作為轉(zhuǎn)換后二叉樹的右子樹，第三棵樹作為轉(zhuǎn)換后的二叉樹根的右子樹的右子樹，如此類推下去，就將一個(gè)森林轉(zhuǎn)換為一棵二叉樹，如圖5-16所示。圖5-16森林和對(duì)應(yīng)的二叉樹

5.6線?索?二?叉?樹

5.6.1線索二叉樹的建立

為了記錄結(jié)點(diǎn)的前趨和后繼信息，可在原來的二叉鏈表中增加一個(gè)前趨指針域(pred)和一個(gè)后繼指針域(succ)，分別指向該結(jié)點(diǎn)在某種次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)，使結(jié)點(diǎn)的結(jié)構(gòu)為這樣做顯然會(huì)浪費(fèi)不少存儲(chǔ)空間。考慮到在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域，因此可以利用這些空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針。這種附加的指針稱為線索；加上了線索的二叉鏈表稱為線索鏈表；相應(yīng)的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。為了區(qū)分一個(gè)結(jié)點(diǎn)的指針域是指向其孩子的指針，還是指向其前趨或后繼的線索，可在每個(gè)結(jié)點(diǎn)中增加兩個(gè)線索標(biāo)志域。這樣，線索鏈表中的結(jié)點(diǎn)結(jié)構(gòu)為其中圖5-17中序線索二叉樹及其二叉鏈表表示5.6.2訪問線索二叉樹

1．查找某結(jié)點(diǎn)?*p在指定次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)

在建立了線索二叉樹后，如何在線索二叉樹中查找結(jié)點(diǎn)的后繼或前趨呢？

在中序線索二叉樹中，查找結(jié)點(diǎn)?*p的中序后繼結(jié)點(diǎn)分兩種情況：

(1)若?*p的右子樹為空，則p->rchild為右線索，直接指向?*p的中序后繼結(jié)點(diǎn)。

(2)若*p的右子樹非空，則*p的中序后繼必是其右子樹中第一個(gè)中序遍歷到的結(jié)點(diǎn)，即從*p的右孩子開始沿左指針鏈向下找，直至找到一個(gè)沒有左孩子的結(jié)點(diǎn)為止。這個(gè)結(jié)點(diǎn)是*p的右子樹中“最左下”的結(jié)點(diǎn)，它就是*p的中序后繼結(jié)點(diǎn)。如圖5-18所示，其中*p的中序后繼結(jié)點(diǎn)是結(jié)點(diǎn)*s。應(yīng)用類似的方法，可以在中序線索樹中查找結(jié)點(diǎn)?*p的中序前趨結(jié)點(diǎn)。若?*p的左子樹為空，則p->lchild為左線索，直接指向?*p的中序前趨結(jié)點(diǎn)；若?*p的左子樹非空，則從?*p的左孩子出發(fā)，沿右指針鏈往下查找，直至找到一個(gè)沒有右孩子的結(jié)點(diǎn)為止。該結(jié)點(diǎn)是?*p的左子樹中“最右下”的結(jié)點(diǎn)，是?*p的左子樹中最后一個(gè)中序遍歷到的結(jié)點(diǎn)，它就是?*p的中序前趨結(jié)點(diǎn)。如圖5-19所示，其中?*p的中序前趨結(jié)點(diǎn)是結(jié)點(diǎn)?*t。圖5-18*p的中序后繼結(jié)點(diǎn)?*s圖5-19*p的中序前趨結(jié)點(diǎn)?*t在后序線索二叉樹中，查找指定結(jié)點(diǎn)*p的后序前趨結(jié)點(diǎn)的方法是：

(1)若p->ltag=1(左子樹為空)，則p->lchild即為前趨結(jié)點(diǎn)。

(2)若p->ltag=0(左子樹非空)，則

①當(dāng)p->rtag=0(右子樹非空)，則p->rchild為前趨結(jié)點(diǎn)；

②當(dāng)p->rtag=1(右子樹為空)，則p->lchild為前趨結(jié)點(diǎn)。如圖5-20所示，其中的虛線表示線索，可以看出：H的后序前趨結(jié)點(diǎn)是B，C的前趨是F，A的前趨是C，F(xiàn)的前趨是G。

在后序線索二叉樹中，查找指定結(jié)點(diǎn)?*p的后序后繼結(jié)點(diǎn)的方法是：

(1)若?*p為根，則后繼為空。

(2)若?*p是其雙親的右孩子，則其雙親即為后序后繼結(jié)點(diǎn)。

(3)若?*p是其雙親的左孩子，但?*p沒有右兄弟時(shí)，則?*p的后序后繼結(jié)點(diǎn)是其雙親結(jié)點(diǎn)。

(4)若?*p是其雙親的左孩子，但?*p有右兄弟時(shí)，則?*p的后序后繼結(jié)點(diǎn)是其雙親的右子樹中第一個(gè)后序遍歷到的結(jié)點(diǎn)，它是該子樹中“最左下”的葉子結(jié)點(diǎn)。圖5-20后序線索二叉樹圖5-20后序線索二叉樹

2．遍歷線索二叉樹

遍歷某種次序的線索二叉樹，只要從該次序的開始結(jié)點(diǎn)出發(fā)，查找結(jié)點(diǎn)在該次序下的后繼，直至查找到終端結(jié)點(diǎn)為止。這對(duì)于中序和前序線索二叉樹是十分簡(jiǎn)單的，無(wú)須像非線索樹遍歷那樣，引入棧來保存留待以后訪問的子樹信息。

5.7二叉樹的應(yīng)用

5.7.1哈夫曼樹及其應(yīng)用

哈夫曼樹，又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹。

1．基本概念

兩個(gè)結(jié)點(diǎn)間的路徑是指從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支。

路徑的長(zhǎng)度是指從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支數(shù)。例如，k1，k2，…，kn是一條路徑，則該路徑長(zhǎng)度為n-1。樹的路徑長(zhǎng)度是樹根到樹中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。當(dāng)然，也可能有其他非完全二叉樹具有同完全二叉樹相同

的路徑長(zhǎng)度，這可以從具有四個(gè)結(jié)點(diǎn)構(gòu)成的三種二叉樹的

圖5-21中看出。圖5-21四結(jié)點(diǎn)構(gòu)成的三種二叉樹設(shè)路徑長(zhǎng)度用PL表示，則二叉樹1、二叉樹2和二叉樹3的路徑長(zhǎng)度分別為

PL1=0+1+1+2=4，PL2=0+1+1+2=4，

PL3=0+1+2+3=6

當(dāng)樹中的結(jié)點(diǎn)被賦予一個(gè)稱之為權(quán)的有某種意義的實(shí)數(shù)時(shí)，則該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)權(quán)值的乘積。樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記做：

(5-5)在有n個(gè)帶權(quán)葉子結(jié)點(diǎn)的所有二叉樹中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹被稱為最優(yōu)二叉樹或哈夫曼樹。

由于WPL是所有葉子結(jié)點(diǎn)的權(quán)值與路徑長(zhǎng)度乘積的和，因此要使WPL盡可能地小，就必須使每個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與權(quán)值之積盡可能小。但因?yàn)闄?quán)值是確定的，所以只能通過調(diào)整葉子結(jié)點(diǎn)的路徑長(zhǎng)度來使結(jié)點(diǎn)的權(quán)值和路徑長(zhǎng)度之積盡可能小。也就是說，當(dāng)一個(gè)葉子結(jié)點(diǎn)的權(quán)值比較大時(shí)，應(yīng)讓其盡可能接近根結(jié)點(diǎn)，這樣就減少了路徑長(zhǎng)度，從而減少了WPL。對(duì)于具有權(quán)值為w1，w2，…，wn的n個(gè)葉子結(jié)點(diǎn)形成的二叉樹，可以具有多種形態(tài)，其中能被稱為哈夫曼樹的二叉樹并不是唯一的。例如，對(duì)于四個(gè)權(quán)值分別為3，4，5，7的葉子結(jié)點(diǎn)a，b，c，d構(gòu)造的二叉樹，可以得到兩棵哈夫曼樹，如圖5-22所示。圖5-22不同形態(tài)的哈夫曼樹可以計(jì)算出這兩棵哈夫曼樹的WPL分別為

WPL1=3×2+4×2+5×2+7×2=38

WPL2=3×3+4×3+5×2+7=38

在葉子數(shù)和權(quán)值相同的二叉樹中，完全二叉樹不一定是最優(yōu)二叉樹。例如，對(duì)于權(quán)值分別為2，4，5，7的四個(gè)結(jié)點(diǎn)a，b，c，d的集合而言，構(gòu)造出的完全二叉樹和哈夫曼樹如圖5-23所示。圖5-23完全二叉樹與哈夫曼樹可以計(jì)算出完全二叉樹的帶權(quán)路徑長(zhǎng)度為

WPL=2×2+4×2+5×2+7×2=36

哈夫曼樹的帶權(quán)路徑長(zhǎng)度為

WPL=2×3+4×3+5×2+7×1=35

2.哈夫曼樹的構(gòu)造

哈夫曼最早給出了一個(gè)帶有一般規(guī)律的算法來構(gòu)造哈夫曼樹。圖5-24哈夫曼樹的構(gòu)造過程圖5-25結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)圖5-26構(gòu)造哈夫曼樹

3.哈夫曼編碼

哈夫曼樹的應(yīng)用很廣泛，下面討論哈夫曼樹在通信編碼中的應(yīng)用。

如何構(gòu)造前綴碼，并且使傳送的電文長(zhǎng)度最小呢？

利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴碼。例如，有一棵二叉樹如圖5-27所示，其四個(gè)葉子結(jié)點(diǎn)分別表示a、b、c和d這四個(gè)字符，且約定左分支表示字符0，右分支表示字符1，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼，這樣得到的一定是二進(jìn)制前綴編碼。由圖5-27所得a、b、c和d的二進(jìn)制前綴編碼分別為0、10、110和11。圖5-27前綴編碼示例

4.哈夫曼樹譯碼

哈夫曼樹譯碼是指由給定的代碼求出代碼所表示的結(jié)點(diǎn)值。它是哈夫曼編碼的逆過程。哈夫曼樹譯碼的過程是：從根結(jié)點(diǎn)出發(fā)，逐個(gè)讀入電文中的二進(jìn)制代碼，若代碼為0則走向左孩子；否則走向右孩子。一旦到達(dá)葉子結(jié)點(diǎn)，便可譯出代碼所對(duì)應(yīng)的字符。然后又重新從根結(jié)點(diǎn)開始繼續(xù)譯碼，直到二進(jìn)制電文結(jié)束為止。5.7.2二叉排序樹

樹形結(jié)構(gòu)的一個(gè)重要應(yīng)用是用來組織目錄。樹形結(jié)構(gòu)的目錄稱為樹目錄。

1.二叉排序樹的概念

如果一棵二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)關(guān)鍵碼，并且每個(gè)結(jié)點(diǎn)的左子樹中所有結(jié)點(diǎn)的