第7章 樹形結構

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

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

7.7線索二叉樹本章小結7.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é)點寫在括號中并用逗號間隔來描述樹結構。下圖是樹的括號表示法。ABCDEFGJHIKLM思考題：樹的邏輯結構定義？適合表示什么類型的數(shù)據(jù)？7.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é)點的路徑上經過的所有節(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個，這與命題相同，故命題成立。性質3高度為h的m次樹至多有個節(jié)點。證明：由樹的性質2可知,第i層上最多節(jié)點數(shù)為mi-1（i=1,2,…,h），顯然當高度為h的m次樹（即度為m的樹）上每一層都達到最多節(jié)點數(shù)時，整個m次樹具有最多節(jié)點數(shù)，因此有：整個樹的最多節(jié)點數(shù)=每一層最多節(jié)點數(shù)之和=m0+m1+m2+…+mh-1=。性質4具有n個節(jié)點的m次樹的最小高度為logm(n(m-1)+1)。證明：設具有n個節(jié)點的m次樹的高度為h，若在該樹中前h-1層都是滿的，即每一層的節(jié)點數(shù)都等于mi-1個（1≤i≤h-1），第h層（即最后一層）的節(jié)點數(shù)可能滿，也可能不滿，則該樹具有最小的高度。其高度h可計算如下：m=3，h=3，最多節(jié)點情況m=3，h=3，最少節(jié)點情況根據(jù)樹的性質3可得： ＜n≤乘(m-1)后得： mh-1＜n(m-1)+1≤mh以m為底取對數(shù)后得：h-1＜logm(n(m-1)+1)≤h即 logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1因h只能取整數(shù)，所以

h=logm(n(m-1)+1)結論得證。例7.1含n個節(jié)點的三次樹的最小高度是多少？最大高度是多少？解：設含n個節(jié)點的（為完全三次樹時高度最?。┑娜螛涞淖钚「叨葹閔，則有：1+3+9+…+3h-2＜n≤1+3+9+…+3h-1(3h-1-1)/2＜n≤(3h-1)/23h-1＜2n+1≤3h即：h=log3(2n+1)

最大高度為n-2。…7.1.5樹的基本運算

樹的運算主要分為三大類：第一類，尋找滿足某種特定關系的節(jié)點，如尋找當前節(jié)點的雙親節(jié)點等；第二類，插入或刪除某個節(jié)點，如在樹的當前節(jié)點上插入一個新節(jié)點或刪除當前節(jié)點的第i個孩子節(jié)點等；第三類，遍歷樹中每個節(jié)點，這里著重介紹。

樹的遍歷運算是指按某種方式訪問樹中的每一個節(jié)點且每一個節(jié)點只被訪問一次。有以下三種遍歷方法：樹的遍歷先根遍歷后根遍歷層次遍歷注意：先根和后根遍歷算法都是遞歸的。先根遍歷:若樹不空，則先訪問根節(jié)點，然后依次先根遍歷各棵子樹。后根遍歷:若樹不空，則先依次后根遍歷各棵子樹，然后訪問根節(jié)點。按層次遍歷:若樹不空，則自上而下自左至右訪問樹中每個節(jié)點。ABCDEFGHJIK先根遍歷的頂點訪問次序：ABEFCDGHIJK后根遍歷的頂點訪問次序：EFBCIJKHGDA層次遍歷的頂點訪問次序：ABCDEFGHIJK7.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ù)。思考題：n個節(jié)點的m次樹有多少個空指針域？思考題：該存儲結構的優(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é)點都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。

