第6章 樹(shù)教學(xué)課件

第6章樹(shù)

?2二叉樹(shù)

6.3遍歷二叉樹(shù)

第六章樹(shù)

第6章樹(shù)

樹(shù)形結(jié)構(gòu)是一種應(yīng)用十分廣泛和重要的非線性數(shù)據(jù)結(jié)

構(gòu)，是一種以分支關(guān)系定義的層次結(jié)構(gòu)。在這種結(jié)構(gòu)中，

每個(gè)數(shù)據(jù)元素至多只有一個(gè)前趨，但可以有多個(gè)后繼；數(shù)

據(jù)元素之間的關(guān)系是一對(duì)多的層次關(guān)系。樹(shù)形結(jié)構(gòu)主要用

于描述客觀世界中具有層次結(jié)構(gòu)的數(shù)據(jù)關(guān)系。

本章重點(diǎn)討論樹(shù)與二叉樹(shù)的概念、性質(zhì)、存貯結(jié)構(gòu)及

其各種運(yùn)算，并研究一般樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換關(guān)系；

此外，作為樹(shù)形結(jié)構(gòu)的應(yīng)用，介紹了哈夫曼樹(shù)及其哈夫曼

編碼。

第六章樹(shù)

ti6.1樹(shù)的基本概念

6.1.1樹(shù)的定義及表示

1、樹(shù)形結(jié)構(gòu)示例

張紅軍

(a)一個(gè)家族結(jié)構(gòu)示意圖

第六章樹(shù)

校長(zhǎng)辦公室

計(jì)算機(jī)學(xué)院科研處人事處財(cái)務(wù)處教務(wù)處

計(jì)算機(jī)系電信系數(shù)學(xué)系人事科勞資科教務(wù)科教材科

(b)行政結(jié)構(gòu)樹(shù)形示意圖

6.1樹(shù)形結(jié)構(gòu)示意圖

第六章樹(shù)—

--------------__

■2、樹(shù)的定義

樹(shù)（Tree）是n（n>0）個(gè)結(jié)點(diǎn)的有限集合T,當(dāng)n=0時(shí)不焉用樹(shù)，

否則，稱為非空樹(shù)。在任一棵非空樹(shù)中：

（1）有且僅有一個(gè)稱為樹(shù)根的結(jié)點(diǎn)。

（2）除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的集

合TLT2,…，Tm,其中每一個(gè)集合本身又都是一棵樹(shù)，一般稱為

根的子樹(shù)。

樹(shù)的定義是一個(gè)遞歸的定義，它反映了樹(shù)的固有特性，即一棵樹(shù)

由若干棵子樹(shù)構(gòu)成，且各子樹(shù)間互不相交，而每棵子樹(shù)又由若干棵更

小的子樹(shù)構(gòu)成。例如，在圖6.2中，（a）是只有一個(gè)根結(jié)點(diǎn)的樹(shù)；（b）

是有8個(gè)結(jié)點(diǎn)的一般樹(shù)，其中A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子

集：T1={B、E、F},T2={C},T3={D、G、H},而且它們都是A的子

樹(shù)，且其本身也是一棵樹(shù)。

第六章樹(shù)

(a)只有根結(jié)點(diǎn)的樹(shù)(b)一般樹(shù)

6.2樹(shù)示例

樹(shù)的表示方法有樹(shù)形表示、集合表示、凹入表示和廣義表等4種。圖

6.3給出了樹(shù)的其它表示形式，如(a)為集合表示法或范氏圖法，(b)

為凹入表示法或縮格法，(c)為廣義表表示法或嵌套括弧法等。

ni/〃/〃/〃〃/〃〃〃〃〃/“/,

D[〃〃/〃〃〃〃〃〃//

D|〃〃〃/〉必〃〃〃〃

E〃〃〃〃〃〃

I7177777777777

p[7777777777777777777(A(B(E,F),C,D(G,H)))

D1〃〃〃〃〃〃〃〃〃/

IcI卜I〃〃〃〃〃/

H

11!\?/〃//〃//〃//〃//〃if/

(a)集合表示(b)凹入表示(c)廣義表表示

圖6.3樹(shù)的其它表示法

第六章樹(shù)

|6.L2樹(shù)的常用術(shù)語(yǔ)K*

樹(shù)的結(jié)點(diǎn)：是指一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支，通常用一

個(gè)結(jié)構(gòu)體或記錄來(lái)描述，在樹(shù)形表示中用一個(gè)圓圈及短線表示。

結(jié)點(diǎn)的度：是指結(jié)點(diǎn)的子樹(shù)數(shù)目。

葉子或終端結(jié)點(diǎn)：是指度為零的結(jié)點(diǎn)。

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

樹(shù)的度：是指樹(shù)中各結(jié)點(diǎn)度的最大值。

有時(shí)，在實(shí)際應(yīng)用中也引用家族樹(shù)中的一些習(xí)慣用語(yǔ)來(lái)描述樹(shù)，如

孩子、雙親、祖先、子孫和兄弟等。如將某結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)

的孩子，相應(yīng)地，將該結(jié)點(diǎn)稱為孩子的雙親；同一個(gè)雙親的孩子之間互

稱為兄弟等等。祖先則是從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過(guò)分支上的所有結(jié)點(diǎn)，

而以某結(jié)點(diǎn)作為根的子樹(shù)中任一個(gè)結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。

第六章樹(shù)________________________________

I

t結(jié)點(diǎn)的層次：從根開(kāi)始定義，根為第一層，根的孩子為囂三盤(pán)，

以此類推，即設(shè)根結(jié)點(diǎn)的層數(shù)為1,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的

層數(shù)加1。若某結(jié)點(diǎn)在第i層，則其孩子結(jié)點(diǎn)就在第i+1層。

樹(shù)的深度或高度：是指樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。

路徑：若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列瓦，k2,kj,使得ki是ki+1的

雙親(l<i<j),則稱該結(jié)點(diǎn)序列是從k］到kj的一條路徑，且路徑的長(zhǎng)

度為j-L即等于路徑上分支的數(shù)目。在樹(shù)形表示中，路徑表示從kl出

發(fā)自上而下地通過(guò)k2，k3,與各結(jié)點(diǎn)。

有序樹(shù)和無(wú)序樹(shù)：若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左至右有序

且不能交換，則稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)。圖6.4給出了兩棵

不同的有序樹(shù)。

，森林：是指m（m>0）棵互不相交的樹(shù)的集合。

顯然，樹(shù)形結(jié)構(gòu)不同于線性結(jié)構(gòu)。在樹(shù)中，一個(gè)結(jié)點(diǎn)至多個(gè)直

接前趨（雙親），卻可以有多個(gè)直接后繼（孩子），即結(jié)點(diǎn)之間的關(guān)系不

象線性結(jié)構(gòu)中的結(jié)點(diǎn)關(guān)系是一一對(duì)應(yīng)關(guān)系，而是呈現(xiàn)出一對(duì)多的層次關(guān)系。

第六章樹(shù)

樹(shù)的基本運(yùn)算i9W

(1)setnull(T)：置T為空樹(shù)，即初始化一棵樹(shù)T。

(2)root(T)或root(x)：求根函數(shù)。

(3)parent(T,x)：求雙親函數(shù)。

(4)child(T,x,i)：求孩子結(jié)點(diǎn)函數(shù)。

