數(shù)據(jù)結(jié)構(gòu)課程輔導(dǎo)與練習(xí)

數(shù)據(jù)結(jié)構(gòu)(本)課程輔導(dǎo)與練習(xí)-第6章

第6章樹和二叉樹

樹是一種重要的非線性結(jié)構(gòu)，從規(guī)律角度看,其數(shù)據(jù)元素之間體現(xiàn)的是一對多的非線性關(guān)系,

一切具有層次關(guān)系的問題都可以用樹來描述。

一、相關(guān)術(shù)語

樹、二叉樹、樹根、子樹、有序樹、無序數(shù)、森林、終端結(jié)點(葉子)、非終端結(jié)點、結(jié)點

的度、結(jié)點的層次、樹的深度、滿二叉樹、完全二叉樹、抱負二叉樹、孩子、雙親、左孩子、

右孩子、先序遍歷、中序遍歷、后序遍歷、層次遍歷、哈夫曼樹、最優(yōu)二叉樹、路徑、路徑

長度、權(quán)、帶權(quán)路徑長度、哈夫曼編碼。

二、樹的概念

樹的定義

樹的遞歸定義：

樹(Tree)是n(n2O)個結(jié)點的有限集T,T為空時稱為空樹，否則它滿意如下兩

個條件：

(1)有且僅有一個特定的稱為根(Root)的結(jié)點；

(2)其余的結(jié)點可分為m(m》0)個互不相交的子集「，T”…，其中每個子集本身又是一

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

留意：

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

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

三、二叉樹的定義

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

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

潔，因此二叉樹顯得特殊重要。

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

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

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

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

在有序樹中，雖然一個結(jié)點的孩子之間是有左右次序的，但是若該結(jié)點只有一個孩

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

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

(一)挨次存儲結(jié)構(gòu)

該方法是把二叉樹的全部結(jié)點依據(jù)肯定的線性次序存儲到一片連續(xù)的存儲單元中。

結(jié)點在這個序列中的相互位置還能反映出結(jié)點之間的規(guī)律關(guān)系。

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

(1)編號方法

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

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

【例】如下圖所示。

(2)編號特點

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

一層結(jié)點個數(shù)的2倍。從一個結(jié)點的編號就可推得其雙親，左、右孩子，兄弟等結(jié)點的編號。

假設(shè)編號為i的結(jié)點是ki（lWiWn）,則有：

①若i>l,則L的雙親編號為［i/2］；若i=l,則K,是根結(jié)點，無雙親。

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

二叉樹中編號i>［n/2］的結(jié)點必定是葉結(jié)點。

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

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

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

2.完全二叉樹的挨次存儲

將完全二叉樹中全部結(jié)點按編號挨次依次存儲在一個向量bt［O..n］中。

其中：

bt［l..n］用來存儲結(jié)點

bt［O］不用或用來存儲結(jié)點數(shù)目。

【例】下表是上圖的完全二叉樹的挨次存儲結(jié)構(gòu)，bt［O］為結(jié)點數(shù)目，b［7］的雙親、左右

孩子分別是bt［3］、bt［14］和bt［15］。

3.一般二叉樹的挨次存儲

（1）詳細方法

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

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

編號

③將結(jié)點按編號存入向量對應(yīng)重量，其中“虛結(jié)點"用表示

【例】上圖中單支樹的挨次存儲結(jié)構(gòu)如下圖

（2）優(yōu)點和缺點

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

②一般的二叉樹采納挨次存儲結(jié)構(gòu)時，雖然簡潔，但易造成存儲空間的鋪張。

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

儲空間。

③在對挨次存儲的二叉樹做插入和刪除結(jié)點操作時，要大量移動結(jié)點。

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

【參見教材】

（二）鏈式存儲結(jié)構(gòu)

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

二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲

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

孩子。結(jié)點的結(jié)構(gòu)為：

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

typedefcharDataType；/*用戶可依據(jù)詳細應(yīng)用定義DataType的實際類型*/

typedefstructnode（

DataTypedata；

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

}BinTNode；/*結(jié)點類型*/

typedefBinTNode*BinTree；/*BinTree為指向BinTNode類型結(jié)點的指針類型*/

3.二叉鏈表（二叉樹的常用鏈式存儲結(jié)構(gòu)）

在一棵二叉樹中，全部類型為BinTNode的結(jié)點，再加上一個指向開頭結(jié)點（即根結(jié)

點）的BinTree型頭指針（即根指針）root,就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，并將其稱為二

叉鏈表。

(示例參見教材)

留意：

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

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

②具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有nT個用來指示結(jié)點的左、右

孩子，其余的n+1個指針域為空。

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

