數(shù)據(jù)結(jié)構(gòu)第7章樹形結(jié)構(gòu)一

第7章樹和二叉樹7.1樹的基本概念

7.2二叉樹概念和性質(zhì)7.3二叉樹存儲(chǔ)結(jié)構(gòu)7.4二叉樹的遍歷7.5二叉樹的基本運(yùn)算及其實(shí)現(xiàn)7.6二叉樹的構(gòu)造7.8哈夫曼樹

7.7線索二叉樹本章小結(jié)客觀世界中許多事物存在層次關(guān)系人類社會(huì)家譜社會(huì)組織結(jié)構(gòu)圖書信息管理C文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件127.1.1樹的定義形式化定義：

樹：T={D,R}。D是包含n個(gè)節(jié)點(diǎn)的有窮集合（n≥0）。當(dāng)n=0時(shí)為空樹，否則關(guān)系R滿足以下條件:

有且僅有一個(gè)節(jié)點(diǎn)d0∈D，它對(duì)于關(guān)系R來(lái)說(shuō)沒有前驅(qū)節(jié)點(diǎn)，節(jié)點(diǎn)d0稱作樹的根節(jié)點(diǎn)。除節(jié)點(diǎn)d0外，D中的每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)。

D中每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)可以有零個(gè)或多個(gè)后繼節(jié)點(diǎn)。7.1樹的基本概念

遞歸定義：樹是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合（記為T）。其中：如果n=0，它是一棵空樹，這是樹的特例；如果n>0，這n個(gè)節(jié)點(diǎn)中存在（有僅存在）一個(gè)節(jié)點(diǎn)作為樹的根節(jié)點(diǎn)，簡(jiǎn)稱為根節(jié)點(diǎn)（root），其余節(jié)點(diǎn)可分為m

（m>0）個(gè)互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。rootT1T2Tm…7.1.2樹的表示

（1）樹形表示法。這是樹的最基本的表示，使用一棵倒置的樹表示樹結(jié)構(gòu)，非常直觀和形象。下圖就是采用這種表示法。ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示1

（2）文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文氏圖表示法。ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示2AEFBCGJHDKLMI

（3）凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。邏輯結(jié)構(gòu)表示3ABCDEFGJHIKLM

（4）括號(hào)表示法。將樹的根節(jié)點(diǎn)寫在括號(hào)的左邊，除根節(jié)點(diǎn)之外的其余節(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法。ABCDEFGJHIKLM7.1.3樹的基本術(shù)語(yǔ)

1.節(jié)點(diǎn)的度與樹的度：樹中某個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度。樹中各節(jié)點(diǎn)的度的最大值稱為樹的度，通常將度為m的樹稱為m次樹。2.分支節(jié)點(diǎn)與葉節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)稱為非終端節(jié)點(diǎn),又叫分支節(jié)點(diǎn)。度為零的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或葉節(jié)點(diǎn)。在分支節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)的分支數(shù)就是該節(jié)點(diǎn)的度。如對(duì)于度為1的節(jié)點(diǎn),其分支數(shù)為1，被稱為單分支節(jié)點(diǎn)；對(duì)于度為2的節(jié)點(diǎn)，其分支數(shù)為2，被稱為雙分支節(jié)點(diǎn)，其余類推。ABCDEFGJHIKLM度為3度為2

3.路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)節(jié)點(diǎn)di和dj，若樹中存在一個(gè)節(jié)點(diǎn)序列di,di1,di2,…,din,dj，使得序列中除di外的任一節(jié)點(diǎn)都是其在序列中的前一個(gè)節(jié)點(diǎn)的后繼，則稱該節(jié)點(diǎn)序列為由di到dj的一條路徑，用路徑所通過(guò)的節(jié)點(diǎn)序列(di,di1,di2,…,dj)表示這條路徑。

路徑長(zhǎng)度等于路徑所通過(guò)的節(jié)點(diǎn)數(shù)目減1（即路徑上分支數(shù)目）。ABCDEFGJHIKLMA到K的路徑為A,D,I,K，其長(zhǎng)度為3

4.孩子節(jié)點(diǎn)、雙親節(jié)點(diǎn)和兄弟節(jié)點(diǎn)：在一棵樹中，每個(gè)節(jié)點(diǎn)的后繼，被稱作該節(jié)點(diǎn)的孩子節(jié)點(diǎn)（或子女節(jié)點(diǎn)）。相應(yīng)地，該節(jié)點(diǎn)被稱作孩子節(jié)點(diǎn)的雙親節(jié)點(diǎn)（或父母節(jié)點(diǎn)）。