(5)rsibling(T,x)：求右兄弟函數(shù)。

(6)create(x,F)：建樹(shù)函數(shù)。

(7)delchild(x,i)：子樹(shù)刪除操作。

(8)addchild(y,i,x)：插入子樹(shù)操作。

(9)traverse(T)：樹(shù)的遍歷操作。

第六章樹(shù)

6.2二叉樹(shù)

二叉樹(shù)(BinaryTree)是另一種重要的樹(shù)形結(jié)構(gòu)，在

實(shí)際應(yīng)用中具有重要的意義。本節(jié)將詳細(xì)地討論二叉樹(shù)的

定義、重要性質(zhì)、存儲(chǔ)方式、運(yùn)算及其應(yīng)用。

第六章樹(shù)

6.2.1二叉樹(shù)的概念及運(yùn)算

1、二叉樹(shù)定義

二叉樹(shù)是n(>0)個(gè)結(jié)點(diǎn)的有限集合，這個(gè)集合可以是空集合，

或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱為根的左子樹(shù)和右子樹(shù)

的二叉樹(shù)組成。顯然，由定義可知，二叉樹(shù)具有遞歸性質(zhì)，它的特

點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)即二叉樹(shù)中任何結(jié)點(diǎn)的度數(shù)不大于2,

而且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。應(yīng)該指出

的是，二叉樹(shù)與樹(shù)是兩個(gè)不同的概念，它不是樹(shù)的特殊情形，例如，

在圖6.5中，(a)和(b)所示的兩棵二叉樹(shù)雖然與(c)所示的一般

樹(shù)相似，但卻不等同于這棵一般樹(shù)。

第六章樹(shù)

(a)二叉樹(shù)1(b)二叉樹(shù)2(c)一般樹(shù)

圖6.5二叉樹(shù)與度為2的一般樹(shù)的區(qū)別舉例

第六章樹(shù)

2、二叉樹(shù)基本形態(tài)

（a）空樹(shù)（b）只有根結(jié)點(diǎn)（c）只有左子樹(shù)（d）只有右子樹(shù)（e）左

空

圖6.6二叉樹(shù)的五種基本形態(tài)

兩種特殊形態(tài)的二叉樹(shù)：滿二叉樹(shù)和完全二叉樹(shù)。

第六章樹(shù)

T)滿二叉樹(shù)是指一棵深度為h且有2人1個(gè)結(jié)點(diǎn)的二叉前，笳露.7(a)

T所示是一棵深度為3的滿二叉樹(shù)。

(2)完全二叉樹(shù)：對(duì)滿二叉樹(shù)中的結(jié)點(diǎn)按照從根結(jié)點(diǎn)起，自上而下，

自左至右的約定進(jìn)行連續(xù)編號(hào)，一棵深度為h,有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且

僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為h的滿二叉樹(shù)中的編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)

時(shí)，稱之為完全二叉樹(shù)，如圖6.7(b)所示為一棵深度為3的完全二叉樹(shù)，

而圖6.7(c)所示就不是完全二叉樹(shù)。

(3)滿二叉樹(shù)的每一層上具有最大的結(jié)點(diǎn)數(shù)，它不存在度為1的結(jié)點(diǎn)，

所有葉子結(jié)點(diǎn)均在第h層上。

(4)完全二叉樹(shù)的特點(diǎn)是所有葉子結(jié)點(diǎn)都只可能在最大的兩層出現(xiàn)，

第i(i0h-l)層含有2口個(gè)結(jié)點(diǎn)，第h層上的結(jié)點(diǎn)都集中在該層最左邊的位置

上，換句話說(shuō)，完全二叉樹(shù)上的結(jié)點(diǎn)編號(hào)與同深度的滿二叉樹(shù)對(duì)應(yīng)位置的

結(jié)點(diǎn)編號(hào)相同。滿二叉樹(shù)是完全二叉樹(shù)的特殊情形，它一定是完全二叉樹(shù)，

而完全二叉樹(shù)不一定是滿二叉樹(shù)。

第六章樹(shù)

(c)非完全二叉樹(shù)

第六章樹(shù)

二叉樹(shù)的基本運(yùn)算

(1)setnull(bt)：置bt為空二叉樹(shù)-

(2)求根函數(shù)root(bt)或root(x)(3)求雙親函數(shù)parent(bt,x)

(4)求孩子結(jié)點(diǎn)函數(shù)Ichiki(bt,x)和rchild(bt,x)

(5)插入運(yùn)算addlchild(b,x,y)和addrchild(bt,x,y)

(6)二叉樹(shù)建立運(yùn)算create(x,Ibt,rbt)

(7)刪除子樹(shù)運(yùn)算dellchild(bt,x)和delrchild(bt,x)

(8)遍歷運(yùn)算traverse(bt)

第六章樹(shù)

6.2.2二叉樹(shù)的性質(zhì).

性質(zhì)1在二叉樹(shù)的第i層上至多有2H結(jié)點(diǎn)(應(yīng)1)。

性質(zhì)2深度為h的二叉樹(shù)至多有2?1個(gè)結(jié)點(diǎn)(h>l)o

性質(zhì)3對(duì)任何一棵二叉樹(shù)T,如果其終端結(jié)點(diǎn)數(shù)為%,度為2的結(jié)點(diǎn)數(shù)為嗎，

則n0=n2+lo

性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|_log2n」+l。

性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)(其深度為,按照

從根結(jié)點(diǎn)起，自上而下，從左到右的約定對(duì)所有結(jié)點(diǎn)從1到n進(jìn)行編號(hào)，

則對(duì)于任意的編號(hào)為i的結(jié)點(diǎn)(l<i<n)有以下性質(zhì)：

(1)如果i=L則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>l,則其雙親的

編號(hào)是㈤2」。

(2)如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))，否則其左孩子

的編號(hào)是2i。

(3)如果2i+l>n,則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子的編號(hào)是2i+L

(4)若i為奇數(shù)且不為1,則該結(jié)點(diǎn)左兄弟的編號(hào)是i?L否則無(wú)左兄弟。

(5)若i為偶數(shù)且小于n,則該結(jié)點(diǎn)右兄弟的編號(hào)是i+L否則無(wú)右兄弟。

第六章樹(shù)

J|623二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

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

二叉樹(shù)的順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的數(shù)

據(jù)元素。

(1)完全二叉樹(shù)

對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，從樹(shù)根結(jié)點(diǎn)起，自上層到下層，

每層自左至右地給所有結(jié)點(diǎn)編號(hào)，然后將完全二叉樹(shù)中的所有結(jié)點(diǎn)按編

號(hào)順序依次存儲(chǔ)在一維數(shù)組R[L..n]中，如圖6.8(a)所示。

(2)一般二叉樹(shù)

一般二叉樹(shù)也必須按完全二叉樹(shù)的形式來(lái)存儲(chǔ)一般二叉樹(shù)中的結(jié)點(diǎn),

只有通過(guò)添加一些并不存在的“虛結(jié)點(diǎn)”，使之成為完全二叉樹(shù)的形式

才行，如圖6.8(b)所示。

在最壞的情況下，一個(gè)深度為h且只有h個(gè)結(jié)點(diǎn)的右單支樹(shù)需要2L1

個(gè)的結(jié)點(diǎn)空間。所以，不宜采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一般的二叉樹(shù)。

