樹的概念課件

⑥樹的概念

胤<:::x概念

⑥二叉樹

胤二叉樹的定義

胤二叉樹的性質(zhì)

置二叉樹的存儲結(jié)構(gòu)

⑥二叉樹的遍歷

胤二叉樹的遍歷

⑥線索二叉樹

胤線索二叉樹

蜀樹和森林

胤樹、森林和二叉樹的轉(zhuǎn)

胤樹的存儲結(jié)構(gòu)

.樹和森林的遍歷

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

胤最優(yōu)二叉樹

胤哈夫曼編碼

樹的概念

本章簡介

樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。

它非常類似于自然界中的樹。

樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。

樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；

在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時(shí)，可用樹來描述其執(zhí)行過程。

本章重點(diǎn)討論二叉樹的存儲表示及其各種運(yùn)算，并研究一般樹和森林與二叉樹的轉(zhuǎn)換關(guān)系,

最后介紹樹的應(yīng)用實(shí)例。

樹的概念

1.家族樹

在現(xiàn)實(shí)生活中，有入如下血統(tǒng)關(guān)系的家族可用樹形圖表示：

張?jiān)从腥齻€(gè)孩子張明、張亮和張麗；

張明有兩個(gè)孩子張林和張維；

張亮有三個(gè)孩子張平、張華和張群；

張平有兩個(gè)孩子張晶和張磊。

張?jiān)?/p>

以上表示很像一棵倒畫的樹。其中"樹根"是張?jiān)矗瑯涞?分支點(diǎn)"是張明、張亮和張平，該家族

的其余成員均是"樹葉"，而樹枝(即圖中的線段)則描述了家族成員之間的關(guān)系。顯然，以張?jiān)礊?/p>

根的樹是一個(gè)大家庭。它可以分成張明、張亮和張麗為根的三個(gè)小家庭；每個(gè)小家庭又都是一個(gè)

樹形結(jié)構(gòu)。

2.樹的定義

樹的遞歸定義：

樹(Tree)是n(應(yīng)0)個(gè)結(jié)點(diǎn)的有限集T,T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：

(1)有且僅有個(gè)特定的稱為根(Root)的結(jié)點(diǎn)：

(2)其余的結(jié)點(diǎn)可分為m(mZO)個(gè)互不相交的子集TI,T2,....Tm,其中每個(gè)子集本身又是一棵樹,

并稱其為根的子樹(Subree)。

注意：

樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構(gòu)成的，而子樹又可由若

干棵更小的子樹構(gòu)成。

上一頁下一頁

3.樹的表示

(1)樹形圖表示

樹形圖表示是樹結(jié)構(gòu)的主要表示方法。

樹的樹形圖表示中：結(jié)點(diǎn)用圓圈表示，結(jié)點(diǎn)的名字寫在圓圈旁邊(有時(shí)亦可寫在圓圈內(nèi))。

如〉樹形表示法00嵌套集合表示法(c)凹入表表示法

(A(B(E,F(I,.D),C,D(G,H)))

(d)廣義表表示法

樹的各種表示法

用該定義來分析上圖(a)所示的樹：

圖中的樹由結(jié)點(diǎn)的有限集T={A,B,C,D,E,F,C,H,I,J}所構(gòu)成，其中A是根結(jié)點(diǎn)，T

中其余結(jié)點(diǎn)可分成三個(gè)互不相交的子集：

T產(chǎn){B,E,F,I,J},

T2={C},

T3={D,G,H}。

「、T2和T3是根A的三棵子樹、且本身又都是一棵樹。例如T”其根為B,其余結(jié)點(diǎn)可分為

兩個(gè)互不相交的的子集T“={E}和TD={F,I,J},它們都是B的子樹。顯然T”是只含一個(gè)根結(jié)

點(diǎn)E的樹，而Tn的根F又有兩棵互不相交的子樹⑴和{J},其本身又都是只含一個(gè)根結(jié)點(diǎn)的樹。

(2)樹的其他表示法

①嵌套集合表示法

是用集合的包含關(guān)系來描述樹結(jié)構(gòu)。

上圖(a)樹的嵌套集合表示法如圖(b)

②凹入表表示法

類似于書的目錄，上圖(a)樹的網(wǎng)入表示法如圖(c)

③廣義表表示法

用廣義表的形式表示的。上圖(a)樹的廣義表表示法如圖(d)

(A(B(E,F(I,J)),C,D(G,H)))

4.樹結(jié)構(gòu)的基本術(shù)語

(1)結(jié)點(diǎn)的度(Degree)

樹中的?個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度(Degree)。

?棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。

度為零的結(jié)點(diǎn)稱為葉子(Leaf)或終端結(jié)點(diǎn)o

度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。

除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

根結(jié)點(diǎn)又稱為開始結(jié)點(diǎn)。

(2)孩子(ChiId)和雙親(Parents)

樹中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的孩子(Child)或兒子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的

雙親(Parents)或父親。

同一個(gè)雙親的孩子稱為兄弟(Sibling)。

(3)祖先(Ancestor)和子孫(Descendant)

①路徑(path)

若樹中存在一個(gè)結(jié)點(diǎn)序列k”k”…，k,,使得上是1<1的雙親(lWi〈j),則稱該結(jié)點(diǎn)序

列是從L到k,的一條路徑(Path)或道路。

路徑的長度指路徑所經(jīng)過的邊(即連接兩個(gè)結(jié)點(diǎn)的線段)的數(shù)目，等于j-k

注意：

若一個(gè)結(jié)點(diǎn)序列是路徑，則在樹的樹形圖表示中，該結(jié)點(diǎn)序列"自上而下''地通過路徑上的

每條邊。

從樹的根結(jié)點(diǎn)到樹中其余結(jié)點(diǎn)均存在一條惟一的路徑。

②祖先(Ancestor)和子孫(Descendant)

若樹中結(jié)點(diǎn)k到k,存在一條路徑，則稱k是X的祖先(Ancestor),k是k的子孫

(Descendant)?

一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫則是以

該結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)。

約定：

結(jié)點(diǎn)k的祖先和子孫不包含結(jié)點(diǎn)k本身。

(4)結(jié)點(diǎn)的層數(shù)(Level)和樹的高度(Height)

結(jié)點(diǎn)的層數(shù)(Level)從根起算：

根的層數(shù)為1

其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。

雙親在同一層的結(jié)點(diǎn)互為堂兄弟。

樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth)。

注意，

很多文獻(xiàn)中將樹根的層數(shù)定義為0。

(5)有序樹(OrderedTree)和無序樹(UnoderedTree)

若將樹中每個(gè)結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹

(OrderedTree)；否則稱為無序樹(UnoderedTree)?

注意：

若不特別指明，?般討論的樹都是有序樹。