具有同一雙親的孩子節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)。進(jìn)一步推廣這些關(guān)系，可以把每個(gè)節(jié)點(diǎn)的所有子樹中的節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子孫節(jié)點(diǎn)。

從樹根節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的路徑上經(jīng)過(guò)的所有節(jié)點(diǎn)被稱作該節(jié)點(diǎn)的祖先節(jié)點(diǎn)。ABCDEFGJHIKLM5.節(jié)點(diǎn)的層次和樹的高度：樹中的每個(gè)節(jié)點(diǎn)都處在一定的層次上。節(jié)點(diǎn)的層次從樹根開始定義，根節(jié)點(diǎn)為第1層，它的孩子節(jié)點(diǎn)為第2層,以此類推,一個(gè)節(jié)點(diǎn)所在的層次為其雙親節(jié)點(diǎn)所在的層次加1。樹中節(jié)點(diǎn)的最大層次稱為樹的高度（或樹的深度）。

6.有序樹和無(wú)序樹：若樹中各節(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對(duì)次序是不能隨意變換的，則稱為有序樹，否則稱為無(wú)序樹。ABCDEFGJHIKLM12347.森林：n（n＞0）個(gè)互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近，因?yàn)橹灰褬涞母?jié)點(diǎn)刪去就成了森林。反之，只要給n棵獨(dú)立的樹加上一個(gè)節(jié)點(diǎn)，并把這n棵樹作為該節(jié)點(diǎn)的子樹，則森林就變成了樹。7.1.4樹的性質(zhì)

性質(zhì)1樹中的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度數(shù)加1。證明：根據(jù)樹的定義，在一棵樹中，除樹根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)。也就是說(shuō)，每個(gè)節(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng)，所以除樹根之外的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的分支數(shù)（度數(shù)），從而可得樹中的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度數(shù)加1。度之和＝分支數(shù)分支數(shù)=n-1所以，n=度之和+1ABCDEFGJHIKLM

求解樹的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：對(duì)于度為m的樹，在n、n0、n1、n2、…、nm中只有兩個(gè)參數(shù)未知時(shí)，一般可求出這兩個(gè)值。例如求n和n0的求解過(guò)程如下：

n=n0+n1+…+nm

度之和=n－1

度之和=n1+2n2+…+mnm

所以有：n＝n1+2n2+…+mnm+1=n0+n1+…+nm

這樣：n0=n2+…+(m－1)nm+1求解方法歸納

例：一棵度為4的樹T中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)度為1的節(jié)點(diǎn)，則樹T的葉子節(jié)點(diǎn)個(gè)數(shù)是

。

A.41 B.82C.113 D.122注：本題為2010年全國(guó)考研題

性質(zhì)2度為m的樹中第i層上至多有mi-1個(gè)節(jié)點(diǎn)，這里應(yīng)有i≥1。

證明（采用數(shù)學(xué)歸納法）

對(duì)于第一層,因?yàn)闃渲械牡谝粚由现挥幸粋€(gè)節(jié)點(diǎn)，即整個(gè)樹的根節(jié)點(diǎn),而由i=1代入mi-1，得mi-1=m1-1=1，也同樣得到只有一個(gè)節(jié)點(diǎn)，顯然結(jié)論成立。假設(shè)對(duì)于第(i-1)層（i＞1）命題成立，即度為m的樹中第(i-1)層上至多有mi-2個(gè)節(jié)點(diǎn)。則根據(jù)樹的度的定義，度為m的樹中每個(gè)節(jié)點(diǎn)至多有m個(gè)孩子節(jié)點(diǎn)，所以第i層上的節(jié)點(diǎn)數(shù)至多為第(i-1)層上節(jié)點(diǎn)數(shù)的m倍，即至多為mi-2×m=mi-1個(gè)，這與命題相同，故命題成立。JIACBDHGFEKLM7.1.6樹的存儲(chǔ)結(jié)構(gòu)1.雙親存儲(chǔ)結(jié)構(gòu)

