第6章樹

?2二叉樹

6.3遍歷二叉樹

第六章樹

第6章樹

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

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

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

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

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

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

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

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

編碼。

第六章樹

ti6.1樹的基本概念

6.1.1樹的定義及表示

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

張紅軍

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

第六章樹

校長辦公室

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

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

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

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

第六章樹—

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

■2、樹的定義

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

否則，稱為非空樹。在任一棵非空樹中：

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

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

合TLT2,…，Tm,其中每一個集合本身又都是一棵樹，一般稱為

根的子樹。

樹的定義是一個遞歸的定義，它反映了樹的固有特性，即一棵樹

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

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

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

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

樹，且其本身也是一棵樹。

第六章樹

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

6.2樹示例

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

6.3給出了樹的其它表示形式，如(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樹的其它表示法

第六章樹

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

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

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

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

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

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

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

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

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

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

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

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

第六章樹________________________________

I

t結(jié)點(diǎ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層。

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

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

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

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

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

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

且不能交換，則稱該樹為有序樹，否則稱為無序樹。圖6.4給出了兩棵

不同的有序樹。

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

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

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

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

第六章樹

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

(1)setnull(T)：置T為空樹，即初始化一棵樹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ù)。

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

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

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

第六章樹

6.2二叉樹

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

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

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

第六章樹

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

1、二叉樹定義

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

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

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

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

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

的是，二叉樹與樹是兩個不同的概念，它不是樹的特殊情形，例如，

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

樹相似，但卻不等同于這棵一般樹。

第六章樹

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

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

第六章樹

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

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

空

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

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

第六章樹

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

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

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

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

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

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

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

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

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

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

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

上，換句話說，完全二叉樹上的結(jié)點(diǎn)編號與同深度的滿二叉樹對應(yīng)位置的

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

而完全二叉樹不一定是滿二叉樹。

第六章樹

(c)非完全二叉樹

第六章樹

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

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

(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)二叉樹建立運(yùn)算create(x,Ibt,rbt)

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

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

第六章樹

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

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

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

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

則n0=n2+lo

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

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

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

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

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

編號是㈤2」。

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

的編號是2i。

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

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

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

第六章樹

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

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

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

據(jù)元素。

(1)完全二叉樹

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

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

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

(2)一般二叉樹

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

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

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

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

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

A#B###C

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

圖6.8二叉樹的編號及其順序存儲結(jié)構(gòu)

!第六章樹

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

1(1)二叉鏈表

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

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

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

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

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

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

Ichilddatarchild

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

第六章樹

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

typedefstructnode

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

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

}btnode,*bitree；

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

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

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

指針唯一地確定。

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

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

第六章樹

root

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

圖6.10二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)

第六章樹

(3)三叉鏈表

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

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

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

的三叉鏈表。

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

圖6.11二叉樹的三叉鏈表

第六章樹

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

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

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

voidsetnull(bitreebt)

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

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

}

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

datatyperoot(bitreebt)

{if(bt->lchild==NULL)

returnNULL；/*空樹時返回NULL*/

else

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

)

[第六章樹.

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

bitreecreate(datatypex,bitreeIbt,bitreerbt)

{bitreep；

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

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

p->data=x；

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

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

returnp；/*返回建成的二叉樹*/

)

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

voidaddlchild(bitreebt,datatypex)

{bitreep；

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

p->data=x；

p->lchild=NULL；

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

第六章樹

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

voiddellchild(bitreebt)

{bitreep；

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

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

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

第六章樹

6.3遍歷二叉樹

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

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

一個遍歷二叉樹的問題，即如何按某條搜索路徑巡訪二叉樹中的每個

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

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

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

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

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

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

■第六章樹._______

6.3.1遍歷二叉樹的遞歸算法—

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

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

L前序遍歷(PreorderTraversal)

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

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

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

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

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

voidpreorder(bitreebt)

{if(bt)

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

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

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

)

)

第六章樹

2.中序遍歷(InorderTraversal)

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

(1)中序遍歷左子樹；

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

(3)中序遍歷右子樹。

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

voidinorder(bitreebt)

{if(bt)

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

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

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

)

}

3,后序遍歷(PostorderTraversal)

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

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

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

第六章樹

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

voidpostorder(bitreebt)

{if(bt)

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

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

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

}

}

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

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

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