(6)森林(Forest)

森林(Forest)是m(m20)棵立不相交的樹的集合。

樹和森林的概念相近。刪去一棵樹的根，就得到?個(gè)森林；反之，加上?個(gè)結(jié)點(diǎn)作樹根,

森林就變?yōu)橐豢脴洹?/p>

5.樹形結(jié)構(gòu)的邏輯特征

樹形結(jié)構(gòu)的邏輯特征可用樹中結(jié)點(diǎn)之間的父子關(guān)系來描述：

(1)樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼(即孩子)結(jié)點(diǎn),但至多只能有一個(gè)直接前趨(即

雙親)結(jié)點(diǎn)。

(2)樹中只有根結(jié)點(diǎn)無前趨，它是開始結(jié)點(diǎn)；葉結(jié)點(diǎn)無后繼，它們是終端結(jié)點(diǎn)。

(3)祖先與子孫的關(guān)系是對父子關(guān)系的延拓，它定義了樹中結(jié)點(diǎn)之間的縱向次序。

(4)有序樹中，同一組兄弟結(jié)點(diǎn)從左到右有長幼之分。

對這一關(guān)系加以延拓，規(guī)定若總和上是兄弟，且心在L的左邊，則笛的任一子孫都在L

的任孫的左邊，那么就定義了樹中結(jié)點(diǎn)之間的橫向次序。

二叉樹

二叉樹是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形

式，即使是?般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲結(jié)構(gòu)及其算法都較為簡單，因

此二叉樹顯得特別重要。

1.二叉樹的遞歸定義

二叉樹(BinaryTree)是n(n》O)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0),或者由一個(gè)根結(jié)

點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。

2.二叉樹的五種基本形態(tài)

二叉樹可以是空集；根可以有空的左廣樹或右子樹；或者左、右子樹皆為空。

二叉樹的五種基本形態(tài)如下圖所示。

I)空二義樹＜b)僅有一個(gè)根結(jié)點(diǎn)的二叉樹(c)右子樹為空的.叉樹

(d)左子樹為空的:叉樹(e)左右子樹均非空的：叉樹

:義樹的萬種基本形態(tài)

3.二叉樹不是樹的特例

(1)二叉樹與無序樹不同

二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，并且有左右之分。

二義樹并非是樹的特殊情形，它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。

(2)二叉樹與度數(shù)為2的有序樹不同

在有序樹中，雖然?個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的，但是若該結(jié)點(diǎn)只有?個(gè)孩子，就無

須區(qū)分其左右次序。而在二叉樹中，即使是??個(gè)孩子也有左右之分。

【例】下圖中(a)和(b)是兩棵不同的二叉樹，它們同右圖中的普通樹(作為有序樹或無序樹)

很相似，但卻不等同于這棵普通樹。若將這三棵樹均看做普通樹，則它們就是相同的了。

AAOA

二叉樹并非是樹的特殊情形，它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。

二叉樹具有以下重要性質(zhì)：

性質(zhì)1二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2r（之1）。

證明:用數(shù)學(xué)歸納法證明：

歸納基礎(chǔ)：i=l時(shí)，有2?.2°=1。因?yàn)榈?層上只有一個(gè)根結(jié)點(diǎn)，所以命題成立。

歸納假設(shè)：假設(shè)對所有的j（lWj<i）命題成立，即第j層上至多有2打個(gè)結(jié)點(diǎn)，證明j=i時(shí)命題

亦成立。

歸納步驟：根據(jù)歸納假設(shè)，第i-1層上至多有2'2個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)至多有兩

個(gè)孩子，故第i層上的結(jié)點(diǎn)數(shù)至多是第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍。即j=i時(shí)，該層上至多有

2、2“2=2*個(gè)結(jié)點(diǎn)，故命題成立。

性質(zhì)2深度為k的二叉樹至多有2k-l個(gè)結(jié)點(diǎn)（kR）。

W：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時(shí)，其樹中結(jié)點(diǎn)數(shù)最多。因此

利用性質(zhì)1可得，深度為k的二叉樹的結(jié)點(diǎn)數(shù)至多為：

2°+2l+...+2k-|=2k-l

故命題正確。

性質(zhì)3在任意-棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為叫，則%=%+1。

證明:因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度數(shù)均不大于2,所以結(jié)點(diǎn)總數(shù)（記為n）應(yīng)等于0度結(jié)點(diǎn)數(shù)、1

度結(jié)點(diǎn)（記為由）和2度結(jié)點(diǎn)數(shù)之和：

n=n0+ri|+n2（式子1）

另一方面，1度結(jié)點(diǎn)有一個(gè)孩子，2度結(jié)點(diǎn)有兩個(gè)孩子，故二叉樹中孩子結(jié)點(diǎn)總數(shù)是：

ri|+2n2

樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子，故二叉樹中的結(jié)點(diǎn)總數(shù)又可表示為：

n=n1+2n2+1（式子2）

由式子1和式子2得到：

no=n2+l

滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。

1、滿二叉樹（FullBinaryTree）

一棵深度為k且有2k-l個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹。

滿二叉樹的特點(diǎn)：

(1)每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹。

(2)滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉

都在最下一層上。

【例】圖(a)是一個(gè)深度為4的滿二叉樹。

(a)滿二又樹(b)完全：叉樹(c)非完全.叉樹

特殊形態(tài)的二叉樹

2、完全二叉樹(CompleteBinaryTree)

若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2,并且最下一層上的結(jié)點(diǎn)都集中

在該層最左邊的若干位置上，則此二又樹稱為完全二叉樹。

特點(diǎn)：

(1)滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

(2)在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹仍然是一棵

完全二叉樹。

(3)在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。

【例】如圖(c)中，結(jié)點(diǎn)F沒有左孩子而有右孩子L,故它不是一棵完全二叉樹。

【例】圖(b)是一棵完全二叉樹。

性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

證明:設(shè)所求完全二叉樹的深度為k。由完全二叉樹定義可得：

深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，-共有2kLi個(gè)結(jié)點(diǎn)。

由于完全二叉樹深度為k,故第k層上還有若干個(gè)結(jié)點(diǎn)，因此該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)：

n>2k-1-lo

另一方面，由性質(zhì)2可得：

n<2k-l,

即：2k-'-l<n<2k-l

由此可推出：2"wn<2k,取對數(shù)后有：

k-l<lgn<k

又因k-1和k是相鄰的兩個(gè)整數(shù)，故有

A-1-LlgNj,

由此即得:

注意：

的證明【參見參考書目】

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

該方法是把二叉樹的所有結(jié)點(diǎn)按照一定的線性次序存儲到一片連續(xù)的存儲單元中。結(jié)點(diǎn)在這

個(gè)序列中的相互位置還能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。

1.完全二叉樹結(jié)點(diǎn)編號