常常要在二叉樹中查找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針

parent,形成一個帶雙親指針的二叉鏈表。

留意：

二叉樹存儲方法的選擇，主要依靠于所要實施的各種運算的頻度。

五、二叉樹的遍歷

(―)中序序列

中序遍歷二叉樹時，對結(jié)點的訪問次序為中序序列

【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為:

DBAECF

(-)先序序列

先序遍歷二叉樹時，對結(jié)點的訪問次序為先序序列

【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為:

ABDCEF

(三)后序序列

后序遍歷二叉樹時，對結(jié)點的訪問次序為后序序列

【例】后序遍歷上圖所示的二叉樹時，得到的后序序列為:

DBEFCA

留意：

(1)在搜尋路線中，若訪問結(jié)點均是第一次經(jīng)過結(jié)點時進行的，則是先序遍歷；若訪

問結(jié)點均是在其次次(或第三次)經(jīng)過結(jié)點時進行的，則是中序遍歷(或后序遍歷)。只要將搜

尋路線上全部在第一次、其次次和第三次經(jīng)過的結(jié)點分別列表，即可分別得到該二叉樹的先

序序列、中序序列和后序序列。

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

都有且僅有一個前趨結(jié)點和一個后繼結(jié)點。為了區(qū)分于樹形結(jié)構(gòu)中前趨（即雙親）結(jié)點和后繼

（即孩子）結(jié)點的概念，對上述三種線性序列，要在某結(jié)點的前趨和后繼之前冠以其遍歷次序

名稱。

六、哈夫曼樹

用哈夫曼算法構(gòu)造哈夫曼樹的要留意以下問題。

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

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

有2n-l個結(jié)點。

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

下面對教材中的哈夫曼編碼加以補充，以關(guān)心同學(xué)們理解。

（-）編碼方案

1.編碼和解碼

數(shù)據(jù)壓縮過程稱為編碼。即將文件中的每個字符均轉(zhuǎn)換為一個惟一的二進制位串。

數(shù)據(jù)解壓過程稱為解碼。即將二進制位串轉(zhuǎn)換為對應(yīng)的字符。

2.等長編碼方案和變長編碼方案

給定的字符集C,可能存在多種編碼方案。

（1）等長編碼方案