第六章樹

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

圖6.12遍歷過程示意圖

■第六章樹.______

*叉樹的三種遍歷序列如下：.0

前序遍歷序列：ABDCE

中序遍歷序列：DBACE

后序遍歷序列：DBECA

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

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

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

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

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

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

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

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

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

13表注式樹

第六章樹

632遍歷二叉樹的非遞歸算法

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

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

的非遞歸算法。

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

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

示的順序棧，top為棧頂指針，P為臨時變量，S棧的作用是保存待訪問

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

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

I第六章樹—

卜序遍歷二叉樹的非遞歸算法

#defineM100.

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

{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指向右子樹繼續(xù)掃描右子樹*/

p=s[top-]；

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

I第六章樹

2.中序遍歷二叉樹的非遞歸算法

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

{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)；/*訪問根結(jié)點(diǎn)*/

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

)

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

第六章樹—

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

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

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

bitreep,sl[M]；

p=bt；

do

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

{sl|++topl=p；

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

p=p->lchild；

)

if(top>=0)

{flag=s2[--top]；

p=sl[top]；

第六章樹

if(flag==0)

{sl[top]=p；'

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

p=p->rchild；

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

else

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

p=NULL；

}

)

}while(top==-1)；

)

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

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

{inttop=-l；

bitree^[M]；_____________

第六章樹—

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)；/*訪問結(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)；

■第六章樹

T6.3.3二叉樹的層次遍歷

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

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

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

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

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

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

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

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

第六章樹

#defineMAXSIZE100

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

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

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

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

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；

第六章樹

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

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

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

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

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

第六章樹

艮建立二叉樹

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

輸入字符：AB（|）D（|）（|）C（|）（|）（其中巾表示空格字符，說明無子樹）。顯然,

該輸入序列與二叉樹的前序遍歷序列相對應(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()；/*建立左子樹*/

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

)

return(t)；

)

第六章樹

r一

上20t

/IA|\

一/???

AB\AcA

?、一

八|D|八

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

圖6.14二叉樹及其二叉鏈表

第六章樹

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

可以在遍歷過程中對所遇結(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;

)

■第六章樹.______

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

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

bitreesearch(bitreebt,datatypex)

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

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

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

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

)

else

returnNULL；

)

第六章樹

4.求二叉樹的高度

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

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；

第六章樹

6.4線索二叉樹

B?線索二叉樹的概念

1、問題提出

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

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

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

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

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

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

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

2、解決辦法

(1)通過采用多重鏈表來表示二叉樹的方法得到，即在每個結(jié)點(diǎn)中除

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

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

第六章樹

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

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

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

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

3、線索二叉樹

有時也裝種附加的指向其前趨和后繼的指針稱為線索(Thread),而

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

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

索二叉樹的過程稱為線索化。

第六章樹

線索二叉鏈表的類型:

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)所示。

第六章樹

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

圖6.15中序線索二叉樹及其線索鏈表

第六章樹

642線索二叉鏈表的建立

可以在對二叉樹的某種次序遍歷過程中，一邊遍歷一邊建立線索,

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

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

要建立中序線索二叉鏈表，可以對二叉樹采用一邊中序遍歷一邊

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

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

第六章樹

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

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

{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—

第六章樹

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

{if(root!=NULL)

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

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無右子樹*/

if(root->ltag==1)

root->lchild=pre；

}

pre=root；

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

第六章樹

■6.4.3遍歷線索二叉樹蕓—

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

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

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

{bithptrp；

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

while(p!=root)/*空樹或遍歷結(jié)束時，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)；/*訪問結(jié)點(diǎn)*/

)

p=p->rchild；

)