(1)編號辦法

在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點(diǎn)

編號，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列。

【例】如下圖所示。

(2)編號特點(diǎn)

完全二叉樹中除最下面一層外，各層都充滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)

個(gè)數(shù)的2倍。從一個(gè)結(jié)點(diǎn)的編號就可推得其雙親，左、右孩子，兄弟等結(jié)點(diǎn)的編號。假設(shè)編號為

i的結(jié)點(diǎn)是k(lWiWn),則有:

①若i>l,則％的雙親編號為|f/2j；若i=l,則K,是根結(jié)點(diǎn)，無雙親。

②若2iWn,則K,的左孩子的編號是2i：否則，K；無左孩子，即長必定是葉子。因此完全

二又樹中編號的結(jié)點(diǎn)必定是葉結(jié)點(diǎn)。

③若2i+lWn,則K,的右孩子的編號是2i+l；否則，K,無右孩子。

④若i為奇數(shù)且不為1,則K,的左兄弟的編號是i-1；否則，K：無左兄弟。

⑤若i為偶數(shù)且小于n,則K；的右兄弟的編號是i+1；否則，K,無右兄弟。

2.完全二叉樹的順序存儲

將完全二叉樹中所有結(jié)點(diǎn)按編號順序依次存儲在一個(gè)向量bt[O..n]中。

其中：

bt[l..n]用來存儲結(jié)點(diǎn)

bt[O]不用或用來存儲結(jié)點(diǎn)數(shù)目。

【例】表6.1是圖6.8所示的完全二叉樹的順序存儲結(jié)構(gòu)，bt[O]為結(jié)點(diǎn)數(shù)目，b[7]的雙親、

左右孩子分別是bt[3]、bt[14]和bt[15]。

下標(biāo)01234567891011121314151617

17ABCDEFGIIIJKLMN0PQ

插入表6.1和圖6.8所不完全一義樹的順序存儲結(jié)構(gòu)

3.一般二叉樹的順序存儲

(1)具體方法

①將一般二叉樹添上一些“虛結(jié)點(diǎn)"，成為"完全二叉樹”

②為了用結(jié)點(diǎn)在向量中的相對位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，按完全二叉樹形式給結(jié)點(diǎn)

編號

③將結(jié)點(diǎn)按編號存入向量對應(yīng)分量，其中"虛結(jié)點(diǎn)"用"U'表示

【例】圖6-9中單支樹的順序存儲結(jié)構(gòu)如卜,圖

下標(biāo),0「，234567

bt3A6B(t)@eC

圖6-9中單支樹的順序存儲結(jié)構(gòu)

(2)優(yōu)點(diǎn)和缺點(diǎn)

①對完全二叉樹而言，順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。

②一般的二叉樹采用順序存儲結(jié)構(gòu)時(shí)，雖然簡單，但易造成存儲空間的浪費(fèi)。

【例】最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹需要2k-l個(gè)結(jié)點(diǎn)的存儲

空間。

③在對順序存儲的二叉樹做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。

4.二叉樹的順序存儲結(jié)構(gòu)類型定義

【參見參考書】

鏈?zhǔn)酱鎯Y(jié)構(gòu)

1.結(jié)點(diǎn)的結(jié)構(gòu)

二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除了存儲結(jié)點(diǎn)本

身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域Ichild和rchild,分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)

的結(jié)構(gòu)為:

IchiIddatarchiId

2.結(jié)點(diǎn)的類型說明

typedefcharDataType；〃用了1可根據(jù)具體應(yīng)用定義DataType的實(shí)際類型

typedefstructnode{

DataTypedata；

Structnode*lchild,*rchild；〃左右孩子指針

}BinTNode；〃結(jié)點(diǎn)類型

typedefBinTNode*BinTree；〃BinTree為指向BinTNode類型結(jié)點(diǎn)的指針類型

3.二叉鏈表（二叉樹的常用鏈?zhǔn)酱鎯Y(jié)構(gòu)）

在一棵二叉樹中，所有類型為BinTNode的結(jié)點(diǎn)，再加上一個(gè)指向開始結(jié)點(diǎn)（即根結(jié)點(diǎn)）的

BinTree型頭指針（即根指針）root,就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并將其稱為二叉鏈表。

【例】下面左圖所示二叉樹的二叉鏈表如下面中圖所示。

注意：

①一個(gè)二叉鏈表由根指針root惟一確定。若二叉樹為空，則root=NULL；若結(jié)點(diǎn)的某個(gè)

孩子不存在，則相應(yīng)的指針為空。

②具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中只有n-1個(gè)用來指示結(jié)點(diǎn)的左、

右孩子，其余的n+1個(gè)指針域?yàn)榭铡?/p>

4.帶雙親指針的二叉鏈表

經(jīng)常要在二叉樹中尋找某結(jié)點(diǎn)的雙親時(shí)，可在每個(gè)結(jié)點(diǎn)上再加一個(gè)指向其雙親的指針

parent,形成--個(gè)帶雙親指針的二叉鏈表。

【例】上面右圖是上面左圖所示的二叉樹的帶雙親指針的二叉鏈表。

注意：

二叉樹存儲方法的選擇，主要依賴于所要實(shí)施的各種運(yùn)算的頻度。

二叉樹的遍歷

遍歷概念

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次

訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。

遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。

遍歷方案

1.遍歷方案

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。

因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：

(1)訪問結(jié)點(diǎn)本身(N),

(2)遍歷該結(jié)點(diǎn)的左子樹(L),

(3)遍歷該結(jié)點(diǎn)的右子樹(R)。

以上三種操作有六種執(zhí)行次序：

NLR、LNR,LRN、NRL、RNL、RLR

注意：

前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序。

2.三種遍歷的命名

根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名：

①NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))

——訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

②LNR：中序遍歷(InorderTraversal)

——訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)。

③LRN：后序遍歷(PostorderTraversal)

——訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

注意：

由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node)、L(Leftsubtlee)和R(Rightsubtree)

又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和

后根遍歷。

遍歷算法

1.中序遍歷的遞歸算法定義：

若二叉樹非空，則依次執(zhí)行如下操作：

(1)遍歷左子樹；

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

(3)遍歷右子樹。

2.先序遍歷的遞歸算法定義：

若二叉樹非空，則依次執(zhí)行如下操作：

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

(2)遍歷左子樹；

(3)遍歷右子樹。

3.后序遍歷得遞歸算法定義:

若二叉樹非空，則依次執(zhí)行如下操作：

