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

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

第6章樹(shù)和二叉樹(shù)

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

一切具有層次關(guān)系的問(wèn)題都可以用樹(shù)來(lái)描述。

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

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

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

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

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

二、樹(shù)的概念

樹(shù)的定義

樹(shù)的遞歸定義：

樹(shù)(Tree)是n(n2O)個(gè)結(jié)點(diǎn)的有限集T,T為空時(shí)稱(chēng)為空樹(shù)，否則它滿意如下兩

個(gè)條件：

(1)有且僅有一個(gè)特定的稱(chēng)為根(Root)的結(jié)點(diǎn)；

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

棵樹(shù)，并稱(chēng)其為根的子樹(shù)(Subree)。

留意：

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

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

三、二叉樹(shù)的定義

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

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

潔，因此二叉樹(shù)顯得特殊重要。

(1)二叉樹(shù)與無(wú)序樹(shù)不同

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

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

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

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

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

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

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

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

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

1.完全二叉樹(shù)結(jié)點(diǎn)編號(hào)

(1)編號(hào)方法

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

全部結(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹(shù)結(jié)構(gòu)的線性序列。

【例】如下圖所示。

(2)編號(hào)特點(diǎn)

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

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

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

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

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

二叉樹(shù)中編號(hào)i>［n/2］的結(jié)點(diǎn)必定是葉結(jié)點(diǎn)。

③若2i+lWn,則K；的右孩子的編號(hào)是2i+l；否則，K無(wú)右孩子。

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

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

2.完全二叉樹(shù)的挨次存儲(chǔ)

將完全二叉樹(shù)中全部結(jié)點(diǎn)按編號(hào)挨次依次存儲(chǔ)在一個(gè)向量bt［O..n］中。

其中：

bt［l..n］用來(lái)存儲(chǔ)結(jié)點(diǎn)

bt［O］不用或用來(lái)存儲(chǔ)結(jié)點(diǎn)數(shù)目。

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

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

3.一般二叉樹(shù)的挨次存儲(chǔ)

（1）詳細(xì)方法

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

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

編號(hào)

③將結(jié)點(diǎn)按編號(hào)存入向量對(duì)應(yīng)重量，其中“虛結(jié)點(diǎn)"用表示

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

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

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

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

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

儲(chǔ)空間。

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

4.二叉樹(shù)的挨次存儲(chǔ)結(jié)構(gòu)類(lèi)型定義

【參見(jiàn)教材】

（二）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

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

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

2.結(jié)點(diǎn)的類(lèi)型說(shuō)明

typedefcharDataType；/*用戶(hù)可依據(jù)詳細(xì)應(yīng)用定義DataType的實(shí)際類(lèi)型*/

typedefstructnode（

DataTypedata；

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

}BinTNode；/*結(jié)點(diǎn)類(lèi)型*/

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

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

在一棵二叉樹(shù)中，全部類(lèi)型為BinTNode的結(jié)點(diǎn)，再加上一個(gè)指向開(kāi)頭結(jié)點(diǎn)（即根結(jié)

點(diǎn)）的BinTree型頭指針（即根指針）root,就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并將其稱(chēng)為二

叉鏈表。

(示例參見(jiàn)教材)

留意：

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

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

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

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

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

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

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

留意：

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

五、二叉樹(shù)的遍歷

(―)中序序列

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

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

DBAECF

(-)先序序列

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

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

ABDCEF

(三)后序序列

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

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

DBEFCA

留意：

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

問(wèn)結(jié)點(diǎn)均是在其次次(或第三次)經(jīng)過(guò)結(jié)點(diǎn)時(shí)進(jìn)行的，則是中序遍歷(或后序遍歷)。只要將搜

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

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

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

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

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

名稱(chēng)。

六、哈夫曼樹(shù)

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

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

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

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

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

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

（-）編碼方案

1.編碼和解碼

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

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

2.等長(zhǎng)編碼方案和變長(zhǎng)編碼方案

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

（1）等長(zhǎng)編碼方案

等長(zhǎng)編碼方案將給定字符集C中每個(gè)字符的碼長(zhǎng)定為[lg[C|],|C[表示字符集的大

小。

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

d,e,f},等長(zhǎng)編碼需要三位二進(jìn)制數(shù)字來(lái)表示六個(gè)字符，因此，整個(gè)文件的編碼長(zhǎng)度為

300000位。

（2）變長(zhǎng)編碼方案

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

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

d,e,f},其中每個(gè)字符在文件中消失的次數(shù)（簡(jiǎn)稱(chēng)頻度）見(jiàn)表。

字符編碼問(wèn)題

字

符abCd

ef

頻度(單位：千

次）4513121695

定長(zhǎng)編

碼000001010011100

101

變長(zhǎng)編

碼01011001111101

1100

依據(jù)計(jì)算公式：

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

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

留意：

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

字符的編碼開(kāi)頭部分（稱(chēng)為前綴）相同。

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

3.前綴碼方案

對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編

碼稱(chēng)為前綴（編）碼。

留意：

等長(zhǎng)編碼是前綴碼

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

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

最佳。

其中：

P：為第i個(gè)字符得概率，

L為碼長(zhǎng)

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

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

碼長(zhǎng)為3）。

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

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

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

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

1.詳細(xì)做法

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

支和右分支分別標(biāo)記為。和1;

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

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

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

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

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

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

總長(zhǎng)）亦最小。

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

前綴。即上述編碼是二進(jìn)制的前綴碼。

3.求哈夫曼編碼的算法

（1）思想方法

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

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

則生成代碼1。

留意：

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

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

置）。

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

可。

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

小應(yīng)為n+E

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

typedefstruct{

charch；/*存儲(chǔ)字符*/

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

JCodeNode；

typedefCodeNodeHuffmanCode[n]；

voidCharSetlluffmanEncodingOluffmanTreeT,HuffmanCodeII)

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

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

charcd[n+l]；/*臨時(shí)存放編碼*/

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

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

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

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

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

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

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

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

代碼1

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

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

)

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

}/*endfor*/

}/*CharSetHuffmanEncoding*/

七、練習(xí)題

單項(xiàng)選擇題

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

()O

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

2.在二叉樹(shù)先序遍歷中，任一個(gè)結(jié)點(diǎn)均在其子女結(jié)點(diǎn)前面，這種說(shuō)法()o

A.正確B.不正確

C.無(wú)法推斷D.以上均不對(duì)

3.二叉樹(shù)第k層上最多有()個(gè)結(jié)點(diǎn)。

A.2kB.2k-1

C.2-1D.2k1

4.二叉樹(shù)的深度為k,則二叉樹(shù)最多有()個(gè)結(jié)點(diǎn)。

A.2kB.2k-l

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

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

()o

A.abdecB.debacC.debcaD.abedc

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

（

A.adbecB.decabC.debacD.abcde

7.樹(shù)最適合于用來(lái)表示（）（＞

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

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

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

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

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

A.無(wú)左孩子B.無(wú)右孩子

C.只有一個(gè)葉子結(jié)點(diǎn)D.任意二叉樹(shù)

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

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

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

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