這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)，用一組連續(xù)空間存儲(chǔ)樹的所有節(jié)點(diǎn)，同時(shí)在每個(gè)節(jié)點(diǎn)中附設(shè)一個(gè)偽指針指示其雙親節(jié)點(diǎn)的位置。樹的雙親存儲(chǔ)結(jié)構(gòu)示意圖雙親存儲(chǔ)結(jié)構(gòu)的類型聲明如下：typedefstruct{

ElemTypedata; //節(jié)點(diǎn)的值

intparent; //指向雙親的位置}PTree[MaxSize];思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？2.孩子鏈存儲(chǔ)結(jié)構(gòu)

孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹的度（即樹中所有節(jié)點(diǎn)度的最大值）設(shè)計(jì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)指針域個(gè)數(shù)。以下左圖的樹對(duì)應(yīng)的孩子鏈存儲(chǔ)結(jié)構(gòu)如右圖所示。樹的孩子鏈存儲(chǔ)結(jié)構(gòu)示意圖孩子鏈存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)類型聲明如下：typedefstructnode{ElemTypedata; //節(jié)點(diǎn)的值

structnode*sons[MaxSons]; //指向孩子節(jié)點(diǎn)}TSonNode;其中，MaxSons為最多的孩子節(jié)點(diǎn)個(gè)數(shù)。思考題：有多少個(gè)空指針域？思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？3.孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)

孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)節(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)數(shù)據(jù)元素域，一個(gè)該節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)指針域，一個(gè)該節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)指針域。樹的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖兄弟鏈存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的類型聲明如下：typedefstructtnode{ElemTypedata; //節(jié)點(diǎn)的值

structtnode*hp; //指向兄弟

structtnode*vp; //指向孩子節(jié)點(diǎn)}TSBNode;每個(gè)節(jié)點(diǎn)固定只有兩個(gè)指針域。思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？7.2.1二叉樹概念

二叉樹是有限的節(jié)點(diǎn)集合。

這個(gè)集合或者是空。

或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。注意：二叉樹的定義是一種遞歸定義。7.2二叉樹概念和性質(zhì)

二叉樹的五種基本形態(tài)：空樹N只含根節(jié)點(diǎn)L右子樹為空樹NL左右子樹均不為空樹N左子樹為空樹NRR

二叉樹是可以采用樹的邏輯結(jié)構(gòu)表示法，其四種表示法也都適用：樹形表示法文氏圖表示法凹入表示法括號(hào)表示法

在一棵二叉樹中,如果所有分支節(jié)點(diǎn)都有左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)，并且葉節(jié)點(diǎn)都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。

下圖所示就是一棵滿二叉樹。可以對(duì)滿二叉樹的節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從樹根為1開始，按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。

若二叉樹中最多只有最下面兩層的節(jié)點(diǎn)的度數(shù)可以小于2，并且最下面一層的葉節(jié)點(diǎn)都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。

如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉樹中每個(gè)節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，編號(hào)的方法同滿二叉樹相同。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。7.2.2二叉樹性質(zhì)

性質(zhì)1非空二叉樹上葉節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1。證明：設(shè)二叉樹上葉節(jié)點(diǎn)數(shù)為n0，單分支節(jié)點(diǎn)數(shù)為n1，雙分支節(jié)點(diǎn)數(shù)為n2，則總節(jié)點(diǎn)數(shù)n=n0+n1+n2。在一棵二叉樹中，所有節(jié)點(diǎn)的分支數(shù)（即度數(shù)）應(yīng)等于單分支節(jié)點(diǎn)數(shù)加上雙分支節(jié)點(diǎn)數(shù)的2倍，即總的分支數(shù)=n1+2n2。由于二叉樹中除根節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)都有唯一的一個(gè)分支指向它，因此二叉樹中有：總的分支數(shù)=總節(jié)點(diǎn)數(shù)-1。由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1

A

F

G

E

D

C

B求解二叉樹的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：通常利用二叉樹的性質(zhì)1，即n0=n2+1來(lái)求解這類問(wèn)題，也常利用以下關(guān)系求解：n=n0+n1+n2度之和=n-1度之和=n1+2n2所以有：

n=n1+2n2求解方法歸納

性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)節(jié)點(diǎn)，這里應(yīng)有i≥1。由樹的性質(zhì)2可推出。性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)節(jié)點(diǎn)（h≥1）。由樹的性質(zhì)3可推出。