(D遍歷左子樹；

(2)遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。

4.中序遍歷的算法實(shí)現(xiàn)

用二叉鏈表做為存儲結(jié)構(gòu)，中序遍歷算法可描述為：

voidInOrder(BinTreeT)

{〃算法里①~⑥是為了說明執(zhí)行過程加入的標(biāo)號

①if(T){//如果二叉樹非空

②InOrder(T->lchiId)；

③printf(〃％c〃，T->data)；//訪問結(jié)點(diǎn)

(4)InOrder(T->rchiId);

⑤}

⑥}//InOrder

遍歷序列

1.遍歷二叉樹的執(zhí)行蹤跡

三種遞歸遍歷算法的搜索路線相同(如下圖虛線所示)。

具體線路為：

從根結(jié)點(diǎn)出發(fā)，逆時(shí)針沿著二叉樹外緣移動(dòng)，對每個(gè)結(jié)點(diǎn)均途徑三次，最后回到根結(jié)點(diǎn)。

遍歷二叉樹的搜索路線

2.遍歷序列

(1)中序序列

中序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)橹行蛐蛄?/p>

【例】中序遍歷上圖所示的二叉樹時(shí)，得到的中序序列為：

DBAECF

(2)先序序列

先序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)橄刃蛐蛄?/p>

【例】先序遍歷上圖所示的二叉樹時(shí)，得到的先序序列為：

ABDCEF

(3)后序序列

后序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)楹笮蛐蛄?/p>

【例】后序遍歷上圖所示的二叉樹時(shí)，得到的后序序列為：

DBEFCA

注意：

(1)在搜索路線中，若訪問結(jié)點(diǎn)均是第一次經(jīng)過結(jié)點(diǎn)時(shí)進(jìn)行的，則是前序遍歷；若訪問結(jié)

點(diǎn)均是在第二次(或第三次)經(jīng)過結(jié)點(diǎn)時(shí)進(jìn)行的，則是中序遍歷(或后序遍歷)。只要將搜索路線上

所有在第次、第二次和第三次經(jīng)過的結(jié)點(diǎn)分別列表，即可分別得到該二叉樹的前序序列、中序

序列和后序序列。

(2)上述三種序列都是線性序列，有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其余結(jié)點(diǎn)都有

且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。為了區(qū)別于樹形結(jié)構(gòu)中前趨(即雙親)結(jié)點(diǎn)和后繼(即孩子)

結(jié)點(diǎn)的概念，對上述三種線性序列，要在某結(jié)點(diǎn)的前趨和后繼之前冠以其遍歷次序名稱。

【例】上圖所示的二叉樹中結(jié)點(diǎn)C,其前序前趨結(jié)點(diǎn)是D,前序后繼結(jié)點(diǎn)是E；中序前趨結(jié)點(diǎn)是E,

中序后繼結(jié)點(diǎn)是F：后序前趨結(jié)點(diǎn)是F,后序后繼結(jié)點(diǎn)是Ao但是就該樹的邏輯結(jié)構(gòu)而言，C的前

趨結(jié)點(diǎn)是A,后繼結(jié)點(diǎn)是E和F。

二叉鏈表的構(gòu)造

1.基本思想

基于先序遍歷的構(gòu)造，即以二叉樹的先序序列為輸入構(gòu)造。

注意：

先序序列中必須加入虛結(jié)點(diǎn)以示空指針的位置。

【例】

建立上圖所示二叉樹，其輸入的先序序列是：ABDS

2.構(gòu)造算法

假設(shè)虛結(jié)點(diǎn)輸入時(shí)以空格字符表示，相應(yīng)的構(gòu)造算法為：

voidCreateBinTree(BinTree*T)

{〃構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實(shí)參(根指針)本身

charch；

if((ch=getchar())=='')*T=NULL；〃讀人空格，將相應(yīng)指針置空

else{〃讀人非空格

*T=(BinTNode*)malloc(sizeof(BinTNode))；〃生成結(jié)點(diǎn)

(*T)->data=ch；

CreateBinTree(&(*T)->1child)；〃構(gòu)造左子樹

CreateBinTree(&(*T)->rchiId)；〃構(gòu)造右子樹

)

}

注意：

調(diào)用該算法時(shí)，應(yīng)將待建立的二叉鏈表的根指針的地址作為實(shí)參。

【例】

設(shè)root是一根指針(即它的類型是BinTree),則調(diào)用CreateBinTree(&root)后root就指向了

已構(gòu)造好的二叉鏈表的根結(jié)點(diǎn)。

構(gòu)造二叉鏈表的其他方法【參見參考書目】

二叉樹建立過程見【動(dòng)畫演示】

二叉樹的應(yīng)用

【參見練習(xí)】

線索二叉樹

線索二叉樹概念

1.定義

n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)

在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針(這種附加的指針稱為"線索。

這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹

(ThreadedBinaryTree)?根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線

索二叉樹和后序線索二叉樹三種。

注意：

線索鏈表解決了二叉鏈表找左、右孩子困難的問題，出現(xiàn)了無法直接找到該結(jié)點(diǎn)在某種遍

歷序列中的前趨和后繼結(jié)點(diǎn)的問題。

2.線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)

線索鏈表中的結(jié)點(diǎn)結(jié)構(gòu)為:

IchildItagdatartagrchiId

其中：

Itag和rtag是增加的兩個(gè)標(biāo)志域，用來區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的

指針，還是指向其前趨或后繼的線索。

句U靖點(diǎn)的前甫的左！MT

田UzAtM3叫"右SM

3.線索二叉樹的表示

【例】下面(a)圖所示的中序線索二叉樹，其線索鏈表如下面(b)圖所示。

(a)中序線索:又樹

(h)中序線索鏈表

中序線索:叉樹及其存儲結(jié)構(gòu)

注意：

圖中的實(shí)線表示指針，虛線表示線索。

結(jié)點(diǎn)C的左線索為空，表示C是中序序列的開始結(jié)點(diǎn)，無前趨；

結(jié)點(diǎn)E的右線索為空，表示E是中序序列的終端結(jié)點(diǎn)，無后繼。

線索二叉樹中，?個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。

二叉樹的線索化

1.線索化和線索化實(shí)質(zhì)

將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化。

按某種次序?qū)⒍鏄渚€索化的實(shí)質(zhì)是：按該次序遍歷二叉樹，在遍歷過程中用線索取代空

指針。

具體過程可【參見動(dòng)畫演示】。

2.二叉樹的中序線索化

(1)分析

算法與中序遍歷算法類似。只需要將遍歷算法中訪問結(jié)點(diǎn)的操作具體化為建立正在訪問的

結(jié)點(diǎn)與其非空中序前趨結(jié)點(diǎn)間線索。

該算法應(yīng)附設(shè)一個(gè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)(pre的初值應(yīng)為NULL),而指針p

指示當(dāng)前正在訪問的結(jié)點(diǎn)。結(jié)點(diǎn)*pre是結(jié)點(diǎn)*p的前趨，而*p是*pre的后繼。

