數(shù)據(jù)結構第7章樹形結構一

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

7.2二叉樹概念和性質7.3二叉樹存儲結構7.4二叉樹的遍歷7.5二叉樹的基本運算及其實現(xiàn)7.6二叉樹的構造7.8哈夫曼樹

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

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

有且僅有一個節(jié)點d0∈D，它對于關系R來說沒有前驅節(jié)點，節(jié)點d0稱作樹的根節(jié)點。除節(jié)點d0外，D中的每個節(jié)點對于關系R來說都有且僅有一個前驅節(jié)點。

D中每個節(jié)點對于關系R來說可以有零個或多個后繼節(jié)點。7.1樹的基本概念

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

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

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

（2）文氏圖表示法。使用集合以及集合的包含關系描述樹結構。下圖就是樹的文氏圖表示法。ABCDEFGJHIKLM邏輯結構表示2AEFBCGJHDKLMI

（3）凹入表示法。使用線段的伸縮描述樹結構。下圖是樹的凹入表示法。邏輯結構表示3ABCDEFGJHIKLM

（4）括號表示法。將樹的根節(jié)點寫在括號的左邊，除根節(jié)點之外的其余節(jié)點寫在括號中并用逗號間隔來描述樹結構。下圖是樹的括號表示法。ABCDEFGJHIKLM7.1.3樹的基本術語

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

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

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

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

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

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

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

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

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

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個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則樹T的葉子節(jié)點個數(shù)是

。

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

性質2度為m的樹中第i層上至多有mi-1個節(jié)點，這里應有i≥1。

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

對于第一層,因為樹中的第一層上只有一個節(jié)點，即整個樹的根節(jié)點,而由i=1代入mi-1，得mi-1=m1-1=1，也同樣得到只有一個節(jié)點，顯然結論成立。假設對于第(i-1)層（i＞1）命題成立，即度為m的樹中第(i-1)層上至多有mi-2個節(jié)點。則根據(jù)樹的度的定義，度為m的樹中每個節(jié)點至多有m個孩子節(jié)點，所以第i層上的節(jié)點數(shù)至多為第(i-1)層上節(jié)點數(shù)的m倍，即至多為mi-2×m=mi-1個，這與命題相同，故命題成立。JIACBDHGFEKLM7.1.6樹的存儲結構1.雙親存儲結構

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

ElemTypedata; //節(jié)點的值

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