性質(zhì)4對(duì)完全二叉樹中編號(hào)為i的節(jié)點(diǎn)（1≤i≤n，n≥1，n為節(jié)點(diǎn)數(shù)）有：（1）若i≤n/2，即2i≤n，則編號(hào)為i的節(jié)點(diǎn)為分支節(jié)點(diǎn)，否則為葉子節(jié)點(diǎn)。（2）若n為奇數(shù)，則每個(gè)分支節(jié)點(diǎn)都既有左孩子節(jié)點(diǎn)，也有右孩子節(jié)點(diǎn)；若n為偶數(shù)，則編號(hào)最大的分支節(jié)點(diǎn)只有左孩子節(jié)點(diǎn)，沒有右孩子節(jié)點(diǎn)，其余分支節(jié)點(diǎn)都有左、右孩子節(jié)點(diǎn)。i/2i2i2i+1

（3）若編號(hào)為i的節(jié)點(diǎn)有左孩子節(jié)點(diǎn)，則左孩子節(jié)點(diǎn)的編號(hào)為2i；若編號(hào)為i的節(jié)點(diǎn)有右孩子節(jié)點(diǎn)，則右孩子節(jié)點(diǎn)的編號(hào)為(2i+1)。（4）除樹根節(jié)點(diǎn)外,若一個(gè)節(jié)點(diǎn)的編號(hào)為i，則它的雙親節(jié)點(diǎn)的編號(hào)為i/2，也就是說(shuō)，當(dāng)i為偶數(shù)時(shí)，其雙親節(jié)點(diǎn)的編號(hào)為i/2,它是雙親節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，當(dāng)i為奇數(shù)時(shí)，其雙親節(jié)點(diǎn)的編號(hào)為(i-1)/2，它是雙親節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。i/2i2i2i+1

性質(zhì)5具有n個(gè)（n＞0）節(jié)點(diǎn)的完全二叉樹的高度為log2n+1或log2n+1。由完全二叉樹的定義和樹的性質(zhì)3可推出。7.2.3二叉樹與樹、森林之間的轉(zhuǎn)換1．森林、樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹步驟如下：（1）加線：在所有相鄰兄弟節(jié)點(diǎn)（森林中每棵樹的根節(jié)點(diǎn)可看成是兄弟節(jié)點(diǎn)）之間加一水平連線。（2）刪線：對(duì)每個(gè)非葉節(jié)點(diǎn)k,除了其最左邊的孩子節(jié)點(diǎn)外，刪去k與其他孩子節(jié)點(diǎn)的連線。（3）旋轉(zhuǎn)：所有水平線段以左邊節(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度。由一般的樹轉(zhuǎn)換的二叉樹的根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)始終為空，原因是一般的樹的根節(jié)點(diǎn)不存在兄弟節(jié)點(diǎn)和相鄰的樹。森林轉(zhuǎn)換為二叉樹（1）轉(zhuǎn)換：將森林中的每棵樹轉(zhuǎn)換為相應(yīng)的二叉樹。（2）連接：第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，直到所有的二叉樹連接在一起，即完成森林向二叉樹的轉(zhuǎn)換。（3）旋轉(zhuǎn)：以根結(jié)點(diǎn)為軸，將整棵樹按順時(shí)針旋轉(zhuǎn)一定的角度，得到一棵層次分明的二叉樹。

（a）森林（b）森林中每棵樹對(duì)應(yīng)的二叉樹（c）森林對(duì)應(yīng)的二叉樹2023/2/339

2.二叉樹還原為樹或森林（1）連線：若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、……，都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連接起來(lái)。（2）刪線：刪除原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。（3）調(diào)整：調(diào)整由上兩步得到的樹或森林，使之層次分明。將一棵二叉樹還原為樹的過(guò)程

例

設(shè)森林F中有3棵樹，第一、第二和第三棵樹的節(jié)點(diǎn)個(gè)數(shù)分別為9、8和7，則與森林F對(duì)應(yīng)的二叉樹根節(jié)點(diǎn)的右子樹上的節(jié)點(diǎn)個(gè)數(shù)是

。

A.16 B.15 C.7 D.17思考題：