(2)將二叉樹按中序線索化的算法

typedefenum{Link,Thread}PointerTag；〃枚舉值Link和Thread分別為0,1

typedefstructnode{

DataTypcdata；

PointerTagItag,rtag；〃左右標(biāo)志

Structnode*lchild,*rchild；

}BinThrNode；\\線索二叉樹的結(jié)點(diǎn)類型

typedefBinThrNode*BinThrTree；

BinThrNode*pre=NULL；〃全局量

voidlnorderThreading(BinThrTreep)

{〃將二叉樹p中序線索化

if(p){〃p非空時(shí)，當(dāng)前訪問結(jié)點(diǎn)是*p

InordcrThrcading(p->lchild)；〃左子樹線索化

〃以下直至右子樹線索化之前相當(dāng)于遍歷算法中訪問結(jié)點(diǎn)的操作

p->ltag=(p->lchild)?Link：Thread；//左指針非空時(shí)左標(biāo)志為Link

//(即0),否則為Thread(即1)

p->rtag=(p->rchild)?Link：Thread；

*(pre){//若*p的前趨*pre存在

i?pre->rtag==Thread)〃若*p的前趨右標(biāo)志為線索

pre->rchild=p；〃令*pre的右線索指向中序后繼

if(p->ltag==Thread)//*p的左標(biāo)志為線索

p->lchild=pre；〃令*p的左線索指向中序前趨

}//完成處理*pre的線索

pre=p；〃令pre是下一訪問結(jié)點(diǎn)的中序前趨

InorderThrecding(p->rehild)；〃右子樹線索化

}//endif

}//InordcrThreading

(3)算法分析

和中序遍歷算法一樣，遞歸過程中對每結(jié)點(diǎn)僅做一次訪問。因此對于n個(gè)結(jié)點(diǎn)的二叉樹,

算法的時(shí)間復(fù)雜度亦為O(n)。

3.二叉樹的前序線索化和后序線索化

前序線索化和后序線索化算法與二叉樹的中序線索化類似，具體可【參見參考書工

線索二叉樹的運(yùn)算

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

(1)在中序線索二叉樹中，查找結(jié)點(diǎn)*P的中序后繼結(jié)點(diǎn)

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

①若*p的右子樹空(即p->rtag為Thread),則p->rchild為右線索，直接指向*p的中序后繼。

【例】下圖的中序線索二叉樹中，結(jié)點(diǎn)D的中序后繼是A。

(a)中序線索二義樹

(b)中序線索鏈表

中序線索:叉樹及其存儲結(jié)構(gòu)

②若*p的右子樹非空(即p->rtag為Link),貝lj*p的中序后繼必是其右子樹中第一個(gè)中序遍

歷到的結(jié)點(diǎn)。也就是從*p的右孩子開始，沿該孩子的左鏈往下查找，直至找到一個(gè)沒有左孩子

的結(jié)點(diǎn)為止，該結(jié)點(diǎn)是*p的右子樹中"最左下"的結(jié)點(diǎn)，即*P的中序后繼結(jié)點(diǎn)。

【例】上圖的中序線索二叉樹中：

A的中序后繼是F,它有右孩子；

F的中序后繼是H,它無右孩子；

B的中序后繼是D,它是B的右孩子。

在中序線索二義樹中求中序后繼結(jié)點(diǎn)的過程可【參見動(dòng)畫演示】,具體算法如下：

BinThrNode*InorderSuccessor(BinThrNode*p)

{//在中序線索樹中找結(jié)點(diǎn)*p的中序后繼，設(shè)p非空

BinThrNode*q；

if(p->rtag==Thread)//*p的右子樹為空

Returnp->rchiid；〃返回右線索所指的中序后繼

else{

q=p->rchild；//從*p的右孩子開始查找

while(q->ltag=Link)

q=q->lchild；〃左子樹非空時(shí)，沿左鏈往下查找

returnq；〃當(dāng)q的左子樹為空時(shí)，它就是最左下結(jié)點(diǎn)

}//endif

}

該算法的時(shí)間復(fù)雜度不超過樹的高度h,即0(h)。

(2)在中序線索二叉樹中查找結(jié)點(diǎn)*p的中序前趨結(jié)點(diǎn)

中序是一種對稱序，故在中序線索二又樹中查找結(jié)點(diǎn)*p的中序前趨結(jié)點(diǎn)與找中序后繼結(jié)點(diǎn)

的方法完全對稱。具體情形如下：

①若*p的左子樹為空，則p->lchild為左線索，直接指向*p的中序前趨結(jié)點(diǎn)；

【例】上圖所示的中序線索二叉樹中，F(xiàn)結(jié)點(diǎn)的中序前趨結(jié)點(diǎn)是A

②若*p的左子樹非空，則從*p的左孩子出發(fā)，沿右指針鏈往下查找，直到找到一個(gè)沒有右

孩子的結(jié)點(diǎn)為止。該結(jié)點(diǎn)是*p的左子樹中"最右下"的結(jié)點(diǎn)，它是*p的左子樹中最后一個(gè)中序遍

歷到的結(jié)點(diǎn)，即*p的中序前趨結(jié)點(diǎn)。

【例】上圖所示中序線索二叉樹中，結(jié)點(diǎn)E左子樹非空，其中序前趨結(jié)點(diǎn)是I

在中序線索二叉樹中求中序前趨結(jié)點(diǎn)的過程可【參見動(dòng)畫演示】,具體算法如下：

BinThrNode*lnorderpre(BinThrNode*p)

{〃在中序線索樹中找結(jié)點(diǎn)*p的中序前趨，設(shè)p非空

BinThrNode*q；

if(p->ltag=Thread)//*p的左子樹為空

returnp->lchild：〃返回左線索所指的中序前趨

else{

q=p->lchild：〃從*p的左孩子開始查找

while(q->rtag==Link)

q=q->rchild；〃右子樹非空時(shí)，沿右鏈往下查找

returnq：〃當(dāng)q的右子樹為空時(shí)，它就是最右下結(jié)點(diǎn)

}//endif

}

由上述討論可知：對于非線索二叉樹，僅從*p出發(fā)無法找到其中序前趨(或中序后繼)，而

必須從根結(jié)點(diǎn)開始中序遍歷，才能找到*p的中序前趨(或中序后繼)。線索二叉樹中的線索使得查

找中序前趨和中序后繼變得簡單有效。

(3)在后序線索二叉樹中，查找指定結(jié)點(diǎn)*p的后序前趨結(jié)點(diǎn)

在后序線索二叉樹中，查找指定結(jié)點(diǎn)*p的后序前趨結(jié)點(diǎn)的具體規(guī)律是：

①若*P的左子樹為空，則p->lchild是前趨線索，指示其后序前趨結(jié)點(diǎn)。