A#B###C

(b)一般二叉樹(shù)及其順序存儲(chǔ)結(jié)構(gòu)

圖6.8二叉樹(shù)的編號(hào)及其順序存儲(chǔ)結(jié)構(gòu)

!第六章樹(shù)

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，?N^

1(1)二叉鏈表

采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)二叉樹(shù)，而且設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可以構(gòu)

成不同形式的二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素

和分別指向其左、右子樹(shù)的兩個(gè)分支構(gòu)成，所以，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)

結(jié)構(gòu)中的結(jié)點(diǎn)至少應(yīng)包含三個(gè)域：數(shù)據(jù)域和左、右指針域，即每個(gè)結(jié)

點(diǎn)應(yīng)包含兩個(gè)指針I(yè)child和rchild,分別指向該結(jié)點(diǎn)的左孩子和右孩子。

其結(jié)點(diǎn)結(jié)構(gòu)形式如圖6.9所示。

Ichilddatarchild

圖6.9二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)

第六章樹(shù)

結(jié)點(diǎn)類型定義：

typedefstructnode

{datatypedata；/*數(shù)據(jù)域*/

structnode*lchild,*rchild；/*左、右孩子域*/

}btnode,*bitree；

在一棵二叉樹(shù)中，所有類型為btnode的結(jié)點(diǎn)，加上一個(gè)指向

根結(jié)點(diǎn)的頭指針，就可構(gòu)成二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，有時(shí)將這種

存儲(chǔ)結(jié)構(gòu)稱為二叉鏈表，如圖6.10所示。一個(gè)二叉鏈表可以由頭

指針唯一地確定。

采用二叉鏈表作為二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)便于從根結(jié)點(diǎn)開(kāi)始

往下搜索孩子或子孫結(jié)點(diǎn)。

第六章樹(shù)

root

(a)二叉樹(shù)(b)二叉鏈表

圖6.10二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

第六章樹(shù)

(3)三叉鏈表

有時(shí)，為了便于檢索結(jié)點(diǎn)的雙親或祖先結(jié)點(diǎn)，可在結(jié)點(diǎn)中

增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域(如圖6.11(a)中的parent),這

種結(jié)構(gòu)稱為三叉鏈表，如圖6.11所示即為圖6.10(a)中二叉樹(shù)所對(duì)應(yīng)

的三叉鏈表。

(a)三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)(b)三叉鏈表

圖6.11二叉樹(shù)的三叉鏈表

第六章樹(shù)

二叉樹(shù)的簡(jiǎn)單運(yùn)算實(shí)現(xiàn)

這里所討論的運(yùn)算實(shí)現(xiàn)算法，以二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)。

(1)置空二叉樹(shù)setnun(bt)

voidsetnull(bitreebt)

{bt->lchild=NULL；/*左鏈域置空*/

bt->rchild=NULL；/*右鏈域置空刃

}

(2)求二叉樹(shù)的根root(bt)

datatyperoot(bitreebt)

{if(bt->lchild==NULL)

returnNULL；/*空樹(shù)時(shí)返回NULL*/

else

return(bt->lchild->data)；/*否則返回根結(jié)點(diǎn)數(shù)據(jù)域的值*/

)