樹二叉樹，二叉樹樹為什么沒有討論樹的算法？7.3.1二叉樹的順序存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的存放次序是：對(duì)該樹中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，其編號(hào)從小到大的順序就是節(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉樹存儲(chǔ)到一維數(shù)組中,則該編號(hào)就是下標(biāo)值加1（注意C/C++語(yǔ)言中數(shù)組的起始下標(biāo)為0）。樹中各節(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)相同。利用二叉樹的性質(zhì)4。7.3二叉樹存儲(chǔ)結(jié)構(gòu)

ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)（不用下標(biāo)為0的元素）ABCDEF

A

B

D#C#E######F12345678910111213142511437一般的二叉樹先用空節(jié)點(diǎn)補(bǔ)全成為完全二叉樹，然后對(duì)節(jié)點(diǎn)編號(hào)typedefElemTypeSqBTree[MaxSize];SqBTreebt="#ABD#C#E######F";7.3.2二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

在二叉樹的鏈接存儲(chǔ)中，節(jié)點(diǎn)的結(jié)構(gòu)如下:

typedefstructnode{ElemTypedata;structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)（即左、右子樹的根節(jié)點(diǎn)）的存儲(chǔ)位置。二叉樹及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈

ABCDEGFAB∧∧D∧G∧C∧E∧∧F∧b7.4.1二叉樹的基本運(yùn)算概述

歸納起來(lái)，二叉樹有以下基本運(yùn)算：（1）創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號(hào)表示法的字符串*str生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（2）查找節(jié)點(diǎn)FindNode(*b,x)：在二叉樹b中尋找data域值為x的節(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針。（3）找孩子節(jié)點(diǎn)LchildNode(p)和Rchild-Node(p)：分別求二叉樹中節(jié)點(diǎn)*p的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)。7.4二叉樹的基本運(yùn)算及其實(shí)現(xiàn)

（4）求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空，則其高度為0；否則，其高度等于左子樹與右子樹中的最大高度加l。（5）輸出二叉樹DispBTNode(*b)：以括號(hào)表示法輸出一棵二叉樹。7.4.2二叉樹的基本運(yùn)算算法實(shí)現(xiàn)（1）創(chuàng)建二叉樹CreateBTNode(*b,*str)略

用ch掃描采用括號(hào)表示法表示二叉樹的字符串。分以下幾種情況：①若ch='('：則將前面剛創(chuàng)建的節(jié)點(diǎn)作為雙親節(jié)點(diǎn)進(jìn)棧，并置k=1，表示其后創(chuàng)建的節(jié)點(diǎn)將作為這個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)；②若ch=')'：表示棧中節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)處理完畢，退棧；③若ch=‘,’：表示其后創(chuàng)建的節(jié)點(diǎn)為右孩子節(jié)點(diǎn)，置k=2；

④其他情況：當(dāng)k=1時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的左孩子節(jié)點(diǎn)；當(dāng)k=2時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。如此循環(huán)直到str處理完畢。

算法中使用一個(gè)棧St保存雙親節(jié)點(diǎn)，top為其棧指針，k指定其后處理的節(jié)點(diǎn)是雙親節(jié)點(diǎn)（保存在棧中）的左孩子節(jié)點(diǎn)（k=1）還是右孩子節(jié)點(diǎn)（k=2）。A(B(D(,G)),C(E,F))Ak=12BAB^^D^G^C^E^^F^DC根據(jù)括號(hào)表示法字符串構(gòu)造二叉樹voidCreateBTNode(BTNode*&b,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL; //建立的二叉樹初始時(shí)為空

ch=str[j];while(ch!='\0') //str未掃描完時(shí)循環(huán)

{switch(ch){ case'(':top++;St[top]=p;k=1;break;

//為左孩子節(jié)點(diǎn)

case')':top--;break; case',':k=2;break;

//為孩子節(jié)點(diǎn)右節(jié)點(diǎn)default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) //p為二叉樹的根節(jié)點(diǎn)

b=p; else //已建立二叉樹根節(jié)點(diǎn)

{switch(k){ case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; }}}j++;ch=str[j];}}（2）查找節(jié)點(diǎn)FindNode(*b,x)

采用先序遍歷遞歸算法查找值為x的節(jié)點(diǎn)。找到后返回其指針，否則返回NULL。算法如下：

BTNode*FindNode(BTNode*b,ElemTypex){BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x); if(p!=NULL)returnp; elsereturnFindNode(b->rchild,x);}}（3）找孩子節(jié)點(diǎn)LchildNode(p)和RchildNode(p)

