2023年山東廣播電視大學(xué)開放教育數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)第四部分

山東廣播電視大學(xué)開放教育《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)指導(dǎo)樹是一種重要的非線性結(jié)構(gòu),從邏輯角度看,其數(shù)據(jù)元素之間體現(xiàn)的是一對(duì)多的非線性關(guān)系,一切具有層次關(guān)系的問題都可以用樹來描述。一、相關(guān)術(shù)語樹、二叉樹、樹根、子樹、有序樹、無序數(shù)、森林、終端結(jié)點(diǎn)(葉子)、非終端結(jié)點(diǎn)、結(jié)點(diǎn)的度、結(jié)點(diǎn)的層次、樹的深度、滿二叉樹、完全二叉樹、抱負(fù)二叉樹、孩子、雙親、左孩子、右孩子、先序遍歷、中序遍歷、后序遍歷、層次遍歷、哈夫曼樹、最優(yōu)二叉樹、途徑、途徑長(zhǎng)度、權(quán)、帶權(quán)途徑長(zhǎng)度、哈夫曼編碼。二、樹的概念樹的定義

樹的遞歸定義：

樹(Treｅ）是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T,T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件:（1）有且僅有一個(gè)特定的稱為根(Roｏｔ)的結(jié)點(diǎn)；（2)其余的結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的子集Tl，Ｔ２，…,Tｍ,其中每個(gè)子集自身又是一棵樹，并稱其為根的子樹(Sｕbｒee）。注意：

樹的遞歸定義刻畫了樹的固有特性:一棵非空樹是由若干棵子樹構(gòu)成的，而子樹又可由若干棵更小的子樹構(gòu)成。三、二叉樹的定義二叉樹是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式,即使是一般的樹也能簡(jiǎn)樸地轉(zhuǎn)換為二叉樹,并且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)樸，因此二叉樹顯得特別重要。(1)二叉樹與無序樹不同

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

二叉樹并非是樹的特殊情形,它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。(2）二叉樹與度數(shù)為2的有序樹不同

在有序樹中，雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右順序的,但是若該結(jié)點(diǎn)只有一個(gè)孩子，就無須區(qū)分其左右順序。而在二叉樹中，即使是一個(gè)孩子也有左右之分。四、二叉樹的存儲(chǔ)結(jié)構(gòu)(一)順序存儲(chǔ)結(jié)構(gòu)

該方法是把二叉樹的所有結(jié)點(diǎn)按照一定的線性順序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)在這個(gè)序列中的互相位置還能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。1．完全二叉樹結(jié)點(diǎn)編號(hào)(1）編號(hào)辦法

在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中,從樹根起，自上層到下層，每層從左至右,給所有結(jié)點(diǎn)編號(hào),能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列?！纠咳缦聢D所示。（2)編號(hào)特點(diǎn)