[第六章樹(shù).

(3)建立二叉樹(shù)操作create(x,Ibt,rbt)

bitreecreate(datatypex,bitreeIbt,bitreerbt)

{bitreep；

p=(bitree)malloc(sizeof(btnode))；

/*申請(qǐng)一個(gè)結(jié)點(diǎn)空間，地址傳給p指針*/

p->data=x；

p->lchild=lbt；/*把二叉樹(shù)Ibt填入p的左孩子鏈域*/

p->rchild=rbt；/*把二叉樹(shù)rbt填入p的右孩子鏈域*/

returnp；/*返回建成的二叉樹(shù)*/

)

(4)插入左孩子addlchild(bt,x)

voidaddlchild(bitreebt,datatypex)

{bitreep；

p=(bitree)malloc(sizeof(btnode))；/*申請(qǐng)一個(gè)結(jié)點(diǎn)空間*/

p->data=x；

p->lchild=NULL；

p->rchild=NULL；/*左、右孩子域置空*/

第六章樹(shù)

(5)刪除左孩子dellchild(bt)

voiddellchild(bitreebt)

{bitreep；

p=bt->lchild；/*保存左子樹(shù)指針*/

bt->lchild=NULL；/*bt的左孩子域置空*/

free(p)；/*釋放左子樹(shù)空間*/

第六章樹(shù)

6.3遍歷二叉樹(shù)

在實(shí)際應(yīng)用中，常常要求在二叉樹(shù)中檢索或查找具有某種特征的

結(jié)點(diǎn)，或者對(duì)二叉樹(shù)中的所有結(jié)點(diǎn)逐一地進(jìn)行某種處理，這就提出了

一個(gè)遍歷二叉樹(shù)的問(wèn)題，即如何按某條搜索路徑巡訪二叉樹(shù)中的每個(gè)

結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅被訪問(wèn)一次?？梢哉f(shuō)，遍歷操作的

實(shí)質(zhì)就是使非線性結(jié)構(gòu)線性化。

若以L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)，

貝I」有DLR、LDR、LRD、DRL、RDL和RLD六種遍歷次序。顯然，前

三種遍歷次序和后三種是對(duì)稱的，若約定先左后右，則只有前三種情

況即DLR、LDR和LRD,分別稱為前序遍歷、中序遍歷和后序遍歷。

■第六章樹(shù)._______

6.3.1遍歷二叉樹(shù)的遞歸算法—

假設(shè)二叉樹(shù)采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)根結(jié)點(diǎn)的訪問(wèn)是輸出結(jié)點(diǎn)數(shù)

據(jù)，以上三種遍歷運(yùn)算的遞歸定義及算法如下：

L前序遍歷(PreorderTraversal)

若二叉樹(shù)為空，則遍歷結(jié)束，否則進(jìn)行如下操作：

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

(2)前序遍歷根結(jié)點(diǎn)的左子樹(shù)；

(3)前序遍歷根結(jié)點(diǎn)的右子樹(shù)。

前序遍又稱之為先根遍歷或先序遍歷。其遞歸算法描述如下：

voidpreorder(bitreebt)

{if(bt)

{printf(“％d\t”，bt->data)；/*訪問(wèn)根結(jié)點(diǎn)，這里假設(shè)數(shù)據(jù)域?yàn)檎?/

preorder(bt->lchild)；/*前序遍歷左子樹(shù)*/

preorder(bt->rchild)；/*前序遍歷右子樹(shù)刃

)

)

第六章樹(shù)

2.中序遍歷(InorderTraversal)

若二叉樹(shù)為空，則遍歷結(jié)束，否則進(jìn)行如下操作:

(1)中序遍歷左子樹(shù)；

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

(3)中序遍歷右子樹(shù)。

中序遍歷又稱為中根遍歷。算法描述如下：

voidinorder(bitreebt)

{if(bt)

{inorder(bt->lchild)；/*中序遍歷左子樹(shù)*/

printf(“％d\t”,bt->data)；/*訪問(wèn)根結(jié)點(diǎn)*/

inorder(btt->rchild)；/*市序遍歷右子樹(shù)*/

)

}

3,后序遍歷(PostorderTraversal)

若二叉樹(shù)為空，則遍歷結(jié)束，否則進(jìn)行如下操作:

(1)后序遍歷左子樹(shù)；

(2)后序遍歷右子樹(shù)；

(3)訪問(wèn)根結(jié)點(diǎn)。.，

第六章樹(shù)

,后序遍歷也稱為后根遍歷。其遞歸算法描述如下：’

voidpostorder(bitreebt)

{if(bt)

{postorder(bt->lchild)；/*后序遍歷左子樹(shù)*/

postorder(bt->rchild)；/*后序遍歷右子樹(shù)*/

printf("%d\t”,bt->data)；/*訪問(wèn)根結(jié)點(diǎn)*/

}

}

從遍歷遞歸算法的執(zhí)行蹤跡來(lái)看，這三種遍歷的搜索路線相同，如圖

6.12所示。只要分別將搜索路線上的所有在第一次、第二次和第三次經(jīng)

過(guò)的結(jié)點(diǎn)收集，即可分別得到該二叉樹(shù)的前序、中序和后序遍歷序列。

第六章樹(shù)

(a)遍歷二叉樹(shù)的搜索路線(b)遍歷二叉樹(shù)的的遞歸執(zhí)行過(guò)程

圖6.12遍歷過(guò)程示意圖

■第六章樹(shù).______

*叉樹(shù)的三種遍歷序列如下：.0

前序遍歷序列：ABDCE

中序遍歷序列：DBACE

后序遍歷序列：DBECA

又如，一棵表達(dá)式二叉樹(shù)如圖6.13所示，對(duì)該表達(dá)式樹(shù)進(jìn)行前序、中

序和后序遍歷，結(jié)果分別為：

前序遍歷序列：-+a*bc/de

中序遍歷序列：a+b*c-d/e

后序遍歷序列：abc*+de/?

上述三種遍歷序列都是線性序列，有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn),

其余結(jié)點(diǎn)有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。有時(shí)，為了區(qū)分樹(shù)形

結(jié)構(gòu)中的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的概念，對(duì)以上三種線性序列，均在某結(jié)

點(diǎn)的前趨和后繼之前加上其遍歷次序的名稱。

13表注式樹(shù)

第六章樹(shù)

632遍歷二叉樹(shù)的非遞歸算法

遞歸算法簡(jiǎn)潔精煉、可讀性好、易理解，但其執(zhí)行效率較低，但

有些程序設(shè)計(jì)語(yǔ)言不支持遞歸功能，所以，我們有必要討論遍歷二叉樹(shù)

的非遞歸算法。

可以利用后來(lái)保存遍歷過(guò)程中遍歷的結(jié)點(diǎn)的左孩子和右孩子，從而

實(shí)現(xiàn)遍歷二叉樹(shù)的非遞歸算法。假定在每個(gè)算法中，s為用一維數(shù)組表

示的順序棧，top為棧頂指針，P為臨時(shí)變量，S棧的作用是保存待訪問(wèn)

結(jié)點(diǎn)的指針，S棧的深度要大于整個(gè)樹(shù)的深度，即假設(shè)?？臻g足夠大，

不會(huì)出現(xiàn)棧滿清況。

I第六章樹(shù)—

卜序遍歷二叉樹(shù)的非遞歸算法

#defineM100.

voidpreorder(bitreebt)/*前序遍歷二叉樹(shù)的非遞歸算法*/

{bitreep,s[M]；

inttop=-l；

p=bt；

do

{while(p)

{printf("%d\t”,p->data);

if(p->rchild)

s[++top]=p->rchild；

)

if(top>=0)/*棧非空，退棧，使p指向右子樹(shù)繼續(xù)掃描右子樹(shù)*/

p=s[top-]；

}while((top==-1)&&(p==NULL))；

I第六章樹(shù)

2.中序遍歷二叉樹(shù)的非遞歸算法

voidinorder(bitreebt)/*中序遍歷二叉樹(shù)的非遞歸算法*/

{bitreep,s[M]；

inttop=-l；

p=bt；

do

{while(p)/*搜索最左下的結(jié)點(diǎn)，并將左孩子進(jìn)棧*/

{s[++top]=p；

p=p->lchild；

)

if(top>=0)

{p=s[top-]；/*出棧，棧頂元素賦p*/

printf(“％d\t”，p->data)；/*訪問(wèn)根結(jié)點(diǎn)*/

p=p->rchild;/*p指向右子樹(shù)，繼續(xù)搜索右子樹(shù)*/

)

}while((top==-1)&&(p==NULL))；

第六章樹(shù)—

]3,后序遍歷二叉樹(shù)的非遞歸算法?

voidpostorder(bitreebt)/*后序遍歷二叉樹(shù)的非遞歸算法*/

{ints2[M],top=-l,flag；

bitreep,sl[M]；

p=bt；

do

{while(p)/*遍歷其左子樹(shù)*/

{sl|++topl=p；

s2[top]=0；/*p結(jié)點(diǎn)首次進(jìn)棧*/

p=p->lchild；

)

if(top>=0)

{flag=s2[--top]；

p=sl[top]；

第六章樹(shù)

if(flag==0)

{sl[top]=p；'

Ts2[++top]=l；/*p結(jié)點(diǎn)第二次進(jìn)棧*/

p=p->rchild；

}/*遍歷p結(jié)點(diǎn)的右子樹(shù)*/

else

{printf(w%d\f\p->data)；/*訪問(wèn)根結(jié)點(diǎn)*/

p=NULL；

}

)

}while(top==-1)；

)

后序遍歷的非遞歸算法也可以描述如下：

voidpostorder(bitreebt)/*后序遍歷二叉樹(shù)的非遞歸算法*/

{inttop=-l；

bitree^[M]；_____________

第六章樹(shù)—

do

{while(p)

{top++；

s[top]=p；

if(p->lchild!=NULL)p=p->lchild；

elsep=p->rchild；

)

p=s[top]；

top—；

printf("％d\t"，p->data)；/*訪問(wèn)結(jié)點(diǎn)*/

while((top>=0)&&(s[top]->rchild==p))

{P=s[top];

top-

printf(66%d\tM,p->data)；

)

if(top>=0)p=s[top]->rchild；

}while(top==-l)；

■第六章樹(shù)

T6.3.3二叉樹(shù)的層次遍歷

所謂層次遍歷(LevelorderTraversal)是指從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始

從上到下逐層遍歷二叉樹(shù)，在同一層次中從左到右依次訪問(wèn)各個(gè)結(jié)點(diǎn)。

例如，對(duì)圖6.12(a)的二叉樹(shù)，按層次遍歷得到的結(jié)點(diǎn)序列為ABCDE。

可利用一個(gè)隊(duì)列結(jié)構(gòu)來(lái)實(shí)現(xiàn)層次遍歷，其做法是：

(1)首先將根結(jié)點(diǎn)入隊(duì)列；

(2)當(dāng)隊(duì)列不空，從隊(duì)列中取出隊(duì)頭結(jié)點(diǎn)訪問(wèn)它，并在其左右孩子非

空時(shí)，把它的左孩子和右孩子結(jié)點(diǎn)依次入隊(duì)列；(3)反復(fù)執(zhí)行(2),

直到隊(duì)列為空時(shí)止。

第六章樹(shù)

#defineMAXSIZE100

voidlevelorder(bitreebt)/*層次遍歷二叉樹(shù)bt*/

{bitreequeue[MAXSIZE]；/*定義隊(duì)列*/

intfront,rear；/*定義隊(duì)列指針*/

if(bt==NULL)/*如果是空樹(shù)，則返回*/

return；

front=0；rear=0；/*隊(duì)列指針初始化*/

queue[++rear]=bt；/*根結(jié)點(diǎn)入隊(duì)*/

while(front!=rear)/*當(dāng)隊(duì)列不空*/

{front=(front+l)%MAXSIZE；/*隊(duì)頭結(jié)點(diǎn)出隊(duì)*/

printf("%d\t"，queue[front]->data)；

if(queue[front]->lchild!=NULL)

{rear=(rear+l)%MAXSIZE；/*修改隊(duì)尾指針*/

queue[rear]=queue[front]->lchild；

}

if(queue[front]->rchild!=NULL)

{rear=(rear+l)%MAXSIZE；/*修改隊(duì)尾指針*/

queuefrear]=queue[front]->rchild；

第六章樹(shù)

6.3.4二叉樹(shù)的運(yùn)算舉例

遍歷是二叉樹(shù)各種運(yùn)算的基礎(chǔ)，利用各種遍歷運(yùn)算可以在遍

歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如求二叉樹(shù)中某結(jié)點(diǎn)的雙親、孩

子和結(jié)點(diǎn)的層次等，也可以在遍歷過(guò)程中生成結(jié)點(diǎn)，建立二叉樹(shù)

的存儲(chǔ)結(jié)構(gòu)以及輸出二叉樹(shù)等。

第六章樹(shù)

艮建立二叉樹(shù)

例如，若要建立圖6.14所示的二叉樹(shù)的二叉鏈表，則按下列順序

輸入字符：AB（|）D（|）（|）C（|）（|）（其中巾表示空格字符，說(shuō)明無(wú)子樹(shù)）。顯然,

該輸入序列與二叉樹(shù)的前序遍歷序列相對(duì)應(yīng)。算法描述如下：

bitreecreatebitree()

{bitreet；charch；

scanf(“％c”,&ch)；

if(ch==69)t=NULL；

else

{t=(bitree)malloc(sizeof(btnode))；/*生成根結(jié)點(diǎn)*/

t->data=ch；

t->lchild=createbitree()；/*建立左子樹(shù)*/

t->rchild=createbitree()；/*建立右子樹(shù)*/

)

return(t)；

)

第六章樹(shù)

r一

上20t

/IA|\

一/???

AB\AcA

?、一

八|D|八

(a)二叉樹(shù)(b)二叉鏈表

圖6.14二叉樹(shù)及其二叉鏈表

第六章樹(shù)

2.求二叉樹(shù)的葉子數(shù)目

可以在遍歷過(guò)程中對(duì)所遇結(jié)點(diǎn)判斷是否為葉子結(jié)點(diǎn)，若是則統(tǒng)計(jì)變

量加1,直到遍歷完所有結(jié)點(diǎn)，葉子結(jié)點(diǎn)總數(shù)即可求得。下面給出利用中

序遍歷求葉子結(jié)點(diǎn)數(shù)的遞歸算法：

intcountleaf(bitreebt)

{intnum=O;/*初始化統(tǒng)計(jì)變量*/

if(bt!=NULL)

if((bt->lchild==NULL)&&(bt->rchild==NULL))

num++;

else

num=countleaf(bt->lchild)+countleaf(bt->rchild);

returnnum;

)

■第六章樹(shù).______

翼叉樹(shù)中結(jié)點(diǎn)的檢索

以前序遍歷來(lái)實(shí)現(xiàn)檢索運(yùn)算的遞歸算法。

bitreesearch(bitreebt,datatypex)

{if(bt!=NULL)/*如果二叉樹(shù)bt非空刃

{if(bt->data==x)returnbt；/*如果根結(jié)點(diǎn)數(shù)據(jù)域值為x則返回bt*/

search(bt->lchild,x)；/*在左子樹(shù)中檢索*/

search(bt->rchild,x)；/*在右子樹(shù)中檢索*/

)

else

returnNULL；

)

第六章樹(shù)

4.求二叉樹(shù)的高度

利用后序遍歷求二叉樹(shù)高度的遞歸算法:

inttreedepth(bitreebt)

{inth,Ih,rh；

if(bt==NULL)h=0；

else

{lh=treedepth(bt->lchild)；

rh=treedepth(bt->rchild)；

if(lh>=rh)h=lh+l；

elseh=rh+l；

)

returnh；

第六章樹(shù)

6.4線索二叉樹(shù)

B?線索二叉樹(shù)的概念

1、問(wèn)題提出

遍歷二叉樹(shù)可以得到二叉樹(shù)中結(jié)點(diǎn)的某個(gè)遍歷次序序列，這實(shí)質(zhì)上是

對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的操作，使得除第一個(gè)和最后一個(gè)外的每個(gè)

結(jié)點(diǎn)在這些線性序列中有且僅有一個(gè)直接前趨和直接后繼。然而，當(dāng)二叉

樹(shù)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，由于每個(gè)結(jié)點(diǎn)中只有指向其左、右孩子的

指針，所以，從任一個(gè)結(jié)點(diǎn)出發(fā)可以直接找到該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)，

在一般情況下是不能直接得到該結(jié)點(diǎn)在某一遍歷序列中的前趨和后繼結(jié)點(diǎn)

的信息。那如何才能直接得到這些信息呢？

2、解決辦法

(1)通過(guò)采用多重鏈表來(lái)表示二叉樹(shù)的方法得到，即在每個(gè)結(jié)點(diǎn)中除

原來(lái)的左、右孩子的指針之外，增加兩個(gè)指針指示結(jié)點(diǎn)在某一個(gè)遍歷序列

中的前趨和后繼結(jié)點(diǎn)。

第六章樹(shù)

(2)通過(guò)遍歷的方法，每當(dāng)要求某結(jié)點(diǎn)在某一個(gè)遍歷序列中的前趨和

后繼結(jié)點(diǎn)的信息，就進(jìn)行一次遍歷。

(3)利用在有n個(gè)結(jié)點(diǎn)的二叉鏈表中的n+1個(gè)是空鏈域來(lái)存放結(jié)點(diǎn)在

某一個(gè)遍歷序列中的前趨和后繼結(jié)點(diǎn)的指針。

3、線索二叉樹(shù)

有時(shí)也裝種附加的指向其前趨和后繼的指針?lè)Q為線索(Thread),而

將加上了線索的二叉鏈表稱為線索鏈表(ThreadLinkedList),相應(yīng)的

加上線索的二叉樹(shù)稱為線索二叉樹(shù)，對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€

索二叉樹(shù)的過(guò)程稱為線索化。

第六章樹(shù)

線索二叉鏈表的類型:

typedefenum{0,1}ptrtag；

typedefstructbithnode

{datatypedata；

structbithnode*lchild,*rchild；

ptrtagItag,rtag；/*標(biāo)志域*/

}bithnode,*bithptr；

其中：ltag=0表示Ichild域?yàn)橹赶蚪Y(jié)點(diǎn)的左孩子的指針；ltag=l表示

Ichild域?yàn)橹赶蚪Y(jié)點(diǎn)其前趨的左線索；rtag=0表示rchild域?yàn)橹赶蚪Y(jié)點(diǎn)的右

孩子的指針；rtag=l表示rchild域?yàn)橹赶蚪Y(jié)點(diǎn)其后繼的右線索。例如圖