直接返回*p節(jié)點(diǎn)的左孩子節(jié)點(diǎn)或右孩子節(jié)點(diǎn)的指針。算法如下：

BTNode*LchildNode(BTNode*p){returnp->lchild;}BTNode*RchildNode(BTNode*p){returnp->rchild;}（4）求高度BTNodeDepth(*b)

求二叉樹的高度的遞歸模型f()如下：

f(b)=0 b=NULLf(b)=MAX{f(b->lchild),f(b->rchild)}+1其他情況intBTNodeDepth(BTNode*b){intlchilddep,rchilddep;if(b==NULL)return(0);//空樹的高度為0else{lchilddep=BTNodeDepth(b->lchild);

//求左子樹的高度為lchilddep rchilddep=BTNodeDepth(b->rchild);

//求右子樹的高度為rchilddep return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1));}}（5）輸出二叉樹DispBTNode(*b)

用括弧表示法輸出二叉樹。對(duì)于非空二叉樹b，先輸出其元素值，當(dāng)存在左孩子節(jié)點(diǎn)或右孩子節(jié)點(diǎn)時(shí)，輸出一個(gè)“(”符號(hào)，然后遞歸處理左子樹，輸出一個(gè)“,”符號(hào)，遞歸處理右子樹，最后輸出一個(gè)“)”符號(hào)。voidDispBTNode(BTNode*b){if(b!=NULL){printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) {printf("(");

DispBTNode(b->lchild); //遞歸處理左子樹

if(b->rchild!=NULL)printf(",");

DispBTNode(b->rchild); //遞歸處理右子樹

printf(")"); }}}7.5.1二叉樹遍歷的概念

二叉樹的遍歷是指按照一定次序訪問(wèn)樹中所有節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。它是最基本的運(yùn)算,是二叉樹中所有其他運(yùn)算的基礎(chǔ)。7.5二叉樹的遍歷1.先序遍歷過(guò)程先序遍歷二叉樹的過(guò)程是：

訪問(wèn)根節(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。ABCDEFGHK先序序列：ABCDEHGKF試按前序（先序）遍歷算法構(gòu)造一棵二叉樹。分析：可以參照上述前序遍歷的算法設(shè)定二叉樹各結(jié)點(diǎn)的值：（1）輸入根結(jié)點(diǎn)的值；（2）若左子樹不空，則輸入左子樹，否則輸入一個(gè)結(jié)束符；（3）若右子樹不空，則輸入右子樹，否則輸入一個(gè)結(jié)束符。對(duì)于圖所示的二叉樹，如果以@代表結(jié)束符，則按該算法輸入的順序?yàn)椋篈BD@@EG@@@C@F@@先序遍歷法創(chuàng)建二叉樹BTNode*CreateBinTree(){ charch; BTNode*t; //用全局變量，確定當(dāng)前要?jiǎng)?chuàng)建結(jié)點(diǎn)的值

ch=strs[i]; i++; if(ch=='@')return(NULL); else { t=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建根節(jié)點(diǎn)

t->data=ch; t->lchild=CreateBinTree();//創(chuàng)建左子樹

t->rchild=CreateBinTree();//創(chuàng)建右子樹

return(t);//創(chuàng)建完畢，返回節(jié)點(diǎn)指針

}}2.中序遍歷過(guò)程中序遍歷二叉樹的過(guò)程是：

中序遍歷左子樹；訪問(wèn)根節(jié)點(diǎn)；中序遍歷右子樹。ABCDEFGHK中序序列：ABCDEHGKF3.后序遍歷過(guò)程后序遍歷二叉樹的過(guò)程是：

后序遍歷左子樹；后序遍歷右子樹；訪問(wèn)根節(jié)點(diǎn)。ABCDEFGHK后序序列：ABCDEHGKF7.5.3二叉樹遍歷遞歸算法

由二叉樹的三種遍歷過(guò)程直接得到如下三種遞歸算法。先序遍歷的遞歸算法：

voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);//訪問(wèn)根節(jié)點(diǎn)

PreOrder(b->lchild);

PreOrder(b->rchild);}}ABCDEFGHK先序序列：^A形參T取值下層調(diào)用結(jié)束后返回到主調(diào)應(yīng)該執(zhí)行的語(yǔ)句ABCDEHGKF^B445^C4^D4555^E45^G45^H45^K45^F45遞歸算法執(zhí)行時(shí)系統(tǒng)棧的變化遞歸算法執(zhí)行過(guò)程：voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);