【例】在下圖所示的后序線索二叉樹中，H的后序前趨是B,F的后序前趨是C。

后序戰(zhàn)索二叉樹

②若*P的左子樹非空，則p->lchild不是前趨線索。由于后序遍歷時(shí)，根是在遍歷其左右子

樹之后被訪問的，故*P的后序前趨必是兩子樹中最后一個(gè)遍歷結(jié)點(diǎn)。

當(dāng)*P的右子樹非空時(shí)，*p的右孩子必是其后序前趨

【例】在上圖所示的后序線索二叉樹中，A的后序前趨是E；

當(dāng)*p無右子樹時(shí)，*p的后序前趨必是其左孩子

【例】在上圖所示的后序線索二叉樹中，E的后序前趨是F

（4）在后序線索二叉樹中，查找指定結(jié)點(diǎn)*p的后序后繼結(jié)點(diǎn)

具體的規(guī)律：

①若*p是根，則*p是該二叉樹后序遍歷過程中最后個(gè)訪問到的結(jié)點(diǎn)。*p的后序后繼為

空

②若*p是其雙親的右孩子，則*p的后序后繼結(jié)點(diǎn)就是其雙親結(jié)點(diǎn)

【例】上圖所示的后序線索二叉樹中，E的后序后繼是A。

③若*p是其雙親的左孩子，但*P無右兄弟，*p的后序后繼結(jié)點(diǎn)是其雙親結(jié)點(diǎn)

【例】上圖所示的后序線索二叉樹中，F(xiàn)的后序后繼是E。

④若*p是其雙親的左孩子，但*p有右兄弟，則*p的后序后繼是其雙親的右子樹中第一個(gè)

后序遍歷到的結(jié)點(diǎn)，它是該子樹中"最左下的葉結(jié)點(diǎn)"

【例】上圖所示的后序線索二叉樹中，B的后序后繼是雙親A的右子樹中最左下的葉結(jié)點(diǎn)H

注意：

F是孩子樹中"最左下"結(jié)點(diǎn)，但它不是葉子。

由上述討論中可知：在后序線索樹中，僅從*p出發(fā)就能找到其后序前趨結(jié)點(diǎn)：要找*p的后

序后繼結(jié)點(diǎn)，僅當(dāng)*p的右子樹為空時(shí)，才能直接由*p的右線索p->rchild得到。否則必須知道*p

的雙親結(jié)點(diǎn)才能找到其后序后繼。因此，如果線索二叉樹中的結(jié)點(diǎn)沒有指向其雙親結(jié)點(diǎn)的指針，

就可能要從根開始進(jìn)行后序遍歷才能找到結(jié)點(diǎn)*P的后序后繼。由此，線索對查找指定結(jié)點(diǎn)的后

序后繼并無多大幫助。

（5）在前序線索二叉樹中，查找指定結(jié)點(diǎn)*p的前序后繼結(jié)點(diǎn)

【參見練習(xí)】

（6）在前序線索二叉樹中，查找指定結(jié)點(diǎn)*p的前序前趨結(jié)點(diǎn)

【參見參考書】

在前序線索二叉樹中，找某一點(diǎn)*P的前序后繼也很簡單，僅從*P出發(fā)就可以找到；但找其

前序前趨也必須知道*P的雙親結(jié)點(diǎn)。當(dāng)樹中結(jié)點(diǎn)未設(shè)雙親指針時(shí)，同樣要進(jìn)行從根開始的前序

遍歷才能找到結(jié)點(diǎn)*P的前序前趨。

2.遍歷線索二叉樹

遍歷某種次序的線索二叉樹，只要從該次序下的開始結(jié)點(diǎn)開發(fā)，反復(fù)找到結(jié)點(diǎn)在該次序下的

后繼，直至終端結(jié)點(diǎn)。

遍歷中序線索二叉樹算法：

voidTraverseInorderThrTrec(BinThrTrecp)

{//遍歷中序線索二叉樹

iRp){〃樹非空

while(p->ltag==Link)

p=p->lchild；〃從根往下找最左下結(jié)點(diǎn)，即中序序列的開始結(jié)點(diǎn)

do{

printf("%c"，p->data)；〃訪問結(jié)點(diǎn)

p=InorderSuccessor(p)；〃找*p的中序后繼

}while(p)

}//endif

}//TraverselnorderThrTree

分析：

①中序序列的終端結(jié)點(diǎn)的右線索為空，所以do語句的終止條件是p=NULL。

②該算法的時(shí)間復(fù)雜性為0(n)。因?yàn)槭欠沁f歸算法，常數(shù)因子上小于遞歸的遍歷算法。因

此，若對一棵二叉樹要經(jīng)常遍歷，或查找結(jié)點(diǎn)在指定次序下的前趨和后繼，則應(yīng)采用線索鏈表作

為存儲結(jié)構(gòu)為宜。

③以上介紹的線索二叉樹是一種全線索樹(即左右線索均要建立)。許多應(yīng)用中只要建立左

右線索中的一種。

④若在線索鏈表中增加一個(gè)頭結(jié)點(diǎn)，令頭結(jié)點(diǎn)的左指針指向根，右指針指向其遍歷序列的

開始或終端結(jié)點(diǎn)會(huì)更方便。

樹和森林

樹、森林與二叉樹的轉(zhuǎn)換

樹或森林與二叉樹之間有一個(gè)自然的一一對應(yīng)關(guān)系。任何一個(gè)森林或一棵樹可惟一地對應(yīng)

到一棵二叉樹；反之，任何一棵二叉樹也能惟一地對應(yīng)到一個(gè)森林或一棵樹。

1.樹、森林到二叉樹的轉(zhuǎn)換

(1)將樹轉(zhuǎn)換為：叉樹

樹中每個(gè)結(jié)點(diǎn)最多只有?個(gè)最左邊的孩子(長子)和一個(gè)右鄰的兄弟。按照這種關(guān)系很自然

地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹：

①在所有兄弟結(jié)點(diǎn)之間加一連線；

②對每個(gè)結(jié)點(diǎn)，除了保留與其長子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線。

【例11下面(a)圖所示的樹可轉(zhuǎn)換為(c)圖所示的二叉樹。具體轉(zhuǎn)換過程可【參見動(dòng)畫演示】

(a)(b)(c)

樹轉(zhuǎn)化成二又樹

注意：

由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。

(2)將一個(gè)森林轉(zhuǎn)換為二叉樹

具體方法是：

①將森林中的每棵樹變?yōu)槎鏄?/p>

②因?yàn)檗D(zhuǎn)換所得的二叉樹的根結(jié)點(diǎn)的右子樹均為空，故可將各二叉樹的根結(jié)點(diǎn)視為兄弟從

左至右連在一起，就形成了--棵二叉樹。