<Back

第六章樹

iI6.5樹和森林

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

1.雙親表示法

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

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

明如下：

#defineMAXSIZE100

typedefstructnode

{datatypedata;

intparent;

Jptnode；

ptnodeT[MAXSIZE]；

第六章樹

.

0123456789???maxsize-1

dataABCDEFGHI???

parent-1011122244???

(a)樹(b)雙親表示

圖6.16樹的雙親表示

第六章樹

2.孩子表示法

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

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

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

typedefstructnode

{datatypedata；

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

}ctree;

ctreeT[MAXSIZE]；

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

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

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

表不法。

第六章樹

1D人

2G人

3

4

5

6

7

8

9

圖6.17樹的孩子鏈表表示

第六章樹

1

2

3

4

5

6

7

8

9

圖6.18樹的雙親孩子鏈表表示

第六章樹

?孩子兄弟表示法

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

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

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

明如下：

typedefstructnode

{datatypedata；

structnode*firstchild,*nextsib；

}cstnodc?*cstree；

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

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

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

第六章樹

圖6.19樹的孩子兄弟表示法

第六章樹

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

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

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

唯一■地對應(yīng)到一■個森林或一1棵樹上。

第六章樹

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

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

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

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

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

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

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

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

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

第六章樹

AEA

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

CDFHE

C

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

DH

E

I

H

K

C

K

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

第六章樹

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

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

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

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

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

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

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

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

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

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

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

第六章樹

?3樹和森林的遍歷

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

兩種方法。

L樹的遍歷

(1)樹的前序遍歷

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

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

(2)樹的后序遍歷

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

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

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

為：ABEFGCDHI

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

第六章樹_________________________________

I

2.森林的遍歷.—

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

(1)森林的前序遍歷

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

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

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

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

(2)森林的后序遍歷

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

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

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

森林O

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

前序遍歷序列：ABCDEFGHIK

后序遍歷序列：BCDAFEHKIG

第六章樹

.6.6哈夫曼樹

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

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

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

6.6.1基本術(shù)語

1.路徑和路徑長度

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

間的分支。

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

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

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

第六章樹

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

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

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

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

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

3.樹的帶權(quán)路徑長度

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

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

n

W尸L=>wz.Zz-

￡=1

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

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

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

第六章樹

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

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

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

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

第六章樹

4,哈夫曼樹

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

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

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

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

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

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

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

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

第六章樹

6.6.2哈夫曼算法

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

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

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

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

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

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

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

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

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

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

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

第六章樹

15

71257

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

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

第六章樹

6.6.3哈夫曼編碼

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

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

(1)編碼和譯碼

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

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

序列。一般的，編碼的方法有等長編碼和不等長編碼等。等長編碼即為

每個字符編制的二進(jìn)制碼的碼長相同。

(2)等長編碼

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

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

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

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

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

到的碼串過于冗長。

第六章樹

(3)不等長編碼

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

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

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

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

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

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

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

(4)前綴編碼

若利用不等長編碼，要求字符集中任一個字符的編碼都不能是其它

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

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

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

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

第六章樹

01

0

0

?

圖6.24前綴編碼示例

第六章樹

(5)哈夫曼編碼.、一

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

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

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

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

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

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

Code)o

例，假設(shè)電文中出現(xiàn)5個字符A、B、C、D、E,已知它們在電文中

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

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

101o

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

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

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

第六章樹

26

9376196

@@?@?

(a)

圖6.25哈夫曼樹及哈夫曼編碼

第六章樹

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

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

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

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

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

dataIchiIdrchilddataIchildparentrchild

A231A203

B452B415

C673C617

D004D020

E005E020

F006F030

G007G030

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

第六章樹

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

typedefstruct

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

intIchild,pa