PreOrder(b->lchild);

PreOrder(b->rchild);}}

中序遍歷的遞歸算法：

voidInOrder(BTNode*b){if(b!=NULL){InOrder(b->lchild); printf("%c",b->data);//訪問(wèn)根節(jié)點(diǎn)

InOrder(b->rchild);}}

后序遍歷遞歸算法：

voidPostOrder(BTNode*b){if(b!=NULL){PostOrder(b->lchild);

PostOrder(b->rchild); printf("%c",b->data);//訪問(wèn)根節(jié)點(diǎn)

}}思考題：

每種遍歷序列提供了什么信息？為什么三種遍歷都采用遞歸求解？

例7.5假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹的所有節(jié)點(diǎn)個(gè)數(shù)。

解：計(jì)算一棵二叉樹b中所有節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下：

f(b)=0 若b=NULL

f(b)=f(b->lchild)+f(b->rchild)+1 其他情況bb->lchildb->rchild對(duì)應(yīng)的遞歸算法如下：intNodes(BTNode*b){intnum1,num2;if(b==NULL) return0;elsereturnNodes(b->lchild)+Nodes(b->rchild)+1}提示：本題算法是基于后序遍歷的。

例7.6假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹的所有葉子節(jié)點(diǎn)個(gè)數(shù)。

解：計(jì)算一棵二叉樹b中所有葉子節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下：

f(b)=0 若b=NULL

f(b)=1 若*b為葉子節(jié)點(diǎn)

f(b)=f(b->lchild)+f(b->rchild) 其他情況intLeafNodes(BTNode*b){

intnum1,num2;

if(b==NULL)return0;elseif(b->lchild==NULL&&b->rchild==NULL)return1;else{ num1=LeafNodes(b->lchild); num2=LeafNodes(b->rchild); return(num1+num2);}}

例7.7假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹的所有單分支節(jié)點(diǎn)個(gè)數(shù)。

解：計(jì)算一棵二叉樹b中所有單分支節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下：

f(b)=0 若b=NULL

f(b)=f(b->lchild)+f(b->rchild)+1 若*b為單分支節(jié)點(diǎn)

f(b)=f(b->lchild)+f(b->rchild) 其他情況intSSonNodes(BTNode*b){

if(b==NULL)

return0;

elseif(b->lchild!=NULL&&b->rchild==NULL|| b->lchild==NULL&&b->rchild!=NULL) //為單分支節(jié)點(diǎn)

returnSSonNodes(b->lchild)+SSonNodes(b->rchild)+1;else //為雙分支節(jié)點(diǎn)或葉子節(jié)點(diǎn)時(shí)

returnSSonNodes(b->lchild)+SSonNodes(b->rchild);}

例7.8假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹中值為k的節(jié)點(diǎn)個(gè)數(shù)。

解：計(jì)算一棵二叉樹b中值為k的節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b,k)如下：

f(b,k)=0 當(dāng)b=NULLf(b,k)=1+f(b->lchild,k)+f(b->rchild,k)當(dāng)b->data=k時(shí)

f(b,k)=f(b->lchild,k)+f(b->rchild,k) 其他情況intCountk(BTNode*b,ElemTypek){if(b==NULL)return0;elseif(b->data==k)return(1+Countk(b->lchild,k)+Countk(b->rchild,k));elsereturn(Countk(b->lchild,k)+Countk(b->rchild,k));}提示：本題算法是基于先序遍歷的。

例7.9假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法把二叉樹b復(fù)制到二叉樹t中。

解：其遞歸模型如下：

f(b,t)

t=NULL 若b=NULL

f(b,t)

復(fù)制根節(jié)點(diǎn)*b產(chǎn)生*t節(jié)點(diǎn); 其他情況

f(b->lchild,t->lchild);f(b->rchild,t->rchild);voidCopy(BTNode*b,BTNode*&t){if(b==NULL)t=NULL;else{t=(BTNode*)malloc(sizeof(BTNode)); t->data=b->data; //復(fù)制一個(gè)根節(jié)點(diǎn)*t

Copy(b->lchild,t->lchild);//遞歸復(fù)制左子樹

Copy(b->rchild,t->rchild)；//遞歸復(fù)制右子樹

}}

例7.10設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法把二叉樹b的左、右子