下圖所示就是一棵滿二叉樹。可以對滿二叉樹的節(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求解二叉樹的節(jié)點個數(shù)問題：通常利用二叉樹的性質1，即n0=n2+1來求解這類問題，也常利用以下關系求解：n=n0+n1+n2度之和=n-1度之和=n1+2n2所以有：n=n1+2n2求解方法歸納

求解完全二叉樹的節(jié)點個數(shù)問題：完全二叉樹屬于二叉樹，也滿足二叉樹的性質1，即n0=n2+1。除此之外，完全二叉樹中一旦n確定，其樹形就確定了，可以計算出高度h以及n0、n1和n2。其中n1=0或1，當n為偶數(shù)時，n1=1，當n為奇數(shù)時，n1=0。其關系有：h=log2n+1或h=log2(n+1)求解方法歸納例7.2已知一棵完全二叉樹的第6層（設根為第1層）有8個葉節(jié)點，則該完全二叉樹的節(jié)點個數(shù)最多是

。A.39 B.52C.111 D.119注：本題為2009年全國考研題

求解滿二叉樹的節(jié)點個數(shù)問題：滿二叉樹是最嚴格的二叉樹，一旦n確定，其樹形就確定了，可以計算出高度h以及n0、n1和n2。其關系有：h=log2(n+1)n1=0n=2h-1n0=2h-1n2=2h-1-1求解方法歸納例：一棵滿二叉樹中共有n個節(jié)點，其中有m個葉子節(jié)點，高度為h，則

。 A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-1

性質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é)點。思考題：

性質4的特點？性質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é)點和相鄰的樹。ABCDEFGHII將森林轉換為二叉樹的過程2.二叉樹還原為森林、樹

步驟如下：（1）對于一棵二叉樹中任一節(jié)點k0，沿著k0的左孩子節(jié)點k1的右子樹方向搜索所有右孩子節(jié)點，即搜索節(jié)點序列k2,k3,…,km，其中ki+1為ki的右孩子節(jié)點（1≤i＜m），km沒有右孩子節(jié)點。（2）刪去k1,k2,…,km之間連線。（3）若k1有雙親節(jié)點k0，則連接k0與ki（2≤i≤m）。（4）將圖形規(guī)整化，使各節(jié)點按層次排列。將一棵二叉樹還原為樹的過程

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

。 A.16 B.15 C.7 D.17例7.4設一棵二叉樹是由森林轉換而來的，若森林中有n個非終端節(jié)點，則二叉樹中無右孩子的節(jié)點個數(shù)為

。A.n-1 B.n

C.n+1 D.n+2設計題：設計一棵二叉樹，表示夫妻、父子和兄弟關系。思考題：

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

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

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

ABD#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先序序列：ABCDEHGKF2.中序遍歷過程中序遍歷二叉樹的過程是：

中序遍歷左子樹；