完全二叉樹中除最下面一層外,各層都充滿了結(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(1≤i≤n),則有：①若ｉ＞1，則kｉ的雙親編號(hào)為[i/２］；若i=1,則Ki是根結(jié)點(diǎn),無雙親。②若2i≤n,則Ｋｉ的左孩子的編號(hào)是２i；否則，Ki無左孩子，即Kｉ必然是葉子。因此完全二叉樹中編號(hào)i＞[n／2]的結(jié)點(diǎn)必然是葉結(jié)點(diǎn)。③若2ｉ+1≤ｎ，則Ki的右孩子的編號(hào)是2i+1;否則,Ｋi無右孩子。④若i為奇數(shù)且不為1,則Kｉ的左兄弟的編號(hào)是ｉ-1；否則，Kｉ無左兄弟。⑤若i為偶數(shù)且小于n,則Kｉ的右兄弟的編號(hào)是i+1;否則，Ki無右兄弟。2.完全二叉樹的順序存儲(chǔ)

將完全二叉樹中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)向量bt[0．.n］中。

其中:

ｂt[1..n］用來存儲(chǔ)結(jié)點(diǎn)

bt[0]不用或用來存儲(chǔ)結(jié)點(diǎn)數(shù)目?！纠肯卤硎巧蠄D的完全二叉樹的順序存儲(chǔ)結(jié)構(gòu),bｔ[0]為結(jié)點(diǎn)數(shù)目，b［7]的雙親、左右孩子分別是bt[3］、bｔ[l4]和bｔ[15]。3．一般二叉樹的順序存儲(chǔ)(１）具體方法①將一般二叉樹添上一些"虛結(jié)點(diǎn)"，成為＂完全二叉樹"②為了用結(jié)點(diǎn)在向量中的相對(duì)位置來表達(dá)結(jié)點(diǎn)之間的邏輯關(guān)系,按完全二叉樹形式給結(jié)點(diǎn)編號(hào)③將結(jié)點(diǎn)按編號(hào)存入向量相應(yīng)分量，其中"虛結(jié)點(diǎn)＂用"∮＂表達(dá)【例】上圖中單支樹的順序存儲(chǔ)結(jié)構(gòu)如下圖(2）優(yōu)點(diǎn)和缺陷①對(duì)完全二叉樹而言,順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)樸又節(jié)省存儲(chǔ)空間。②一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡(jiǎn)樸，但易導(dǎo)致存儲(chǔ)空間的浪費(fèi)。【例】最壞的情況下,一個(gè)深度為k且只有ｋ個(gè)結(jié)點(diǎn)的右單支樹需要2k-1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。③在對(duì)順序存儲(chǔ)的二叉樹做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。4．二叉樹的順序存儲(chǔ)結(jié)構(gòu)類型定義

【參見教材】（二)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)自身的數(shù)據(jù)外,還應(yīng)設(shè)立兩個(gè)指針域lchｉld和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的結(jié)構(gòu)為:2．結(jié)點(diǎn)的類型說明

typedefcｈａｒDaｔaTyｐe；/*用戶可根據(jù)具體應(yīng)用定義Ｄａt(yī)aTypｅ的實(shí)際類型＊/

typedefstructｎode{

DataＴypｅｄaｔａ;

Sｔrｕctｎodｅ*lcｈild,*rchild;／*左右孩子指針*/

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

typｅdefBinTＮoｄe*BiｎＴrｅe(cuò)；/*BinTreｅ為指向BinTNoｄｅ類型結(jié)點(diǎn)的指針類型*/3.二叉鏈表（二叉樹的常用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）

在一棵二叉樹中,所有類型為ＢinTNode的結(jié)點(diǎn),再加上一個(gè)指向開始結(jié)點(diǎn)(即根結(jié)點(diǎn))的BinTree型頭指針（即根指針)rｏot，就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),并將其稱為二叉鏈表。(示例參見教材)注意：①一個(gè)二叉鏈表由根指針ｒoot惟一擬定。若二叉樹為空,則rｏot=NUＬL;若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。

②具有n個(gè)結(jié)點(diǎn)的二叉鏈表中,共有2n個(gè)指針域。其中只有ｎ-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子，其余的n＋1個(gè)指針域?yàn)榭铡?.帶雙親指針的二叉鏈表

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

注意:

二叉樹存儲(chǔ)方法的選擇，重要依賴于所要實(shí)行的各種運(yùn)算的頻度。五、二叉樹的遍歷AACFEDB(一)中序序列

中序遍歷二叉樹時(shí)，對(duì)結(jié)點(diǎn)的訪問順序?yàn)橹行蛐蛄小纠恐行虮闅v上圖所示的二叉樹時(shí)，得到的中序序列為:

DBAECF(二）先序序列

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

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

ＡＢDＣEF（三）后序序列

后序遍歷二叉樹時(shí),對(duì)結(jié)點(diǎn)的訪問順序?yàn)楹笮蛐蛄小纠亢笮虮闅v上圖所示的二叉樹時(shí)，得到的后序序列為:

DBEFCＡ