等長編碼方案將給定字符集C中每個字符的碼長定為[lg[C|],|C[表示字符集的大

小。

【例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C={a,b,C,

d,e,f},等長編碼需要三位二進制數(shù)字來表示六個字符，因此，整個文件的編碼長度為

300000位。

（2）變長編碼方案

變長編碼方案將頻度高的字符編碼設(shè)置短，將頻度低的字符編碼設(shè)置較長.

【例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集，={a,b,c,

d,e,f},其中每個字符在文件中消失的次數(shù)（簡稱頻度）見表。

字符編碼問題

字

符abCd

ef

頻度(單位：千

次）4513121695

定長編

碼000001010011100

101

變長編

碼01011001111101

1100

依據(jù)計算公式：

（45*1+13*3+12*3+16*3+9*4+584）*1000=224000

整個文件被編碼為224000位，比定長編碼方式節(jié)省了約25%的存儲空間。

留意：

變長編碼可能使解碼產(chǎn)生二義性。產(chǎn)生該問題的緣由是某些字符的編碼可能與其他

字符的編碼開頭部分（稱為前綴）相同。

【例】設(shè)E、T、W分別編碼為00、01、0001,則解碼時無法確定信息串0001是ET還是W。

3.前綴碼方案

對字符集進行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編

碼稱為前綴（編）碼。

留意：

等長編碼是前綴碼

4.最優(yōu)前綴碼

平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼。最優(yōu)的前綴碼對文件的壓縮效果亦

最佳。

其中：

P：為第i個字符得概率，

L為碼長

【例】若將表6.5所示的文件作為統(tǒng)計的樣本，則a至f六個字符的概率分別為0.45,

0.13,0.12,0.16,0.09,0.05,對變長編碼求得的平均碼長為2.24,優(yōu)于定長編碼（平均

碼長為3）。

（二）依據(jù)哈夫曼樹構(gòu)造哈夫曼編碼

采用哈夫曼樹很簡潔求出給定字符集及其概率（或頻度）分布的最優(yōu)前綴碼。哈夫曼編碼

正是一種應(yīng)用廣泛且特別有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20%至

90%,其壓縮效率取決于被壓縮文件的特征。

1.詳細做法

（1）用字符5作為葉子，P：或￡做為葉子C,的權(quán)，構(gòu)造一棵哈夫曼樹，并將樹中左分

支和右分支分別標記為。和1;

（2）將從根到葉子的路徑上的標號依次相連，作為該葉子所表示字符的編碼。該編碼即

為最優(yōu)前綴碼（也稱哈夫曼編碼）。

2.哈夫曼編碼為最優(yōu)前綴碼

由哈夫曼樹求得編碼為最優(yōu)前綴碼的緣由：

①每個葉子字符a的碼長恰為從根到該葉子的路徑長度L,平均碼長（或文件總長）又是二

叉樹的帶權(quán)路徑長度WPL。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長（或文件

總長）亦最小。

②樹中沒有一片葉子是另一葉子的祖先，每片葉子對應(yīng)的編碼就不行能是其它葉子編碼的

前綴。即上述編碼是二進制的前綴碼。

3.求哈夫曼編碼的算法

（1）思想方法

給定字符集的哈夫曼樹生成后，求哈夫曼編碼的詳細實現(xiàn)過程是：依次以葉子

T[i]（0Wi〈n-l）為動身點，向上回溯至根為止。上溯時走左分支則生成代碼0,走右分支

則生成代碼1。

留意：

①由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量

中，并設(shè)一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結(jié)束位

置）。

②當(dāng)某字符編碼完成時，從臨時向量的start處將編碼復(fù)制到該字符相應(yīng)的位串bits中即

可。

③由于字符集大小為n,故變長編碼的長度不會超過n,加上一個結(jié)束符'\0',bits的大

小應(yīng)為n+E

(2)字符集編碼的存儲結(jié)構(gòu)及其算法描述

typedefstruct{

charch；/*存儲字符*/

charbits[n+l]；/*存放編碼位串*/

JCodeNode；

typedefCodeNodeHuffmanCode[n]；

voidCharSetlluffmanEncodingOluffmanTreeT,HuffmanCodeII)

{/*依據(jù)哈夫曼樹T求哈夫曼編碼表H*/

intc,p,i;/*c和p分別指示T中孩子和雙親的位置*/

charcd[n+l]；/*臨時存放編碼*/

intstart；/*指示編碼在cd中的起始位置*/

cd[n]='\0'；/*編碼結(jié)束符*/

for(i=0,i<n,i++){/*依次求葉子T[i]的編碼*/

H[i].ch=getchar()；/*讀入葉子T[i]對應(yīng)的字符*/

start二n；/*編碼起始位置的初值*/

c=i；/*從葉子T[i]開頭上溯*/

while((p=T[c].parent)>=0){/*直至上溯到T[c]是樹根為止

/*若T[c]是T[p]的左孩子，則生成代碼0；否則生成

代碼1

cd[一一start]=(T[p).lchild==C)?'O'：T'；*/

c=p；/*連續(xù)上溯*/

)

strcpybits,&cd[start])；/*復(fù)制編碼位串*/

}/*endfor*/

}/*CharSetHuffmanEncoding*/

七、練習(xí)題

單項選擇題

1.假定一棵二叉樹中，雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30,則葉子結(jié)點數(shù)為

()O

A.15B.16C.17D.47

2.在二叉樹先序遍歷中，任一個結(jié)點均在其子女結(jié)點前面，這種說法()o

A.正確B.不正確

C.無法推斷D.以上均不對

3.二叉樹第k層上最多有()個結(jié)點。

A.2kB.2k-1

C.2-1D.2k1

4.二叉樹的深度為k,則二叉樹最多有()個結(jié)點。

A.2kB.2k-l

C.2k-1D.2k-l

5.設(shè)某一二叉樹先序遍歷為abdec,中序遍歷為dbeac,則該二叉樹后序遍歷的挨次是

()o

A.abdecB.debacC.debcaD.abedc

6.設(shè)某一二叉樹中序遍歷為badce,后序遍歷為bdeca,則該二叉樹先序遍歷的挨次是

（

A.adbecB.decabC.debacD.abcde

7.樹最適合于用來表示（）（＞

A.線性結(jié)構(gòu)的數(shù)據(jù)

B.挨次結(jié)構(gòu)的數(shù)據(jù)

C.元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù)

D.元素之間有包含和層次關(guān)系的數(shù)據(jù)

8.一棵非空的二叉樹，先序遍歷與后續(xù)遍歷正好相反，則該二叉樹滿意（）o

A.無左孩子B.無右孩子

C.只有一個葉子結(jié)點D.任意二叉樹

9.設(shè)a,b為一棵二叉樹的兩個結(jié)點，在后續(xù)遍歷中，a在b前的條件是（）。

A.a在b上方B.a在b下方

C.a在b左方D.a在b右方

10.權(quán)值為｛1,2,6,8｝的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（