訪問根節(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取值下層調用結束后返回到主調應該執(zhí)行的語句ABCDEHGKF^B445^C4^D4555^E45^G45^H45^K45^F45遞歸算法執(zhí)行時系統(tǒng)棧的變化遞歸算法執(zhí)行過程：中序遍歷的遞歸算法：

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=NULLf(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=NULLf(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=NULLf(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產生*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的左、右子樹進行交換。要求不破壞原二叉樹。

解：本題要求不破壞原有二叉樹，實際上就是建立一個新的二叉樹t，它交換了二叉樹b的左、右子樹。其遞歸模型如下：f(b,t)t=NULL 若b=NULLf(b,t)復制根節(jié)點*b產生*t節(jié)點; 其他情況f(b->lchild,t->rchild);f(b->rchild,t->lchild);voidSwap(BTNode*b,BTNode*&t){if(b==NULL)t=NULL;else{t=(BTNode*)malloc(sizeof(BTNode));t->data=b->data; //復制一個根節(jié)點*t

Swap(b->lchild,t->rchild); //遞歸交換左子樹

Swap(b->rchild,t->lchild); //遞歸交換右子樹}}例7.11假設二叉樹采用二叉鏈存儲結構存儲，試設計一個算法輸出一棵給定二叉樹的所有葉子節(jié)點。

解：輸出一棵二叉樹的所有葉子節(jié)點的遞歸模型f()如下：f(b)：不做任何事件 若b=NULLf(b)：輸出*b節(jié)點的data域若*b為葉子節(jié)點f(b)：f(b->lchild);f(b->rchild)其他情況voidDispLeaf(BTNode*b){if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); else {DispLeaf(b->lchild);

DispLeaf(b->rchild);}}}voidDispLeaf(BTNode*b){if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data);

DispLeaf(b->lchild);

DispLeaf(b->rchild);}}與先序遍歷算法完全相同，只是訪問的方式不同。例7.12假設二叉樹采用二叉鏈存儲結構，設計一個算法Level()求二叉樹中指定節(jié)點的層數(shù)。解：設Level(b,x,h)返回二叉鏈b中data值為x的節(jié)點的層數(shù)，其中h表示b所指節(jié)點的層數(shù)。b調用Level(b,x,1)返回x節(jié)點的層數(shù)。intLevel(BTNode*b,ElemTypex,inth)//找到*p節(jié)點后h為其層次,否則為0{if(b==NULL)return0;//空樹時返回0elseif(b->data==x)returnh;//找到節(jié)點時else{l=Level(b->lchild,x,h+1);//在左子樹中查找if(l==0)//左子樹中未找到時在右子樹中查找 returnLevel(b->rchild,x,h+1); elsereturnl;}}注意：基于先序遍歷算法思想。

例7.13假設二叉樹采用二叉鏈存儲結構,設計一個算法判斷兩棵二叉樹是否相似,所謂二叉樹t1和t2是相似的指的是t1和t2都是空的二叉樹；或者t1和t2的根節(jié)點是相似的,以及t1的左子樹和t2的左子樹是相似的且t1的右子樹與t2的右子樹是相似的。解：判斷兩棵二叉樹是否相似的遞歸模型f()如下： f(t1,t2)=true若t1=t2=NULL f(t1,t2)=false 若t1、t2之一為NULL,另一不為NULL f(t1,t2)=f(t1->lchild,t2->lchild)& 其他情況 f(t1->rchild,t2->rchild)對應的算法如下：intLike(BTNode*b1,BTNode*b2)//t1和t2兩棵二叉樹相似時返回1,否則返回0{intlike1,like2;if(b1==NULL&&b2==NULL)return1;elseif(b1==NULL||b2==NULL)return0;else{like1=Like(b1->lchild,b2->lchild);like2=Like(b1->rchild,b2->rchild);return(like1&like2);}}注意：基于后序遍歷算法思想。7.5.3二叉樹遍歷非遞歸算法

1.先序遍歷非遞歸算法1步驟如下：

if(當前b樹不空){根節(jié)點b進棧;while(棧不空){出棧節(jié)點p并訪問之;若*p節(jié)點有右孩子，將其右孩子進棧；若*p節(jié)點有左孩子，將其左孩子進棧；}}根左右bvoidPreOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;top++;St[top]=b;//根節(jié)點入棧while(top>-1) //棧不為空時循環(huán){p=St[top];top--;//退棧并訪問該節(jié)點 printf("%c",p->data);if(p->rchild!=NULL)//右孩子節(jié)點入棧 {top++;St[top]=p->rchild;}if(p->lchild!=NULL)//左孩子節(jié)點入棧 {top++;St[top]=p->lchild;}}}2.先序遍歷非遞歸算法2

if(當前b樹不空){p＝b;while(棧不空或者p!=NULL){while(p有左孩子){訪問p所指節(jié)點;將p進棧；p=p->lchild}if(棧不空){出棧p；p＝p->rchild;}}}先序遍歷ABCDEHGKFABCDEFGHK^A^B

^C^D^E^F^G^H^K先序序列：voidPreOrder2(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;p=b;while(top>-1||p!=NULL){while(p!=NULL)//掃描*p的所有左節(jié)點并進棧 {printf("%c",p->data);//訪問之top++;St[top]=p; p=p->lchild; }

if(top>-1) {p=St[top];top--; //出棧*p節(jié)點 p=p->rchild;//處理右子樹}}}2.中序遍歷非遞歸算法

步驟如下：

if(當前b樹不空){p＝b;while(棧不空或者p!=NULL){while(p有左孩子){將p進棧；p=p->lchild;}if(棧不空){出棧p并訪問之；p＝p->rchild;}}}左根右bpb的最左下節(jié)點說明：

（1）所有左下孩子進棧，體現(xiàn)先訪問左子樹的特點。（2）當所有左下孩子進棧后，棧頂節(jié)點p沒有左孩子（也就是沒有左子樹）或者其左子樹均已訪問，所以可以訪問p節(jié)點。（3）當訪問p節(jié)點后，轉向其右孩子，采用同樣的方式中序遍歷右子樹。中序遍歷ABCDEHGKFABCDEFGHK^A^B

^C^D^E^F^G^H^K中序序列：voidInOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;p=b;while(top>-1||p!=NULL){while(p!=NULL) //掃描*p的所有左節(jié)點并進棧 {top++;St[top]=p; p=p->lchild; } if(top>-1) {p=St[top];top--; //出棧*p節(jié)點printf("%c",p->data); //訪問之 p=p->rchild; //處理右子樹}}}找*b的最左下節(jié)點3.后序遍歷非遞歸算法步驟如下：

if(當前b樹不空){do{while(b!=NULL,b有左孩子,將進棧);出棧節(jié)點b;if(b的右子樹已訪問)則訪問b并退棧；elseb＝b->rchild;}while(棧不空);}左右根難點：如何判斷一個節(jié)點*b的右孩子節(jié)點已訪問過。方法：用p保存剛剛訪問過的節(jié)點（初值為NULL），若b->rchild==p成立，說明*b的左右子樹均已訪問，現(xiàn)在應訪問*b。原因：在后序遍歷中，*b的右孩子節(jié)點一定剛好在*b之前訪問。左右根pb后序遍歷ABCDEHGKFABCDEFGHK^A^B^C^D^E^F^G^H^K后序序列：voidPostOrder1(BTNode*b){BTNode*St[MaxSize];BTNode*p;intflag,top=-1;//棧指針置初值do{while(b!=NULL)//將*b的所有左節(jié)點進棧{top++;St[top]=b; b=b->lchild; } p=NULL; //p指向棧頂節(jié)點的前一個已訪問的節(jié)點 flag=1; //表示*b的左子樹已訪問或為空找最左下節(jié)點while(top!=-1&&flag==1){b=St[top];//取出當前的棧頂元素 if(b->rchild==p) {printf("%c",b->data);//訪問*b節(jié)點 top--;p=b; //p指向則被訪問的節(jié)點 } else{b=b->rchild; //b指向右孩子節(jié)點flag=0; ///b的左子樹未訪問}}}while(top!=-1);}b的右孩子不存在或已訪問過

從上述過程可知，棧中保存的是當前節(jié)點*b的所有祖先節(jié)點（均未訪問過）。例如，求一個節(jié)點的所有祖先節(jié)點。

例7.14假設二叉樹采用二叉鏈存儲結構，設計一個算法輸出從根節(jié)點到每個葉子節(jié)點的路徑之逆（因為樹中路徑是從根節(jié)點到其他節(jié)點的節(jié)點序列，這里就是求從葉子節(jié)點及其雙親節(jié)點、該雙親節(jié)點的雙親節(jié)點，直到根節(jié)點的序列，或者說求葉子節(jié)點及其所有祖先節(jié)點的序列）。

解：本例采用后序遍歷非遞歸算法。voidAllPath1(BTNode*b){BTNode*St[MaxSize];BTNode*p;intflag,i,top=-1; //棧指針置初值if(b!=NULL){do {while(b!=NULL)//將*b的所有左節(jié)點進棧 {top++; St[top]=b; b=b->lchild; } p=NULL; flag=1;while(top!=-1&&flag){b=St[top]; //取出當前的棧頂元素 if(b->rchild==p) {if(b->lchild==NULL&&b->rchild==NULL) {//若為葉子節(jié)點,輸出棧中所有節(jié)點值 for(i=top;i>0;i--) printf("%c->",St[i]->data); printf("%c\n",St[0]->data); } top--; p=b; //p指向剛訪問過的節(jié)點 } else {b=b->rchild; //b指向右孩子節(jié)點 flag=0; } }}while(top!=-1);printf("\n");}}7.5.4層次遍歷算法在進行層次遍歷時，對某一層的節(jié)點訪問完后，再按照它們的訪問次序對各個節(jié)點的左、右孩子順序訪問，這樣一層一層進行，先訪問的節(jié)點其左、右孩子也要先訪問，這樣與隊列的操作原則比較吻合。因此層次遍歷算法采用一個環(huán)形隊列qu來實現(xiàn)。層次遍歷過程是：先將根節(jié)點進隊，在隊不空時循環(huán)：從隊列中出列一個節(jié)點*p，訪問它；若它有左孩子節(jié)點，將左孩子節(jié)點進隊；若它有左孩子節(jié)點，將左孩子節(jié)點進隊。如此操作直到隊空為止。對應的算法如下：voidLevelOrder(BTNode*b){BTNode*p;BTNode*qu[MaxSize]; //定義環(huán)形隊列,存放節(jié)點指針intfront,rear; //定義隊頭和隊尾指針front=rear=-1; //置隊列為空隊列rear++;qu[rear]=b; //根節(jié)點指針進入隊列while(front!=rear) //隊列不為空{front=(front+1)%MaxSize; p=qu[front]; //隊頭出隊列 printf("%c",p->data); //訪問節(jié)點 if(p->lchild!=NULL) //有左孩子時將其進隊 {rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) //有右孩子時將其進隊 {rear=(rear+1)%MaxSize; qu[rear]=p->rchild; }}}例7.15采用層次遍歷方法設計上例的算法。

解：這里設計的隊列為非環(huán)形順序隊列qu（類似于第3章3.2.4小節(jié)中求解迷宮問題時使用的隊列），將所有已訪問過的節(jié)點指針進隊，并在隊列中保存雙親節(jié)點的位置。當找到一個葉子節(jié)點時，在隊列中通過雙親節(jié)點的位置輸出根節(jié)點到該葉子節(jié)點的路徑之逆。對應的算法如下：voidAllPath2(BTNode*b){structsnode{BTNode*node; //存放當前節(jié)點指針 intparent; //存放雙親節(jié)點在隊列中的位置}qu[MaxSize]; //定義非環(huán)形隊列BTNode*q;intfront,rear,p; //定義隊頭和隊尾指針front=rear=-1; //置隊列為空隊列rear++;qu[rear].node=b; //根節(jié)點指針進入隊列qu[rear].parent=-1; //根節(jié)點沒有雙親節(jié)點while(front!=rear) //隊列不為空{front++; //front是當前節(jié)點*q在qu中的位置 q=qu[front].node; //隊頭出隊列,該節(jié)點指針仍在qu中

if(q->lchild==NULL&&q->rchild==NULL) {p=front; //輸出*q到根節(jié)點的路徑序列 while(qu[p].parent!=-1) {printf("%c->",qu[p].node->data); p=qu[p].parent; } printf("%c\n",qu[p].node->data); } if(q->lchild!=NULL) //*q節(jié)點有左孩子時將其進列 {rear++; qu[rear].node=q->lchild; qu[rear].parent=front;//*q的雙親位置為front } if(q->rchild!=NULL) //*q節(jié)點有右孩子時將其進列 {rear++; qu[rear].node=q->rchild; qu[rear].parent=front;//*q的雙親位置為front }}}思考題：求一個節(jié)點的祖先節(jié)點有哪些方法？7.6二叉樹的構造

同一棵二叉樹具有唯一先序序列、中序序列和后序序列。但不同的二叉樹可能具有相同的先序序列、中序序列和后序序列。

給定先序、中序和后序遍歷序列可以唯一確定這棵二叉樹的樹形。僅由一個先序序列（或中序序列、后序序列），無法確定這棵二叉樹的樹形。思考：給定先序、中序和后序遍歷序列中任意兩個,是否可以唯一確定這棵二叉樹的樹形？命題成立否？

同時給定一棵二叉樹的先序序列和中序序列就能唯一確定這棵二叉樹。

同時給定一棵二叉樹的中序序列和后序序列就能唯一確定這棵二叉樹。

同時給定一棵二叉樹的先序序列和后序序列就能唯一確定這棵二叉樹。

定理7.1：任何n（n≥0）個不同節(jié)點的二又樹，都可由它的中序序列和先序序列唯一地確定。采用數(shù)學歸納法證明。當n=0時，二叉樹為空，結論正確。假設節(jié)點數(shù)小于n的任何二叉樹，都可以由其先序序列和中序序列唯一地確定。已知某棵二叉樹具有n（n＞0）個不同節(jié)點，其先序序列是a0a1…an-1；中序序列是b0b1…bk-1bkbk+1…bn-1。因為在先序遍歷過程中，訪問根節(jié)點后，緊跟著遍歷左子樹，最后再遍歷右子樹。所以a0必定是二叉樹的根節(jié)點，而且a0必然在中序序列中出現(xiàn)。也就是說，在中序序列中必有某個bk（0≤k≤n-1）就是根節(jié)點a0。由于bk是根節(jié)點,而在中序遍歷過程中,先遍歷左子樹,再訪問根節(jié)點,最后再遍歷右子樹。所以在中序序列中,b0b1…bk-1必是根節(jié)點bk（也就是a0）左子樹的中序序列,即bk的左子樹有k個節(jié)點（注意k=0表示節(jié)點bk沒有左子樹）。而bk+1…bn-1必是根節(jié)點bk（也就是a0）右子樹的中序序列,即bk的右子樹有n-k-1個節(jié)點（注意k=n-1表示節(jié)點bk沒有右子樹）。。另外,在先序序列中,緊跟在根節(jié)點a0之后的k個節(jié)點a1…ak就是左子樹的先序序列,ak+1…an-1這n-k-1就是右子樹的先序序列。根據(jù)歸納假設,由于子先序序列a1…ak和子中序序列b0b1…bk-1可以唯一地確定根節(jié)點a0的左子樹,而子先序序列ak+1…an-1和子中序序列bk+1…bn-1可以唯一地確定根節(jié)點a0的右子樹。綜上所述，這棵二叉樹的根節(jié)點己經確定，而且其左、右子樹都唯一地確定了，所以整個二叉樹也就唯一地確定了。

例如,已知先序序列為ABDGCEF,中序序列為DGBAECF,則構造二叉樹的過程如下所示。

根節(jié)點：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根節(jié)點：B左先序:DG左中序:DG右先序:空右中序:空根節(jié)點：D左先序:空左中序:空右先序:G右中序:G根節(jié)點：G左先序:空左中序:空右先序:空右中序:空根節(jié)點：C左先序:E左中序:E右先序:F右中序:F根節(jié)點：E左先序:空左中序:空右先序:空右中序:空根節(jié)點：F左先序:空左中序:空右先序:空右中序:空由上述定理得到以下構造二叉樹的算法：BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n<=0)returnNULL;s=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建節(jié)點s->data=*pre;for(p=in;p<in+n;p++)//在中序中找為*ppos的位置k if(*p==*pre) break;k=p-in;s->lchild=CreateBT1(pre+1,in,k); //構造左子樹s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);returns;}

先序遍歷的思路定理7.2：任何n（n＞0）個不同節(jié)點的二又樹，都可由它的中序序列和后序序列唯一地確定。同樣采用數(shù)學歸納法證明。

實際上，對于根節(jié)點ak的左右子樹，在確定左右子樹的子中序序列后，不需要確定左右子樹的整個子后序序列，只需確定子中序序列中全部字符在后序序列中最右邊的那個字符即可，因為這個字符就是子樹的根節(jié)點。

例如,已知中序序列為DGBAECF，后序序列為GDBEFCA。對應的構造二叉樹的過程如下所示。根節(jié)點：A左中序:DGB左根:B右中序:ECF右根:C根節(jié)點：B左中序:DG左根:D右中序:空右根:空根節(jié)點：D左中序:空左根:空右中序:G右根:G根節(jié)點：G左中序:空左根:空右中序:空右根:空根節(jié)點：C左中序:E左根:E右中序:F右根:F根節(jié)點：E左中序:空左根:空右中序:空右根:空根節(jié)點：F左中序:空左根:空右中序:空右根:空由上述定理得到以下構造二叉樹的算法：BTNode*CreateBT2(char*post,char*in,intn,intm){BTNode*s;char*p,*q,*maxp;intmaxpost,maxin,k;if(n<=0)returnNULL;maxpost=-1;for(p=in;p<in+n;p++)//求in在post中最右邊的字符

for(q=post;q<post+m;q++)

//在in中用maxp指向這個字符,用maxin標識它在in中的下標 if(*p==*q) {k=q-post; if(k>maxpost) {maxpost=k;maxp=p;maxin=p-in;}

}

s=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建二叉樹節(jié)點*ss->data=post[maxpost];s->lchild=CreateBT2(post,in,maxin,m);