注意:（1）在搜索路線中,若訪問結(jié)點(diǎn)均是第一次通過結(jié)點(diǎn)時(shí)進(jìn)行的，則是先序遍歷;若訪問結(jié)點(diǎn)均是在第二次(或第三次）通過結(jié)點(diǎn)時(shí)進(jìn)行的,則是中序遍歷(或后序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次通過的結(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)的概念,對(duì)上述三種線性序列，要在某結(jié)點(diǎn)的前趨和后繼之前冠以其遍歷順序名稱。六、哈夫曼樹用哈夫曼算法構(gòu)造哈夫曼樹的要注意以下問題。

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

②ｎ個(gè)葉子的哈夫曼樹要通過n－1次合并,產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)。③哈夫曼樹是嚴(yán)格的二叉樹,沒有度數(shù)為1的分支結(jié)點(diǎn)。下面對(duì)教材中的哈夫曼編碼加以補(bǔ)充,以幫助同學(xué)們理解。（一）編碼方案1.編碼和解碼

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

數(shù)據(jù)解壓過程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為相應(yīng)的字符。2．等長(zhǎng)編碼方案和變長(zhǎng)編碼方案

給定的字符集C,也許存在多種編碼方案。(１）等長(zhǎng)編碼方案

等長(zhǎng)編碼方案將給定字符集C中每個(gè)字符的碼長(zhǎng)定為[ｌg|C|］，|C｜表達(dá)字符集的大小。【例】設(shè)待壓縮的數(shù)據(jù)文獻(xiàn)共有100000個(gè)字符,這些字符均取自字符集C=｛a，b，c，d,ｅ，f｝，等長(zhǎng)編碼需要三位二進(jìn)制數(shù)字來表達(dá)六個(gè)字符，因此,整個(gè)文獻(xiàn)的編碼長(zhǎng)度為300000位。(２）變長(zhǎng)編碼方案

變長(zhǎng)編碼方案將頻度高的字符編碼設(shè)立短，將頻度低的字符編碼設(shè)立較長(zhǎng)?！纠吭O(shè)待壓縮的數(shù)據(jù)文獻(xiàn)共有1000００個(gè)字符，這些字符均取自字符集C＝｛ａ,b，ｃ,ｄ，ｅ，f｝,其中每個(gè)字符在文獻(xiàn)中出現(xiàn)的次數(shù)（簡(jiǎn)稱頻度)見表。

字符編碼問題

-－------－－----------－-－---－------－－--－－－-－-----－-－--－----－-------

字符

a

ｂ

c

d

e

f

頻度（單位：千次）

45

13

12

16

9

５

定長(zhǎng)編碼

０00

001

01０

011

100

1０１

變長(zhǎng)編碼

0

101

１０0

111

1101

1１0０

-------－--－-------－－----－－-----－--－----------－---－－－----－--------

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

（45*1+13*３＋1２*3+16*３＋9*4+584)＊1０00=2２4000整個(gè)文獻(xiàn)被編碼為22４000位，比定長(zhǎng)編碼方式節(jié)約了約２５％的存儲(chǔ)空間。

注意：

變長(zhǎng)編碼也許使解碼產(chǎn)生二義性。產(chǎn)生該問題的因素是某些字符的編碼也許與其他字符的編碼開始部分(稱為前綴)相同。

【例】設(shè)E、Ｔ、W分別編碼為00、01、0001,則解碼時(shí)無法擬定信息串000１是EＴ還是W。３.前綴碼方案

對(duì)字符集進(jìn)行編碼時(shí),規(guī)定字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴(編）碼。

注意：

等長(zhǎng)編碼是前綴碼4.最優(yōu)前綴碼

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

其中:

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

ｌｉ為碼長(zhǎng)【例】若將表6.5所示的文獻(xiàn)作為記錄的樣本，則ａ至f六個(gè)字符的概率分別為０．45,0.13,0．12，０.１6，0．09,0．05,對(duì)變長(zhǎng)編碼求得的平均碼長(zhǎng)為2．24，優(yōu)于定長(zhǎng)編碼（平均碼長(zhǎng)為3）。（二)根據(jù)哈夫曼樹構(gòu)造哈夫曼編碼運(yùn)用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文獻(xiàn)壓縮掉20%至90％,其壓縮效率取決于被壓縮文獻(xiàn)的特性。１．具體做法（1）用字符ci作為葉子,pi或fｉ做為葉子ｃi的權(quán),構(gòu)造一棵哈夫曼樹,并將樹中左分支和右分支分別標(biāo)記為０和1；(2）將從根到葉子的途徑上的標(biāo)號(hào)依次相連，作為該葉子所表達(dá)字符的編碼。該編碼即為最優(yōu)前綴碼(也稱哈夫曼編碼)。２.哈夫曼編碼為最優(yōu)前綴碼

由哈夫曼樹求得編碼為最優(yōu)前綴碼的因素：①每個(gè)葉子字符cｉ的碼長(zhǎng)恰為從根到該葉子的途徑長(zhǎng)度lｉ,平均碼長(zhǎng)（或文獻(xiàn)總長(zhǎng))又是二叉樹的帶權(quán)途徑長(zhǎng)度ＷPL。而哈夫曼樹是WPL最小的二叉樹,因此編碼的平均碼長(zhǎng)(或文獻(xiàn)總長(zhǎng)）亦最小。②樹中沒有一片葉子是另一葉子的祖先，每片葉子相應(yīng)的編碼就不也許是其它葉子編碼的前綴。即上述編碼是二進(jìn)制的前綴碼。3.求哈夫曼編碼的算法（1)思想方法

給定字符集的哈夫曼樹生成后,求哈夫曼編碼的具體實(shí)現(xiàn)過程是:依次以葉子Ｔ[i](0≤i≤ｎ-1)為出發(fā)點(diǎn)，向上回溯至根為止。上溯時(shí)走左分支則生成代碼0，走右分支則生成代碼１。

注意:①由于生成的編碼與規(guī)定的編碼反序，將生成的代碼先從后往前依次存放在一個(gè)臨時(shí)向量中，并設(shè)一個(gè)指針staｒt指示編碼在該向量中的起始位置（stａrt初始時(shí)指示向量的結(jié)束位置)。②當(dāng)某字符編碼完畢時(shí)，從臨時(shí)向量的sｔart處將編碼復(fù)制到該字符相應(yīng)的位串ｂｉts中即可。③由于字符集大小為ｎ，故變長(zhǎng)編碼的長(zhǎng)度不會(huì)超過n,加上一個(gè)結(jié)束符'\0',bｉtｓ的大小應(yīng)為ｎ+１。(2）字符集編碼的存儲(chǔ)結(jié)構(gòu)及其算法描述

ｔｙpedeｆstrｕcｔ{

cｈarch；/＊存儲(chǔ)字符*/

charｂits[n+1];/＊存放編碼位串*/

｝CoｄｅNoｄe;

ｔypeｄefＣodeNoｄeＨｕffmanCｏdｅ[n］;

voiｄChaｒSetHｕｆfmanEnｃoding(HufｆmaｎTreｅT,ＨuffmanCｏdeH)

{／*根據(jù)哈夫曼樹Ｔ求哈夫曼編碼表Ｈ*/

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

charｃd[ｎ+1];／*臨時(shí)存放編碼*/

intsｔart;／＊指示編碼在ｃd中的起始位置*/

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

ｆor(i＝0，i<n,i＋+)｛/*依次求葉子T[i］的編碼＊/

H[i].ch=ｇｅtｃhａｒ();/*讀入葉子T［i]相應(yīng)的字符＊/

sｔaｒｔ＝n;/*編碼起始位置的初值*／

ｃ=i;／*從葉子T[i]開始上溯*/

ｗｈｉle((p=T[c].parｅｎt）>=0){/*直至上溯到T［c]是樹根為止

/*若T[ｃ]是T［p]的左孩子，則生成代碼０;否則生成代碼１

ｃd[--ｓtart]=(Ｔ［p).１ｃhilｄ＝＝C)？'0'：'１'；*/

c=p；／＊繼續(xù)上溯*/

}

stｒcｐy（H[ｉ]．bitｓ,&cd[start])；/*復(fù)制編碼位串*／

}/*endｆｏr*/

}/＊ＣｈaｒSeｔHｕffmanEncodiｎｇ*/七、練習(xí)題單項(xiàng)選擇題1．假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為()。A．15Ｂ.16C.172．在二叉樹先序遍歷中,任一個(gè)結(jié)點(diǎn)均在其子女結(jié)點(diǎn)前面,這種說法（)。A．對(duì)的B．不對(duì)的C.無法判斷D．以上均不對(duì)３．二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。Ａ．2ｋB．2k-1C.2k-1D.2ｋ－１4．二叉樹的深度為k,則二叉樹最多有(）個(gè)結(jié)點(diǎn)。Ａ.２ｋB.2ｋ－1C．2k-1Ｄ.2k-１5.設(shè)某一二叉樹先序遍歷為ａbdec，中序遍歷為dbeaｃ，則該二叉樹后序遍歷的順序是()。A.abｄecB．ｄebacC.debcaD．a(chǎn)bedｃ6．設(shè)某一二叉樹中序遍歷為baｄce,后序遍歷為bdeca，則該二叉樹先序遍歷的順序是（）。A．a(chǎn)ｄbｅcＢ.ｄecabＣ．debacD．a(chǎn)bcｄe7.樹最適合于用來表達(dá)（)。A.線性結(jié)構(gòu)的數(shù)據(jù)Ｂ.順序結(jié)構(gòu)的數(shù)據(jù)Ｃ.元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù)D．元素之間有包含和層次關(guān)系的數(shù)據(jù)8.一棵非空的二叉樹,先序遍歷與后續(xù)遍歷正好相反，則該二叉樹滿足（）。A.無左孩子B．無右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D．任意二叉樹９．設(shè)a,b為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中,a在ｂ前的條件是（）。A．ａ在ｂ上方