【例2】下圖中，左邊包含三棵樹的森林可轉(zhuǎn)換為右邊的二叉樹。

森林轉(zhuǎn)化為：又樹

具體轉(zhuǎn)換過程可【參見動(dòng)畫演示】

2.二叉樹到樹、森林的轉(zhuǎn)換

把二又樹轉(zhuǎn)換到樹和森林自然的方式是：若結(jié)點(diǎn)x是雙親y的左孩子，則把x的右孩子,

右孩子的右孩子，…，都與y用連線連起來，最后去掉所有雙親到右孩子的連線。

［例3］下圖的森林就是由例2中二叉樹轉(zhuǎn)換成的。

1周(c)的：一叉樹轉(zhuǎn)化為森林

具體轉(zhuǎn)換過程可【參見動(dòng)畫演示】

樹的存儲結(jié)構(gòu)

本節(jié)僅討論樹的三種常用表示法。

1.雙親鏈表表示法

雙親鏈表表示法利用樹中每個(gè)結(jié)點(diǎn)的雙親唯一性，在存儲結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附

設(shè)一個(gè)指向其雙親的指針parent,惟一地表示任何一棵樹。

（1）雙親鏈表表示法的實(shí)現(xiàn)

方法①用動(dòng)態(tài)鏈表實(shí)現(xiàn)

方法②用向量表示——更為方便

（2）雙親鏈表向量表示的形式說明

^defineMaxTreeSize100〃向量空間的大小，由用戶定義

typedefcharDataType；〃應(yīng)由用戶定義