6.15(a)、(b)所示。

第六章樹(shù)

(a)中序線索二叉樹(shù)(b)中序線索鏈表

圖6.15中序線索二叉樹(shù)及其線索鏈表

第六章樹(shù)

642線索二叉鏈表的建立

可以在對(duì)二叉樹(shù)的某種次序遍歷過(guò)程中，一邊遍歷一邊建立線索,

若當(dāng)前訪問(wèn)結(jié)點(diǎn)的左孩子域?yàn)榭談t建立前趨線索，若右孩子域?yàn)榭談t

建立后繼線索。下面給出中序線索二叉鏈表的建立算法。

要建立中序線索二叉鏈表，可以對(duì)二叉樹(shù)采用一邊中序遍歷一邊

建立線索的方法，若在遍歷過(guò)程中被訪問(wèn)結(jié)點(diǎn)的左孩子為空，則建立

前趨線索；若右孩子為空，則建立后繼線索。算法描述如下：

第六章樹(shù)

bithptrpre/*pre為全程量，初值為NULL*/

bithptrcreatinordthrd(bithptrroot)/*t指向二叉樹(shù)的根*/

{voidinthrd()；

bithptrthrt；

thrt=(bithrtree)malloc(sizeof(bithrnode))；

thrt->ltag=O；

thrt->rtag=l；

thrt->rchild=thrt；

if(root==NULL)

thrt->lchild=thrt；

else

{thrt->lchild=root；

pre=thrt；

inthrd(root)；/*進(jìn)行中序線索化*/

pre->rchild=thrt；

pre->rtag=l；

thre->rchild=pre;

)

returnthrt；—一

1—

第六章樹(shù)

voidinthrd(bithptrroot)/*將二叉樹(shù)root中序線索化*/

{if(root!=NULL)

{inthrd(root->lchild)；/*左子樹(shù)線索化*/

if(root->lchild==NULL)root->ltag=l；/*建立左線索標(biāo)志*/

if(root->rchild==NULL)root->rtag=l；/*建立右線索標(biāo)志*/

if(pre!=NULL)/*pre為全程量，為root的前趨指針*/

{if(pre->rtag==1)

pre->rchild=root；/*pre無(wú)右子樹(shù)*/

if(root->ltag==1)

root->lchild=pre；

}

pre=root；

inthrd(root->rchild)；/*右子樹(shù)線索化*/

第六章樹(shù)

■6.4.3遍歷線索二叉樹(shù)蕓—

?在線索二叉樹(shù)上進(jìn)行遍歷，只要從頭結(jié)點(diǎn)出發(fā)反復(fù)查找結(jié)點(diǎn)前繼,

直到又回到頭結(jié)點(diǎn)時(shí)止。下面給出中序遍歷中序線索二叉樹(shù)的算法。

voidinordtraverse(bithptrroot)/*root為頭結(jié)點(diǎn)指針*/

{bithptrp；

p=root->lchild；/*p指向根結(jié)點(diǎn)*/

while(p!=root)/*空樹(shù)或遍歷結(jié)束時(shí)，p=root*/

{while(p->ltag==0)/*查找最左下的結(jié)點(diǎn)*/

p=p->lchild；

printf(66%c\tM,p->data)；

while((p->rtag==1)&&(p->rchild!=root))

{p=p->rchild；/*若右指針為線索，貝傳遞指針*/

printf("％c\t"，p->data)；/*訪問(wèn)結(jié)點(diǎn)*/

)

p=p->rchild；

)

<Back

第六章樹(shù)

iI6.5樹(shù)和森林

6.5.1樹(shù)的存儲(chǔ)結(jié)構(gòu)

1.雙親表示法

可以在存儲(chǔ)樹(shù)中結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)增加一個(gè)指向其雙親

的指針parent。假設(shè)以一組地址連續(xù)的空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，則其類型說(shuō)

明如下：

#defineMAXSIZE100

typedefstructnode

{datatypedata;

intparent;

Jptnode；

ptnodeT[MAXSIZE]；

第六章樹(shù)

.

0123456789???maxsize-1

dataABCDEFGHI???

parent-1011122244???

(a)樹(shù)(b)雙親表示

圖6.16樹(shù)的雙親表示

第六章樹(shù)

2.孩子表示法

為樹(shù)中每個(gè)結(jié)點(diǎn)的孩子建立一個(gè)單鏈表，一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)就有

n個(gè)孩子鏈表,并在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針域，指向其孩子鏈表的表頭，

這種孩子表示法也稱為孩子鏈表表示法，其形式說(shuō)明如下：

typedefstructnode

{datatypedata；

structnode*next；/*定義孩子鏈表頭指針*/

}ctree;

ctreeT[MAXSIZE]；

孩子表示法便于實(shí)現(xiàn)對(duì)結(jié)點(diǎn)的孩子的運(yùn)算，但不適合于對(duì)結(jié)點(diǎn)的雙

親進(jìn)行運(yùn)算。若要既便于實(shí)現(xiàn)涉及孩子又便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算，

可以考慮將雙親表示法與孩子鏈表表示法結(jié)合起來(lái)，形成雙親孩子鏈表

表不法。

第六章樹(shù)

1D人

2G人

3

4

5

6

7

8

9

圖6.17樹(shù)的孩子鏈表表示

第六章樹(shù)

1

2

3

4

5

6

7

8

9

圖6.18樹(shù)的雙親孩子鏈表表示

第六章樹(shù)

?孩子兄弟表示法

該方法又稱二叉鏈表表示法，即以二叉鏈表做為樹(shù)的存儲(chǔ)結(jié)構(gòu)，

鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別指向結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)右

兄弟結(jié)點(diǎn)，所以，有時(shí)也稱為左孩子右兄弟表示法。其結(jié)構(gòu)的類型說(shuō)

明如下：

typedefstructnode

{datatypedata；

structnode*firstchild,*nextsib；

}cstnodc?*cstree；

利用這種存儲(chǔ)結(jié)構(gòu)廟于實(shí)現(xiàn)樹(shù)的各種運(yùn)算如查找結(jié)點(diǎn)的孩子等，

可借助二叉鏈表導(dǎo)出樹(shù)與二叉樹(shù)之間的確定對(duì)應(yīng)關(guān)系，并利用二叉樹(shù)

的有關(guān)算法來(lái)實(shí)現(xiàn)對(duì)樹(shù)的各種運(yùn)算。

第六章樹(shù)

圖6.19樹(shù)的孩子兄弟表示法

第六章樹(shù)

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

可借助二叉鏈表導(dǎo)出樹(shù)與二叉樹(shù)之間的確定對(duì)應(yīng)關(guān)系。任何一個(gè)

森林或一棵樹(shù)可以唯一地對(duì)應(yīng)于一棵二叉樹(shù)，而任何一棵二叉樹(shù)也能

唯一■地對(duì)應(yīng)到一■個(gè)森林或一1棵樹(shù)上。

第六章樹(shù)

■L樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)、》一,

「從樹(shù)的孩子兄弟表示法中可以導(dǎo)出樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系，的樹(shù)中

每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子和一個(gè)右鄰的兄弟，按照這種關(guān)系,

就可以將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)。