孩子鏈存儲結構可按樹的度（即樹中所有節(jié)點度的最大值）設計節(jié)點的孩子節(jié)點指針域個數(shù)。以下左圖的樹對應的孩子鏈存儲結構如右圖所示。樹的孩子鏈存儲結構示意圖孩子鏈存儲結構的節(jié)點類型聲明如下：typedefstructnode{ElemTypedata; //節(jié)點的值

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

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

structtnode*hp; //指向兄弟

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

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

這個集合或者是空。

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

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

二叉樹是可以采用樹的邏輯結構表示法，其四種表示法也都適用：樹形表示法文氏圖表示法凹入表示法括號表示法

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

下圖所示就是一棵滿二叉樹?？梢詫M二叉樹的節(jié)點進行連續(xù)編號，約定編號從樹根為1開始，按照層數(shù)從小到大、同一層從左到右的次序進行。圖中每個節(jié)點外邊的數(shù)字為對該節(jié)點的編號。

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

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

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

A

F

G

E

D

C

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

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

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

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

（3）若編號為i的節(jié)點有左孩子節(jié)點，則左孩子節(jié)點的編號為2i；若編號為i的節(jié)點有右孩子節(jié)點，則右孩子節(jié)點的編號為(2i+1)。（4）除樹根節(jié)點外,若一個節(jié)點的編號為i，則它的雙親節(jié)點的編號為i/2，也就是說，當i為偶數(shù)時，其雙親節(jié)點的編號為i/2,它是雙親節(jié)點的左孩子節(jié)點，當i為奇數(shù)時，其雙親節(jié)點的編號為(i-1)/2，它是雙親節(jié)點的右孩子節(jié)點。i/2i2i2i+1

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

（a）森林（b）森林中每棵樹對應的二叉樹（c）森林對應的二叉樹2023/2/339

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

例

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

。

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

樹二叉樹，二叉樹樹為什么沒有討論樹的算法？7.3.1二叉樹的順序存儲結構

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

ABCDEFGHIJK123456789101112131415順序存儲結構（不用下標為0的元素）ABCDEF

A

B

D#C#E######F12345678910111213142511437一般的二叉樹先用空節(jié)點補全成為完全二叉樹，然后對節(jié)點編號typedefElemTypeSqBTree[MaxSize];SqBTreebt="#ABD#C#E######F";7.3.2二叉樹的鏈式存儲結構

在二叉樹的鏈接存儲中，節(jié)點的結構如下:

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

其中,data表示值域,用于存儲對應的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲左孩子節(jié)點和右孩子節(jié)點（即左、右子樹的根節(jié)點）的存儲位置。二叉樹及其鏈式存儲結構：二叉鏈

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

歸納起來，二叉樹有以下基本運算：（1）創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串*str生成對應的鏈式存儲結構。（2）查找節(jié)點FindNode(*b,x)：在二叉樹b中尋找data域值為x的節(jié)點，并返回指向該節(jié)點的指針。（3）找孩子節(jié)點LchildNode(p)和Rchild-Node(p)：分別求二叉樹中節(jié)點*p的左孩子節(jié)點和右孩子節(jié)點。7.4二叉樹的基本運算及其實現(xiàn)

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

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

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

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

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

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

//為左孩子節(jié)點

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

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

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

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

采用先序遍歷遞歸算法查找值為x的節(jié)點。找到后返回其指針，否則返回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é)點LchildNode(p)和RchildNode(p)

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

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)

用括弧表示法輸出二叉樹。對于非空二叉樹b，先輸出其元素值，當存在左孩子節(jié)點或右孩子節(jié)點時，輸出一個“(”符號，然后遞歸處理左子樹，輸出一個“,”符號，遞歸處理右子樹，最后輸出一個“)”符號。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二叉樹遍歷的概念

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

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

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

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

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

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

}}2.中序遍歷過程中序遍歷二叉樹的過程是：

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

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

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

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

PreOrder(b->lchild);

PreOrder(b->rchild);}}ABCDEFGHK先序序列：^A形參T取值下層調(diào)用結束后返回到主調(diào)應該執(zhí)行的語句ABCDEHGKF^B445^C4^D4555^E45^G45^H45^K45^F45遞歸算法執(zhí)行時系統(tǒng)棧的變化遞歸算法執(zhí)行過程：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);//訪問根節(jié)點

InOrder(b->rchild);}}

后序遍歷遞歸算法：

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

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

}}思考題：

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

例7.5假設二叉樹采用二叉鏈存儲結構存儲，試設計一個算法，計算一棵給定二叉樹的所有節(jié)點個數(shù)。

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

f(b)=0 若b=NULL

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

例7.6假設二叉樹采用二叉鏈存儲結構存儲，試設計一個算法，計算一棵給定二叉樹的所有葉子節(jié)點個數(shù)。

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

f(b)=0 若b=NULL

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

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假設二叉樹采用二叉鏈存儲結構存儲，試設計一個算法，計算一棵給定二叉樹的所有單分支節(jié)點個數(shù)。

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

f(b)=0 若b=NULL

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

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é)點

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

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

例7.8假設二叉樹采用二叉鏈存儲結構存儲，試設計一個算法，計算一棵給定二叉樹中值為k的節(jié)點個數(shù)。

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

f(b,k)=0 當b=NULLf(b,k)=1+f(b->lchild,k)+f(b->rchild,k)當b->data=k時

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假設二叉樹采用二叉鏈存儲結構，設計一個算法把二叉樹b復制到二叉樹t中。

解：其遞歸模型如下：

f(b,t)

t=NULL 若b=NULL

f(b,t)

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

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; //復制一個根節(jié)點*t

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

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

}}

例7.10設二叉樹采用二叉鏈存儲結構，設計一個算法把二叉樹b的左、右子