typedefstruct{

DataTypedata；〃結(jié)點(diǎn)數(shù)據(jù)

intparent；〃雙親指針，指示結(jié)點(diǎn)的雙親在向量中的位置

JPTreeNode；

typedefstruct{

PTreeNodenodes[MaxTreeSize];

intn；〃結(jié)點(diǎn)總數(shù)

JPTree；

PTreeT；//T是雙親鏈表

注意：

若T.nodes[i].parent=j,則T.nodes[i]的雙親是T.nodes[j]0

（3）雙親鏈表表示實(shí)例

【例】圖6.17（a）的雙親鏈表表示如下面數(shù)組所示。

MaxTrecSizc-1

下標(biāo)01234567891

ABCDEFG11IJ???

-1000112333???

圖6.17樹轉(zhuǎn)化為.又樹(a)所示.義樹的雙親鏈表T

分析：

E和F所在結(jié)點(diǎn)的雙親域是1,它們的雙親結(jié)點(diǎn)在向量中的位置是1,即B是它們的雙親。

注意：

①根無雙親，其parent域?yàn)門。

②雙親鏈表表示法中指針parent向上鏈接，適合求指定結(jié)點(diǎn)的雙親或祖先(包括根)；求

指定結(jié)點(diǎn)的孩子或其它后代時(shí)，可能要遍歷整個(gè)數(shù)組。

2.孩子鏈表表示法

(1)結(jié)點(diǎn)結(jié)構(gòu)

①定長結(jié)點(diǎn)

即樹中每個(gè)結(jié)點(diǎn)均按樹的度k來設(shè)置指針。

n個(gè)結(jié)點(diǎn)的樹-共有n*k個(gè)指針域，而樹中只有n-1條邊，故樹中的空指針數(shù)目為

kn-(n-l)=n(k-l)+l(k越大，浪費(fèi)的空間越多)。

②不定長結(jié)點(diǎn)

即樹中每個(gè)結(jié)點(diǎn)按本結(jié)點(diǎn)的度來設(shè)置指針數(shù)，并在結(jié)點(diǎn)中增設(shè)一個(gè)度數(shù)域degree指出該

結(jié)點(diǎn)包含的指針數(shù)。

各結(jié)點(diǎn)不等長，雖然節(jié)省了空間，但是給運(yùn)算帶來不便。

(2)孩子鏈表表示法

孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表,并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的

頭指針存放在一個(gè)向量中。

①孩子鏈表表示法的類型說明

〃以下的DataType和MaxTreeSize由用戶定義

typedefstructCNode{〃子鏈表結(jié)點(diǎn)

intchild；〃孩子結(jié)點(diǎn)在向量中對應(yīng)的序號

structCNode*next；

JCNode；

typedefstruct{

DataTypedata；〃存放樹中結(jié)點(diǎn)數(shù)據(jù)

CNode*firstchild；〃孩子鏈表的頭指針

JPTNode；

typedefstruct{

PTNodenodes[MaxTreeSize]；

Intn,root；〃n為結(jié)點(diǎn)總數(shù)，root指出根在向量中的位置

(CTree；

CtreeT；//T為孩子鏈表表示

注意：

當(dāng)結(jié)點(diǎn)T.nodesli]為葉子時(shí),其孩子鏈表為空，BPT.nodes[i].firstchild=NULL<)

②孩子鏈表表示法實(shí)例

【例】圖6.17(a)所示樹的孩子鏈表表示T如下面(a)圖所示。

A

圖6.17樹轉(zhuǎn)化為：叉樹(a)中樹的孩子鏈表表示法

注意:

①孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們在向量空間的序號。

②與雙親鏈表表示法相反，孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算，但不便于

實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算。

③將雙親鏈表表示法和孩廣鏈表表示法結(jié)合起來，可形成雙親孩子鏈表表示法。

【例】上面的(b)圖就是用雙親鏈表表示法來存儲圖6.17(a)中的樹。

3.孩子兄弟鏈表表示法

(1)表示方法

在存儲結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域

leftmostchild和rightsibling,即可得樹的孩子兄弟鏈表表示。

(2)表示實(shí)例

【例】圖6.17(a)中樹的孩子兄弟鏈表如下圖所示。

A

圖6.17(a)

圖6.17樹轉(zhuǎn)化為：叉樹(a)中樹的孩子兄弟鏈表

注意:

這種存儲結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈表表示完全一樣。可利用二叉樹的算法

來實(shí)現(xiàn)對樹的操作。

樹的遍歷

1.樹T的前序遍歷定義；

若樹T非空，則：

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

②依次前序遍歷根R的各子樹T”

2.樹的后序遍歷定義：

若樹T非空，則:

①依次后序遍歷根T的各子樹r,Tz,???,Tk；

②訪問根結(jié)點(diǎn)Ro

【例】對下面的(a)圖中的樹進(jìn)行前序遍歷和后序遍歷，得到的前序序列和后序序列分別是ABCDE

和BDCEAo

AA

樹和對應(yīng)的二義樹

注意：

①前序遍歷一棵樹恰好等價(jià)于前序遍歷該樹對應(yīng)的二叉樹

②后序遍歷樹恰好等價(jià)于中序遍歷該樹對應(yīng)的二叉樹。

森林的兩種遍歷方法

1.前序遍歷森林

若森林非空，則：

①訪問森林中第一棵樹的根結(jié)點(diǎn)；

②前序遍歷第一棵樹中根結(jié)點(diǎn)的各子樹所構(gòu)成的森林

③前序遍歷除第一棵樹外其它樹構(gòu)成的森林。

2.后序遍歷森林

若森林非空，貝IJ：

①后序遍歷森林中第?棵樹的根結(jié)點(diǎn)的各子樹所構(gòu)成的森林；

②訪問第一棵樹的根結(jié)點(diǎn)；

③后序遍歷除第一棵樹外其它樹構(gòu)成的森林。

注意：

①前序遍歷森林等同于前序遍歷該森林對應(yīng)的二叉樹

②后序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹

【例】對下面(a)圖中所示的森林進(jìn)行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序

列分別為ABCDEFICJH和BDCAIFJGHE?而(b)圖所示二叉樹的前序序列和中序序列也分別為

ABCDEFICJH和BDCAIFJGHE,

(a)森林(b)對應(yīng)的.又樹

森林和對陶的二叉樹

③當(dāng)用二叉鏈表作樹和森林的存儲結(jié)構(gòu)時(shí)，樹和森林的前序遍歷和后遍歷，可用二叉樹

的前序遍歷和中序遍歷算法來實(shí)現(xiàn)。

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

最優(yōu)二叉樹概念

1.樹的路徑長度

樹的路徑長度是從樹根到樹中每一結(jié)點(diǎn)的路徑長度之和。在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完

全二叉樹的路徑長度最短。

2.樹的帶權(quán)路徑長度(WeightedPathLengthofTree,簡記為WPL)

結(jié)點(diǎn)的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點(diǎn)的?個(gè)有某種意義的實(shí)數(shù)。

結(jié)點(diǎn)的帶權(quán)路徑長度：結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。

樹的帶權(quán)路徑長度(WeightedPathLengthofTree)：定義為樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長

度之和，通常記為:

?！鲂?，丸

其中:

n表示葉子結(jié)點(diǎn)的數(shù)目

w；和L分別表示葉結(jié)點(diǎn)k,的權(quán)值和根到結(jié)點(diǎn)k：之間的路徑長度。

樹的帶權(quán)路徑長度亦稱為樹的代價(jià)。

3.最優(yōu)二叉樹或哈夫曼樹

在權(quán)為W,wz,…，的n個(gè)葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小(即代價(jià)最

小)的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。

【例】給定4個(gè)葉子結(jié)點(diǎn)a,b,c和d,分別帶權(quán)7,5,2和4。構(gòu)造如下圖所示的三棵二叉

樹(還有許多棵)，它們的帶權(quán)路徑長度分別為：

(a)WPL=7*2+5*2+2*2+4*2=36

(b)WPL=7*3+5*3+2*1+4*2=46

(c)WPL=7*1+5*2+2*3+4*3=35

具有不同WPL的二叉樹(結(jié)點(diǎn)旁的數(shù)字為權(quán))

注意：

①葉子上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)

二叉樹。

②最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。

③最優(yōu)二叉樹的形態(tài)不唯一，WPL最小

構(gòu)造最優(yōu)二叉樹

1.哈夫曼算法

哈夫曼首先給出了對于給定的葉子數(shù)目及其權(quán)值構(gòu)造最優(yōu)二叉樹的方法，故稱其為哈夫曼

算法。其基本思想是：

(1)根據(jù)給定的n個(gè)權(quán)值wi,w2,???,w”構(gòu)成n棵二叉樹的森林F={T”T2,???,T?),其中每

棵二叉樹"中都只有一個(gè)權(quán)值為w,的根結(jié)點(diǎn)，其左右子樹均空。

(2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(當(dāng)這樣的樹不止兩棵樹時(shí)，可以從中任選兩

棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個(gè)新結(jié)點(diǎn)作為新樹的

根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關(guān)緊要)，將這兩個(gè)孩子的權(quán)

值之和作為新樹根的權(quán)值。

(3)對新的森林F重復(fù)(2),直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。

用哈夫曼算法構(gòu)造哈夫曼樹的過程見【動(dòng)畫演示】。

注意：

①初始森林中的n棵二叉樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子

②n個(gè)葉子的哈夫曼樹要經(jīng)過n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共

有2n-l個(gè)結(jié)點(diǎn)。

③哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為1的分支結(jié)點(diǎn)。

2.哈夫曼樹的存儲結(jié)構(gòu)及哈夫曼算法的實(shí)現(xiàn)

(D哈夫曼樹的存儲結(jié)構(gòu)

用一個(gè)大小為2n-l的向量來存儲哈夫曼樹中的結(jié)點(diǎn)，其存儲結(jié)構(gòu)為：

^definen100//葉子數(shù)目

#definem2*nT//樹中結(jié)點(diǎn)總數(shù)

typedefstruct{〃結(jié)點(diǎn)類型

floatweight；〃權(quán)值，不妨設(shè)權(quán)值均大于零

intIchild,rchild,parent；〃左右孩子及雙親指針

}HTNode；

typedefHTNodeHuffmanTree[m]；〃HuffmanTree是向量類型

注意：

因?yàn)镃語言數(shù)組的下界為0,故用T表示空指針。樹中某結(jié)點(diǎn)的lchild>rchild和parent

不等于T時(shí)，它們分別是該結(jié)點(diǎn)的左、右孩子和雙親結(jié)點(diǎn)在向量中的下標(biāo)。

這里設(shè)置parent域有兩個(gè)作用：其一是使查找某結(jié)點(diǎn)的雙親變得簡單；其二是可通過判

定parent的值是否為T來區(qū)分根與非根結(jié)點(diǎn)。

(2)哈夫曼算法的簡要描述

在上述存儲結(jié)構(gòu)上實(shí)現(xiàn)的哈夫曼算法可大致描述為(設(shè)T的類型為HuffmanTree)：

(1)初始化

將T[0.?mT]中2n-l個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空(即置為-1),權(quán)值置為0。

(2)輸人

讀人n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量(即T[0..n-1])中。它們是初始森林中n個(gè)

孤立的根結(jié)點(diǎn)上的權(quán)值。

(3)合并

對森林中的樹共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放人向量T的第i個(gè)分量中

(nWiWm-1)。每次合并分兩步：

①在當(dāng)前森林T[0.?iT]的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn)[pl]和T[p2]

作為合并對象，這里OWpl,p2Wi-L

②將根為T[pl]和T[p2]的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點(diǎn)

T[i]?具體操作:

將T[pl]和T[p2]的parent置為i,

將T[i]的Ichild和rchild分別置為pl和p2

新結(jié)點(diǎn)T[i]的權(quán)值置為T[pl]和