圖6.20樹(shù)轉(zhuǎn)換為二叉樹(shù)

森林轉(zhuǎn)換為二叉樹(shù)：先將森林中的每一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)，再將第一

棵樹(shù)的樹(shù)根作為轉(zhuǎn)換后二叉樹(shù)的根，第一棵樹(shù)的左子樹(shù)作為轉(zhuǎn)換后二叉

樹(shù)的左子樹(shù)，第二棵樹(shù)作為轉(zhuǎn)換后的二叉樹(shù)的右子樹(shù)，第三棵樹(shù)作為轉(zhuǎn)

如此進(jìn)行，直紗轉(zhuǎn)臉宅:上匕

第六章樹(shù)

AEA

森林與二叉樹(shù)轉(zhuǎn)換

CDFHE

C

樹(shù)與二叉樹(shù)轉(zhuǎn)換

DH

E

I

H

K

C

K

圖6.21樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換示意圖

第六章樹(shù)

?二叉樹(shù)轉(zhuǎn)換成森林

若二叉樹(shù)非空，則將二叉樹(shù)的根及其左子樹(shù)作為轉(zhuǎn)換后的第一棵樹(shù)的

二叉樹(shù)形式，剩下的二叉樹(shù)的右子樹(shù)又可以看作是由一個(gè)森林轉(zhuǎn)換后的二

叉樹(shù)，可以利用同樣的方法進(jìn)行轉(zhuǎn)換，如此類推，直到最后產(chǎn)生一棵沒(méi)有

右子樹(shù)的二叉樹(shù)為止，這樣就得到了森林。

若想進(jìn)一步得到樹(shù)，可以利用樹(shù)的孩子兄弟表示法的逆方法，即根據(jù)

結(jié)點(diǎn)本身、結(jié)點(diǎn)的右孩子、右孩子的右孩子、…，原本都是同一個(gè)雙親的

兄弟這個(gè)性質(zhì)將二叉樹(shù)轉(zhuǎn)換為樹(shù)。

顯然，上述定義是遞歸定義，容易寫(xiě)出相互轉(zhuǎn)換的遞歸算法。同時(shí)，

利用樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換，對(duì)樹(shù)和森林的運(yùn)算也可轉(zhuǎn)換成二叉樹(shù)

的運(yùn)算來(lái)實(shí)現(xiàn)。

第六章樹(shù)

?3樹(shù)和森林的遍歷

對(duì)于樹(shù)和森林，根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序可分為前序遍歷和后序遍歷

兩種方法。

L樹(shù)的遍歷

(1)樹(shù)的前序遍歷

樹(shù)的前序遍歷也稱作先根遍歷或先序遍歷，其遞歸定義為：

若樹(shù)非空，則先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次前序遍歷根的各棵子樹(shù)。

(2)樹(shù)的后序遍歷

樹(shù)的后序遍歷也稱作后根遍歷，其遞歸定義為：

若樹(shù)非空，則先依次后序遍歷根的各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。

例如，對(duì)圖6.16(a)中所示的樹(shù)進(jìn)行先序遍歷，可得前序遍歷序列

為：ABEFGCDHI

若對(duì)其進(jìn)行后序遍歷，則可得后序遍歷序列為：EFGBCHIDA

第六章樹(shù)_________________________________

I

2.森林的遍歷.—

i按照森林和樹(shù)的相互遞歸的定義，可以得到森林的兩種遍歷方法。

(1)森林的前序遍歷

森林的前序遍歷即依次按前序次序遍歷森林中的每一棵樹(shù)，其形式化

的遞歸定義為：若森林非空，則先訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)，然后前

序遍歷第一棵子樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林，再前序遍歷除第一棵樹(shù)之外剩余

的樹(shù)構(gòu)成的森林。

(2)森林的后序遍歷

后序遍歷即依次按后序次序遍歷森林中的每一棵樹(shù)，其形式化遞歸定

義為：若森林非空，則先后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林，

然后訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)，再后序遍歷除第一棵樹(shù)之外剩余的樹(shù)構(gòu)成的

森林O

何如，對(duì)圖6.21中的森林進(jìn)行前序和后序遍歷，其結(jié)果為：

前序遍歷序列：ABCDEFGHIK

后序遍歷序列：BCDAFEHKIG

第六章樹(shù)

.6.6哈夫曼樹(shù)

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

的二叉樹(shù)，有著廣泛的應(yīng)用。本節(jié)先討論哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）的概

念，然后討論它的應(yīng)用及其算法實(shí)現(xiàn)。

6.6.1基本術(shù)語(yǔ)

1.路徑和路徑長(zhǎng)度

樹(shù)中兩個(gè)結(jié)點(diǎn)之間的路徑，是指從樹(shù)中一個(gè)結(jié)點(diǎn)到達(dá)另一個(gè)結(jié)點(diǎn)之

間的分支。

將路徑中所經(jīng)過(guò)的分支數(shù)稱為這兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度，它等于路

徑上的結(jié)點(diǎn)數(shù)減1,即等于路徑上分支的數(shù)目j-1。

將從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和定義為樹(shù)的路徑長(zhǎng)度。

第六章樹(shù)

2.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度

.在許多實(shí)際應(yīng)用中，常為樹(shù)中的結(jié)點(diǎn)賦于一個(gè)有某種意義祥照，

稱之為該結(jié)點(diǎn)的權(quán)。

將結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度規(guī)定為從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度

與該結(jié)點(diǎn)權(quán)值的乘積。

3.樹(shù)的帶權(quán)路徑長(zhǎng)度

樹(shù)的帶權(quán)路徑長(zhǎng)度(WeightedPathLength)為樹(shù)中所有葉子結(jié)點(diǎn)

的帶權(quán)路徑長(zhǎng)度之和，通常記為：

n

W尸L=>wz.Zz-

￡=1

其中，n表示帶權(quán)葉子結(jié)點(diǎn)的數(shù)目，Wj表示葉子用的權(quán)值，L表示

由樹(shù)的根到葉子結(jié)點(diǎn)ki之間的路徑長(zhǎng)度。

例如，圖6.22計(jì)算每一棵二叉樹(shù)的帶權(quán)路徑長(zhǎng)度WPL分別為：

第六章樹(shù)

圖6.22具有不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)

(a)WPL=7X3+1X3+2X2+5X1=33

(b)WPL=1X3+2X3+5X2+7X1=26

(c)WPL=1X2+7X3+2X4+5X4=51

第六章樹(shù)

4,哈夫曼樹(shù)

哈夫曼樹(shù)(HuffmanTree)是指由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有

二叉樹(shù)中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)，又稱最優(yōu)二叉樹(shù)。相應(yīng)的,

其構(gòu)造算法稱為哈夫曼算法。

對(duì)于具有n個(gè)其權(quán)值分別為Wjw2,Wn的帶權(quán)葉子結(jié)點(diǎn)的二

叉樹(shù)來(lái)說(shuō)，其形態(tài)可以有許多種，其中能被稱為哈夫曼樹(shù)的二叉樹(shù)是

不唯一的，但其最小的WPL是確定的，而且在葉子數(shù)目及權(quán)值相同的

二叉樹(shù)中，完全二叉樹(shù)不一定是最優(yōu)二叉樹(shù)。一般情況下，在哈夫曼

樹(shù)中，權(quán)值越大的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越近。

第六章樹(shù)

6.6.2哈夫曼算法

(1)根據(jù)給定的n個(gè)權(quán)值{wLw2,…，wn)構(gòu)成n棵二叉樹(shù)的森林

F={T1,T2,…，Tn},其中每棵二叉樹(shù)Ti(IWiWn)都只有一個(gè)權(quán)值為wi的

根結(jié)點(diǎn)，其左、右子樹(shù)均為空；

(2)在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù)作為一棵新的二

叉樹(shù)的左、右子樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根

結(jié)點(diǎn)的僅值之和；

八(3)從森林F中刪除這兩棵二叉樹(shù)，同時(shí)將新得到的二叉樹(shù)加入到F中;

(4)重復(fù)(2)和(3)步驟，直到F中只含一棵二叉樹(shù)為止，此二叉

樹(shù)便是所構(gòu)造的哈夫曼樹(shù)。

例如，上例中由4個(gè)帶權(quán)為7,1,2,5的葉子結(jié)點(diǎn)A,B,C,D,根據(jù)

哈夫曼算法構(gòu)造其對(duì)應(yīng)哈夫曼樹(shù)的過(guò)程如圖6.23所示。

第六章樹(shù)

15

71257

(a)(b)(c)(d)

圖6.23哈夫曼樹(shù)的構(gòu)造過(guò)程

第六章樹(shù)

6.6.3哈夫曼編碼

哈夫曼算法的應(yīng)用很廣泛，本節(jié)以遠(yuǎn)距離電報(bào)通訊中的編碼為例來(lái)

說(shuō)明它的應(yīng)用。

(1)編碼和譯碼

在電報(bào)通訊中，需要將欲傳送電文中的字符轉(zhuǎn)換成由二進(jìn)制的0、1

序列，然后進(jìn)行傳送，并在接收端將收到的二進(jìn)制串轉(zhuǎn)化為對(duì)應(yīng)的字符

序列。一般的，編碼的方法有等長(zhǎng)編碼和不等長(zhǎng)編碼等。等長(zhǎng)編碼即為

每個(gè)字符編制的二進(jìn)制碼的碼長(zhǎng)相同。

(2)等長(zhǎng)編碼

例如，電文為“ABACCDA”，由于其中出現(xiàn)的字符只有四種，所以

只需兩個(gè)字符的二進(jìn)制串便可分辨。若將其等長(zhǎng)編碼設(shè)計(jì)為：A：00,B：

01,C：10,D：11,則上述七個(gè)字符的電文便為“00010010101100”，

總長(zhǎng)度14位，接收端接收并進(jìn)行譯碼時(shí)，可按二位一分割譯碼即可得相

應(yīng)的電文。顯然，利用等長(zhǎng)編碼方法進(jìn)行編碼，譯碼方便，但編碼所得

到的碼串過(guò)于冗長(zhǎng)。

第六章樹(shù)

(3)不等長(zhǎng)編碼

如上例中，A、C字符出現(xiàn)的次數(shù)較多，這樣可以設(shè)計(jì)字符A、B、C、

D的編碼分別為0、00、1和01,則上述共7個(gè)字符的電文可編碼為總長(zhǎng)度

為9的二進(jìn)制字符串“000011010”。顯然，其編碼總長(zhǎng)度大幅度減少，但

在譯碼時(shí)會(huì)帶來(lái)麻煩。例如，在接收端接收到的二進(jìn)制串中前四個(gè)字符

的子串“0000”就可有多種譯法，可以是“AAAA”，或是“ABA”，也可

以是“BB”等，顯然是不合適的，原因在于以上編碼不是前綴編碼因而

在譯碼時(shí)會(huì)產(chǎn)生多義性。

(4)前綴編碼

若利用不等長(zhǎng)編碼，要求字符集中任一個(gè)字符的編碼都不能是其它

字符編碼的前綴，這種編碼稱做前綴編碼(PrefixCode)?？梢岳枚鏄?shù)

來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼。用葉子結(jié)點(diǎn)表示要編碼的字符，并約定左分

支為‘0"右分支為'「，然后就可以用從根到葉子結(jié)點(diǎn)的路徑上分支字

符組成的串作為該字符的編碼，這樣得到的編碼必為二進(jìn)制前綴編碼。

第六章樹(shù)

01

0

0

?

圖6.24前綴編碼示例

第六章樹(shù)

(5)哈夫曼編碼.、一

S假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為巧，其編碼長(zhǎng)度為L(zhǎng)，電文中有n

種字符，則電文總長(zhǎng)度應(yīng)為WJ+W2I2+…+wj=0對(duì)應(yīng)到二叉樹(shù)上,

n可以看作是二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)，Wj可以著作是葉子結(jié)點(diǎn)的權(quán)值，I

恰為從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)Kj的路徑長(zhǎng)度，顯然，設(shè)計(jì)電文總長(zhǎng)度最短的二

進(jìn)制前綴編碼即是構(gòu)造以字符出現(xiàn)頻率作為權(quán)值的具有n個(gè)葉子結(jié)點(diǎn)的哈

夫曼樹(shù)，由此所得到的二進(jìn)制前綴編碼稱為哈夫曼編碼(Huffman

Code)o

例，假設(shè)電文中出現(xiàn)5個(gè)字符A、B、C、D、E,已知它們?cè)陔娢闹?/p>

出現(xiàn)的頻率是9、3、7、6、1,利用｛9,3,7,6,1｝為權(quán)值構(gòu)造的哈夫曼

樹(shù)如圖6.25所示，其編碼分別為：A：00,B：100,C：01,D：11,E：

101o

哈夫曼樹(shù)也可以用來(lái)譯碼，譯碼時(shí)從根結(jié)點(diǎn)出發(fā)，按二進(jìn)制位串中的

0和1確定是進(jìn)入左分支還是進(jìn)入到右分支，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)便可譯出該

葉子對(duì)應(yīng)的字符，若電文未完，則回到根結(jié)點(diǎn)繼續(xù)進(jìn)行譯碼。

第六章樹(shù)

26

9376196

@@?@?

(a)

圖6.25哈夫曼樹(shù)及哈夫曼編碼

第六章樹(shù)

6.6.4哈夫曼算法的實(shí)現(xiàn)■

1.哈夫曼樹(shù)的構(gòu)造算法

用一個(gè)大小為2n?l的一維數(shù)組構(gòu)成靜態(tài)鏈表來(lái)存放哈夫曼樹(shù)中的結(jié)點(diǎn)。

如圖6.26所示的靜態(tài)鏈表。其中data為數(shù)據(jù)域,Ichild為左孩子指針域,

rchild為右孩子指針域,parent為雙親指針域,’0,表示空指針。

dataIchiIdrchilddataIchildparentrchild

A231A203

B452B415

C673C617

D004D020

E005E020

F006F030

G007G030

(a)二叉樹(shù)(b)二叉靜態(tài)鏈表(c)三叉靜態(tài)鏈表

第六章樹(shù)

結(jié)點(diǎn)結(jié)構(gòu)描述:

typedefstruct

{floatweight；/*數(shù)據(jù)域用于存放權(quán)值*/

intIchild,pa