數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）課件 第6章樹和二叉樹(上)

第6章樹和二叉樹6.1樹6.2二叉樹6.3遞歸算法設(shè)計(jì)方法6.4二叉樹的基本運(yùn)算算法6.5二叉樹的遍歷6.6二叉樹的構(gòu)造6.7二叉樹與樹之間的轉(zhuǎn)換6.8線索二叉樹6.9哈夫曼樹第6章樹和二叉樹1/1156.1樹6.1.1樹的定義從數(shù)據(jù)結(jié)構(gòu)角度看，樹包含n（n≥0）個(gè)結(jié)點(diǎn)，當(dāng)n=0時(shí)，稱為空樹；非空樹的定義如下：

T=(D，R)其中，D為樹中結(jié)點(diǎn)的有限集合，關(guān)系R滿足以下條件：有且僅有一個(gè)結(jié)點(diǎn)d0∈D，它對(duì)于關(guān)系R來說沒有前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)d0稱作樹的根結(jié)點(diǎn)。除根結(jié)點(diǎn)d0外，D中的每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，但可以有多個(gè)后繼結(jié)點(diǎn)。D中可以有多個(gè)終端結(jié)點(diǎn)。6.1樹2/115

【例6.1】

有一棵樹T=(D，R)，其中

D={A，B，C，D，E，F(xiàn)，G，H},

R={r}

r={<A,B>，<A,C>，<A,D>，<C,E>，<C,F>，<D,G>，<E,H>}畫出其邏輯結(jié)構(gòu)圖。6.1樹3/115

A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：

T1={B}，T2={C，E，F(xiàn)，H}，T3={D，G}。T1、T2、T3都是根結(jié)點(diǎn)A的子樹，且各自本身也是一棵樹。說明：樹中結(jié)點(diǎn)之間的關(guān)系應(yīng)為有向關(guān)系，在上圖中，結(jié)點(diǎn)之間的連線即分支線都是有向的，默認(rèn)箭頭向下的。ABCDEFHG6.1樹4/1156.1.2樹的邏輯結(jié)構(gòu)表示樹形表示法。這是樹的最基本的表示，使用一棵倒置的樹表示樹結(jié)構(gòu)，非常直觀和形象。ABCDEFHG6.1樹5/115文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。ABCDEFHG6.1樹6/115凹入表示法。使用線段的伸縮關(guān)系描述樹結(jié)構(gòu)。ABCDEFHG6.1樹7/115括號(hào)表示法。將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)分隔。A(B,C(E(H),F),D(G))ABCDEFHG6.1樹8/1156.1.3樹的基本術(shù)語(yǔ)度為3度為1結(jié)點(diǎn)的度。樹中每個(gè)結(jié)點(diǎn)具有的子樹數(shù)或者后繼結(jié)點(diǎn)數(shù)稱為該結(jié)點(diǎn)的度。ABCDEFHG6.1樹9/115樹的度。樹中所有結(jié)點(diǎn)的度的最大值稱之為樹的度。樹的度為3ABCDEFHG6.1樹10/115分支結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。度為1的結(jié)點(diǎn)稱為單分支結(jié)點(diǎn)，度為2的結(jié)點(diǎn)稱為雙分支結(jié)點(diǎn)，依次類推。ABCDEFHGA、C、D、E為分支結(jié)點(diǎn)6.1樹11/115葉子結(jié)點(diǎn)（或葉結(jié)點(diǎn)）。度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。ABCDEFHGB、H、F、G為葉子結(jié)點(diǎn)6.1樹12/115孩子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的后繼稱之為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。結(jié)點(diǎn)A的孩子結(jié)點(diǎn)為B、C和DABCDEFHG6.1樹13/115雙親結(jié)點(diǎn)（或父親結(jié)點(diǎn)）。一個(gè)結(jié)點(diǎn)稱為其后繼結(jié)點(diǎn)的雙親結(jié)點(diǎn)。結(jié)點(diǎn)E和F的雙親結(jié)點(diǎn)均為CABCDEFHG6.1樹14/115子孫結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹中除該結(jié)點(diǎn)外的所有結(jié)點(diǎn)稱之為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。ABCDEFHG結(jié)點(diǎn)C結(jié)點(diǎn)的子孫結(jié)點(diǎn)為E、F和H6.1樹15/115祖先結(jié)點(diǎn)。從樹根結(jié)點(diǎn)到達(dá)某個(gè)結(jié)點(diǎn)的路徑上通過的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)（不含該結(jié)點(diǎn)自身）。ABCDEFHG結(jié)點(diǎn)F的祖先結(jié)點(diǎn)為A、C6.1樹16/115兄弟結(jié)點(diǎn)。具有同一雙親的結(jié)點(diǎn)互相稱之為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)E和F是兄弟結(jié)點(diǎn)ABCDEFHG6.1樹17/115結(jié)點(diǎn)層次。樹具有一種層次結(jié)構(gòu)，根結(jié)點(diǎn)為第一層，其孩子結(jié)點(diǎn)為第二層，如此類推得到每個(gè)結(jié)點(diǎn)的層次。1234ABCDEFHG6.1樹18/115樹的高度。樹中結(jié)點(diǎn)的最大層次稱為樹的高度或深度。1234ABCDEFHG高度是46.1樹19/115森林。零棵或多棵互不相交的樹的集合稱為森林。ABCDEFHG4棵樹構(gòu)成的森林6.1樹20/115性質(zhì)1：

樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。度之和＝分支數(shù)分支數(shù)=n-1所以，n=度之和+16.1.4樹的性質(zhì)6.1樹ABCDEFHGn=8度之和＝3+2+1+1=7分支數(shù)=7n=度之和+121/115性質(zhì)2：度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）。6.1樹22/115

推廣：當(dāng)一棵m次樹的第i層有mi-1個(gè)結(jié)點(diǎn)（i≥1）時(shí)，稱該層是滿的，若一棵m次樹的所有葉子結(jié)點(diǎn)在同一層，并且每一層都是滿的，稱為滿m次樹。顯然，滿m次樹是所有相同高度的m次樹中結(jié)點(diǎn)總數(shù)最多的樹。也可以說，對(duì)于n個(gè)結(jié)點(diǎn)，構(gòu)造的m次樹為滿m次樹或者接近滿m次樹，此時(shí)樹的高度最小。6.1樹23/115性質(zhì)3：

高度為h的m次樹至多有個(gè)結(jié)點(diǎn)。6.1樹24/115

【例6.1】若一棵三次樹中度為3的結(jié)點(diǎn)為2個(gè)，度為2的結(jié)點(diǎn)為1個(gè)，度為1的結(jié)點(diǎn)為2個(gè)，則該三次樹中總的結(jié)點(diǎn)個(gè)數(shù)和度為0的結(jié)點(diǎn)個(gè)數(shù)分別是多少？6.1樹25/115

設(shè)該三次樹中總結(jié)點(diǎn)個(gè)數(shù)、度為0的結(jié)點(diǎn)個(gè)數(shù)、度為1的結(jié)點(diǎn)個(gè)數(shù)、度為2的結(jié)點(diǎn)個(gè)數(shù)和度為3的結(jié)點(diǎn)個(gè)數(shù)分別為n、n0、n1、n2和n3。

顯然，每個(gè)度為i的結(jié)點(diǎn)在所有結(jié)點(diǎn)的度數(shù)之和中貢獻(xiàn)i個(gè)度。依題意有：n1=2，n2=1，n3=2。由樹的性質(zhì)1可知

n=所有結(jié)點(diǎn)的度數(shù)之和+1

=0×n0+1×n1+2×n2+3×n3+1=1×2+2×1+3×2+1=11又因?yàn)閚=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以該三次樹中總的結(jié)點(diǎn)個(gè)數(shù)和度為0的結(jié)點(diǎn)個(gè)數(shù)分別是11和6。6.1樹26/1156.1.5樹的基本運(yùn)算樹的運(yùn)算主要分為三大類：查找滿足某種特定關(guān)系的結(jié)點(diǎn)，如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；插入或刪除某個(gè)結(jié)點(diǎn)，如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等；遍歷樹中結(jié)點(diǎn)。6.1樹27/115

樹的遍歷運(yùn)算是指按某種方式訪問樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問一次。

有以下三種遍歷方法：樹的遍歷

先根遍歷后根遍歷層次遍歷注意：先根和后根遍歷算法都是遞歸的。6.1樹28/115先根遍歷:若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后根遍歷:若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。層次遍歷:若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。6.1樹29/115ABCDEFGHJIK先根遍歷的頂點(diǎn)訪問次序：ABEFCDGHIJK后根遍歷的頂點(diǎn)訪問次序：EFBCIJKHGDA層次遍歷的頂點(diǎn)訪問次序：ABCDEFGHIJK6.1樹30/1156.1.6樹的存儲(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)的位置。1.雙親存儲(chǔ)結(jié)構(gòu)ABCDEFHG位置dataparent0A-11B02C03D04E25F26G37H46.1樹31/115孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹的度（即樹中所有結(jié)點(diǎn)度的最大值）設(shè)計(jì)結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針域個(gè)數(shù)。2.孩子鏈存儲(chǔ)結(jié)構(gòu)ABCDEFHG6.1樹32/115孩子兄弟鏈存儲(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)指針域。3.孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)ABCDEFHG6.1樹33/1156.2二叉樹6.2.1二叉樹的定義二叉樹的遞歸定義：二叉樹或者是一棵空樹。或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱做根結(jié)點(diǎn)的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。6.2二叉樹34/115注意：二叉樹與度為2的樹是不同的。度為2的樹至少有3個(gè)結(jié)點(diǎn)，而二叉樹的結(jié)點(diǎn)數(shù)可以為0。度為2的樹不區(qū)分子樹的次序，而二叉樹中的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，且必須要區(qū)分左右子樹，即使在結(jié)點(diǎn)只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。6.2二叉樹35/115歸納起來，二叉樹的5種形態(tài)：?(a)空二叉樹(b)只有一個(gè)根結(jié)點(diǎn)的二叉樹(c)右子樹為空的二叉樹(d)左子樹為空的二叉樹(e)左、右子樹非空的二叉樹6.2二叉樹36/115

【例6.3】給出由3個(gè)結(jié)點(diǎn)A、B和C構(gòu)成的所有形態(tài)的二叉樹（不考察結(jié)點(diǎn)值的差異）。解：含有3個(gè)結(jié)點(diǎn)A、B和C的所有形態(tài)的二叉樹：ABCABCABCABCABC6.2二叉樹37/115性質(zhì)1

非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即n0=n2+1。約定：二叉樹上葉結(jié)點(diǎn)數(shù)為n0，單分支結(jié)點(diǎn)數(shù)為n1，雙分支結(jié)點(diǎn)數(shù)為n2，6.2.2二叉樹性質(zhì)總結(jié)點(diǎn)數(shù)n=n0+n1+n2。一個(gè)度為1的結(jié)點(diǎn)貢獻(xiàn)1個(gè)度，一個(gè)度為2的結(jié)點(diǎn)貢獻(xiàn)2個(gè)度，所以總的度數(shù)=n1+2n2?？偟亩葦?shù)=總分支數(shù)=n-1。則n1+2n2=n0+n1+n2-1，求出n0=n2+1。證明：6.2二叉樹38/115

【例6.4】一棵二叉樹中總結(jié)點(diǎn)個(gè)數(shù)為200，其中單分支結(jié)點(diǎn)個(gè)數(shù)為19，求其葉子結(jié)點(diǎn)個(gè)數(shù)。

n=200，n1=19。又n=n0+n1+n2，由性質(zhì)1得，n2=n0-1，所以有：n=2n0-1+n1，即n0=(n-n1+1)/2=91。所以這樣的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)為91。6.2二叉樹39/115性質(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可推出。6.2二叉樹40/115滿二叉樹：在一棵二叉樹中，當(dāng)?shù)趇層的結(jié)點(diǎn)數(shù)為2i-1個(gè)時(shí)，則稱此層的結(jié)點(diǎn)數(shù)是滿的，當(dāng)一棵二叉樹中的每一層都滿時(shí)，且葉子結(jié)點(diǎn)在同一層上，則稱此樹為滿二叉樹。滿二叉樹特性：除葉子結(jié)點(diǎn)以外的其他結(jié)點(diǎn)的度皆為2。

6.2二叉樹41/115高度為h的滿二叉樹中的結(jié)點(diǎn)數(shù)為2h-1個(gè)。層序編號(hào)：從根結(jié)點(diǎn)為1開始，按照層次從小到大、同一層從左到右的次序順序編號(hào)。可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。一棵高度為4的滿二叉樹，其結(jié)點(diǎn)數(shù)為24-1=15。圖中每個(gè)結(jié)點(diǎn)旁的編號(hào)是層序編號(hào)ABDHIEJKCFLMGNO1248951011361213714156.2二叉樹42/115完全二叉樹：在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)，則稱此樹為完全二叉樹。完全二叉樹特性：二叉樹中至多只有最下邊兩層結(jié)點(diǎn)的度數(shù)小于2。高度為h的完全二叉樹若按層序編號(hào),它與高度為h的滿二叉樹中結(jié)點(diǎn)的編號(hào)一一對(duì)應(yīng)。6.2二叉樹43/115一棵完全二叉樹，它與等高度的滿二叉樹相比，在最后一層的右邊缺少了3個(gè)結(jié)點(diǎn)。ABDHIEJKCFLG1248951011361276.2二叉樹44/115

性質(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)。6.2二叉樹45/115

（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，也就是說，當(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+16.2二叉樹46/115【例6.5】一棵完全二叉樹中總結(jié)點(diǎn)個(gè)數(shù)為200，求其葉子結(jié)點(diǎn)個(gè)數(shù)。

n=200，由于n為偶數(shù)，所以n1=1。

又n=n0+n1+n2，由性質(zhì)1得n2=n0-1，所以有：n=2n0-1+n1，n0=(n-n1+1)/2=100。這樣的完全二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)為100。6.2二叉樹47/1156.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)1．順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)一棵二叉樹時(shí)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。由二叉樹的性質(zhì)4可知，對(duì)于完全二叉樹（或滿二叉樹），樹中結(jié)點(diǎn)層序編號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，所以可以用一維數(shù)組按從上到下、從左到右的順序存儲(chǔ)樹中所有結(jié)點(diǎn)值，通過數(shù)組元素的下標(biāo)關(guān)系反映完全二叉樹或滿二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系。6.2二叉樹48/115一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)1234567891011121314…ABCDEFGHIJKL###位置dataABDHIEJKCFLG1248951011361276.2二叉樹49/115一般的二叉樹的順序存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)：ABDEGHCFKABDEGHCFK1248951011361271413增添空結(jié)點(diǎn)補(bǔ)齊為一棵完全二叉樹并對(duì)所有結(jié)點(diǎn)進(jìn)行編號(hào)6.2二叉樹50/115ABDEGHCFK12489510113612714131234567891011121314…ABCDE#F##GH##K#位置data僅保留實(shí)際存在的結(jié)點(diǎn)值，其他為空6.2二叉樹51/115二叉樹順序存儲(chǔ)結(jié)構(gòu)的類型定義如下：typedefElemTypeSqBinTree[MaxSize];其中，ElemType為二叉樹中結(jié)點(diǎn)的數(shù)據(jù)值類型，MaxSize為順序表的最大長(zhǎng)度。為了方便運(yùn)算，通常將下標(biāo)為0的位置空著，值為'#'的結(jié)點(diǎn)為空結(jié)點(diǎn)。

6.2二叉樹52/115完全二叉樹或滿二叉樹采用順序存儲(chǔ)結(jié)構(gòu)比較合適，既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)確定結(jié)點(diǎn)在二叉樹中的位置以及結(jié)點(diǎn)之間的關(guān)系。對(duì)于一般二叉樹，如果它接近于完全二叉樹形態(tài)，需要增加的空結(jié)點(diǎn)個(gè)數(shù)不多，也可適合采用順序存儲(chǔ)結(jié)構(gòu)。6.2二叉樹53/115如果需要增加很多空結(jié)點(diǎn)才能將一棵二叉樹改造成為一棵完全二叉樹，采用順序存儲(chǔ)結(jié)構(gòu)會(huì)造成空間的大量浪費(fèi)，這時(shí)不宜用順序存儲(chǔ)結(jié)構(gòu)。h=4MazSize=24-1=15空間利用率=4/15=27%6.2二叉樹54/1152．二叉鏈存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹，通常采用二叉鏈表示。鏈表中的每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，分別指向?qū)?yīng)結(jié)點(diǎn)的左孩子和右孩子（注意在樹的孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的兩個(gè)指針分別指向?qū)?yīng)結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟）。6.2二叉樹55/115在二叉鏈存儲(chǔ)中，結(jié)點(diǎn)的類型聲明如下：typedefstructtnode{ElemTypedata;

//數(shù)據(jù)域

structtnode*lchild,*rchild; //指針域}BTNode;data表示數(shù)據(jù)域，用于存儲(chǔ)放入結(jié)點(diǎn)值（默認(rèn)情況下為單個(gè)字母）。lchild和rchild分別表示左指針域和右指針域，分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)（即左、右子樹的根結(jié)點(diǎn)）的存儲(chǔ)地址。當(dāng)某結(jié)點(diǎn)不存在左或右孩子時(shí)，其lchild或rchild指針域取特殊值NULL。6.2二叉樹56/115ABDEGHCFKA

B

∧D∧

E

∧G∧

∧H∧

∧C

F∧

∧K∧

b6.2二叉樹57/1156.3遞歸算法設(shè)計(jì)方法6.3.1什么是遞歸在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱之為遞歸。若調(diào)用自身，稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q，而q又調(diào)用p，稱之為間接遞歸。后面主要介紹直接遞歸。6.3遞歸算法設(shè)計(jì)方法58/115例如，有以下遞歸函數(shù)：對(duì)應(yīng)的求解f(n)的遞歸算法fun()如下：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)

n≥3intfun(inti){

if(i==1||i==2) return(1);

else return(fun(i-1)+fun(i-2));}6.3遞歸算法設(shè)計(jì)方法59/115計(jì)算fun(5)的過程求解fun(5)fun(3)=fun(2)+fun(1)n=3返回22fun(3)=fun(2)+fun(1)n=3fun(4)=fun(3)+fun(2)n=43返回3fun(5)=fun(4)+fun(3)n=5返回22返回11返回11返回11返回11返回11返回5=56.3遞歸算法設(shè)計(jì)方法60/115遞歸樹fun(5)fun(4)fun(3)fun(2)fun(1)fun(2)fun(3)fun(2)fun(1)6.3遞歸算法設(shè)計(jì)方法61/115一般地，遞歸模型由兩部分組成，一部分為遞歸出口，它給出了遞歸的終止條件。另一部分為遞歸體，它確定遞歸求解時(shí)的遞推關(guān)系。例如，前面例子中的f(1)=1和f(2)=1就是遞歸出口；f(n)=f(n-1)+f(n-2)就是遞歸體。6.3遞歸算法設(shè)計(jì)方法62/115遞歸算法求解過程的特征：先將不能直接求解的問題轉(zhuǎn)換成若干個(gè)相似的小問題，通過分別求解各子問題，最后獲得整個(gè)問題的解。當(dāng)這些子問題不能直接求解時(shí)，還可以再將它們轉(zhuǎn)換成若干個(gè)更小的子問題，如此反復(fù)進(jìn)行，直到遇到遞歸出口為止。這種自上而下將問題分解、求解，再自上而下引用、合并，求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計(jì)方法。6.3遞歸算法設(shè)計(jì)方法63/1156.3.2遞歸算法設(shè)計(jì)一般方法遞歸算法的設(shè)計(jì)方法是，先確定對(duì)應(yīng)的遞歸模型，再將其轉(zhuǎn)換為遞歸算法。其核心思想是把問題簡(jiǎn)化分解為幾個(gè)子問題，其中子問題的形式和算法與原問題算法相似，只是比原來簡(jiǎn)化。6.3遞歸算法設(shè)計(jì)方法64/115獲取求解問題的遞歸模型的一般步驟對(duì)原問題f(s)進(jìn)行分析，假設(shè)出合理的“小問題”f(s')（與數(shù)學(xué)歸納法中假設(shè)n=k-1時(shí)等式成立相似）；假設(shè)f(s')是可解的，在此基礎(chǔ)上確定f(s)的解，即給出f(s)與f(s')之間的關(guān)系（與數(shù)學(xué)歸納法中求證n=k時(shí)等式成立的過程相似）；確定一個(gè)特定情況（如f(1)或f(0)）的解，由此作為遞歸出口（與數(shù)學(xué)歸納法中求證n=1或時(shí)n=0式成立相似）。6.3遞歸算法設(shè)計(jì)方法65/115【例6.7】設(shè)計(jì)一個(gè)遞歸算法求一個(gè)整數(shù)數(shù)組中所有元素之和。

相應(yīng)的遞歸算法如下：f(1)=a[0]f(i)=f(i-1)+a[i-1]intfun(inta[],inti){if(i==1)returna[0];

elsereturn(fun(a,i-1)+a[i-1]);}6.3遞歸算法設(shè)計(jì)方法設(shè)f(i)為整數(shù)數(shù)組a中a[0]～a[i-1]這i個(gè)元素之和，這是原問題。

小問題為f(i-1)，它為a[0]～a[i-2]這i-1個(gè)元素之和。

假設(shè)f(i-1)已求出，顯然有f(i)=f(i-1)+a[i-1]，另外，f[1]=a[0]。對(duì)應(yīng)的遞歸模型如下：66/115

【例6.8】對(duì)于不帶頭結(jié)點(diǎn)的非空單鏈表L（結(jié)點(diǎn)類型用SLinkNode表示），其結(jié)點(diǎn)值均為整數(shù)，設(shè)計(jì)以下遞歸算法：（1）求最大的結(jié)點(diǎn)值；（2）求最小的結(jié)點(diǎn)值；（3）正向輸出所有結(jié)點(diǎn)值；（4）反向輸出所有結(jié)點(diǎn)值。a1a2an∧…LL->nextf(L->next)f(L)6.3遞歸算法設(shè)計(jì)方法67/115

（1）設(shè)f1(L)計(jì)算單鏈表L中最大結(jié)點(diǎn)值，這是原問題，小問題為f1(L->next)計(jì)算以單鏈表L->next中最大結(jié)點(diǎn)值。假設(shè)f1(L->next)已計(jì)算出來，顯然有：

f1(L)=max(L->data，f1(L->next))；

當(dāng)單鏈表L中只有一個(gè)結(jié)點(diǎn)時(shí)有：f1(L)=L->data。a1a2an∧…LL->nextf(L->next)f(L)遞歸模型f1(L)=L->data

當(dāng)L中只有一個(gè)結(jié)點(diǎn)時(shí)f1(L)=max{L->data，f1(L->next)}

其他情況6.3遞歸算法設(shè)計(jì)方法68/115intf1(SLinkNode*L){intm;

if(L->next==NULL)returnL->data;else

{m=f1(L->next); //遞歸求小問題的解

if(m>L->data)returnm;

elsereturnL->data;

}}f1(L)=L->data

當(dāng)L中只有一個(gè)結(jié)點(diǎn)時(shí)f1(L)=max{L->data，f1(L->next)}

其他情況6.3遞歸算法設(shè)計(jì)方法69/115（2）分析同（1）小題。對(duì)應(yīng)的遞歸算法如下：intf2(SLinkNode*L){intm;

if(L->next==NULL) returnL->data;

else

{m=f2(L->next); //遞歸求小問題的解

if(m<L->data)returnm;

elsereturnL->data;

}}a1a2an∧…LL->nextf(L->next)f(L)6.3遞歸算法設(shè)計(jì)方法70/115

（3）設(shè)f3(L)正向輸出單鏈表L的所有結(jié)點(diǎn)值，這是原問題。則小問題就是f3(L->next)，它正向輸出單鏈表L->next的所有結(jié)點(diǎn)值。

假設(shè)f3(L->next)已輸出，顯然f3(L)等價(jià)于先輸出L->data值，再調(diào)用f3(L->next))。當(dāng)單鏈表L為空時(shí)，不做任何輸出。a1a2an∧…LL->nextf(L->next)f(L)6.3遞歸算法設(shè)計(jì)方法71/115對(duì)應(yīng)的遞歸模型如下：f3(L)

不做任何事情 當(dāng)L==NULLf3(L)

輸出L->data;f3(L->next)) 其他情況voidf3(SLinkNode*L){if(L!=NULL)

{ printf("%d",L->data);

f3(L->next);

}}其中“

”表示等價(jià)關(guān)系。6.3遞歸算法設(shè)計(jì)方法72/115（4）分析同（3）小題。對(duì)應(yīng)的遞歸算法如下：voidf4(SLinkNode*L){if(L!=NULL)

{f4(L->next);

printf("%d",L->data);

}}a1a2an∧…LL->nextf(L->next)f(L)6.3遞歸算法設(shè)計(jì)方法73/1156.3.3二叉樹的遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)便是從遞歸數(shù)據(jù)結(jié)構(gòu)的基本遞歸運(yùn)算入手的。對(duì)于二叉樹，以二叉鏈為存儲(chǔ)結(jié)構(gòu)，其基本遞歸運(yùn)算就是求一個(gè)結(jié)點(diǎn)p的左子樹（p->lchild）和右子樹（p->rchild）。p->lchild和p->rchild一定是一棵二叉樹（這是為什么二叉樹的定義中空樹也是二叉樹的原因）。6.3遞歸算法設(shè)計(jì)方法74/115對(duì)于二叉樹b，設(shè)f(b)是求解的“大問題”。f(b->lchild)和f(b->rchild)為“小問題”。假設(shè)f(b->lchild)和f(b->rchild)是可求的，在此基礎(chǔ)上得出f(b)和f(b->lchild)、f(b->rchild)之間的關(guān)系，從而得到遞歸體。再考慮b=NULL或只有一個(gè)結(jié)點(diǎn)的特殊情況，從而得到遞歸出口。一般地，二叉樹的遞歸結(jié)構(gòu)如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)6.3遞歸算法設(shè)計(jì)方法75/115例如，假設(shè)二叉樹中所有結(jié)點(diǎn)值為整數(shù)，采用二叉鏈存儲(chǔ)結(jié)構(gòu)，求該二叉樹b中所有結(jié)點(diǎn)值之和。f(b)=0

當(dāng)b=NULLf(b)=b->data+f(b->lchild)+f(b->rchild) 其他情況intSum(BTNode*b){if(b==NULL)return0;

elsereturn(b->data+Sum(b->lchild)+Sum(b->rchild));}6.3遞歸算法設(shè)計(jì)方法設(shè)f(b)為二叉樹b中所有結(jié)點(diǎn)值之和，則f(b->lchild)和f(b->rchild)分別求根結(jié)點(diǎn)b的左、右子樹的所有結(jié)點(diǎn)值之和。顯然有f(b)=b->data+f(b->lchild)+f(b->rchild)。當(dāng)b=NULL時(shí)f(b)=0。76/1156.4二叉樹的基本運(yùn)算算法6.4.1二叉樹的基本運(yùn)算一般地，二叉樹有如下幾個(gè)基本運(yùn)算：CreateBTree(bt,str)：根據(jù)二叉樹的括號(hào)表示法str建立二叉鏈存儲(chǔ)結(jié)構(gòu)bt。DestroyBTree(bt)：釋放二叉樹bt占用的內(nèi)存空間。BTHeight(bt)：求一棵二叉樹bt的高度。NodeCount(bt)：求一棵二叉樹bt的結(jié)點(diǎn)個(gè)數(shù)。LeafCount(bt)：求一棵二叉樹bt的葉子結(jié)點(diǎn)個(gè)數(shù)。DispBTree(bt)：以括號(hào)表示法輸出一棵二叉樹bt。6.4二叉樹的基本運(yùn)算算法77/1156.4.2二叉樹基本運(yùn)算實(shí)現(xiàn)算法本小節(jié)采用二叉鏈存儲(chǔ)結(jié)構(gòu)，討論二叉樹基本運(yùn)算算法。（1）創(chuàng)建二叉樹CreateBTree(bt,str)

str邏輯結(jié)構(gòu)bt存儲(chǔ)結(jié)構(gòu)6.4二叉樹的基本運(yùn)算算法78/115

采用括號(hào)表示法表示的二叉樹字符串str，且每個(gè)結(jié)點(diǎn)的值是單個(gè)字符。用ch掃描str，其中只有4類字符，各類字符的處理方式：若ch='('：表示前面剛創(chuàng)建的p結(jié)點(diǎn)存在著孩子結(jié)點(diǎn)，需將其進(jìn)棧，以便建立它和其孩子結(jié)點(diǎn)的關(guān)系。然后開始處理該結(jié)點(diǎn)的左孩子，因此置k=1，表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)（棧頂結(jié)點(diǎn)）的左孩子結(jié)點(diǎn)；若ch=')'：表示以棧頂結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹創(chuàng)建完畢，將其退棧；若ch=','：表示開始處理?xiàng)ｍ斀Y(jié)點(diǎn)的右孩子結(jié)點(diǎn)，置k=2；其他情況：只能是單個(gè)字符，表示要?jiǎng)?chuàng)建一個(gè)新結(jié)點(diǎn)p，根據(jù)k值建立p結(jié)點(diǎn)與棧頂結(jié)點(diǎn)之間的聯(lián)系，當(dāng)k=1時(shí)，表示p結(jié)點(diǎn)作為棧頂結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，當(dāng)k=2時(shí)，表示p結(jié)點(diǎn)作為棧頂結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。6.4二叉樹的基本運(yùn)算算法79/115對(duì)應(yīng)的算法如下：voidCreateBTree(BTNode*&bt,char*str){BTNode*St[MaxSize],*p=NULL;

inttop=-1,k,j=0;

charch;

bt=NULL; //建立的二叉樹初始時(shí)為空

ch=str[j];6.4二叉樹的基本運(yùn)算算法80/115while(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)

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

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

{switch(k)

{

case1:St[top]->lchild=p;break;

case2:St[top]->rchild=p;break;

} }}

j++;

ch=str[j];}}6.4二叉樹的基本運(yùn)算算法81/115（2）銷毀二叉樹bt的運(yùn)算算法銷毀二叉樹bt的遞歸模型f(bt)如下：f(bt)

不做任何事情 當(dāng)bt=NULLf(bt)

f(bt->lchild);f(bt->rchild);free(bt);其他情況voidDestroyBTree(BTNode*&bt){if(bt!=NULL)

{ DestroyBTree(bt->lchild);

DestroyBTree(bt->rchild);

free(bt);

}}6.4二叉樹的基本運(yùn)算算法82/115（3）求二叉樹高度運(yùn)算算法求二叉樹bt的高度的遞歸模型f(bt)如下：f(bt)=0

若bt=NULLf(bt)=max{f(bt->lchild),f(bt->rchild)}+1 其他情況intBTHeight(BTNode*bt){intlchilddep,rchilddep;

if(bt==NULL)return(0);

//空樹的高度為0

else

{lchilddep=BTHeight(bt->lchild);//求左子樹的高度rchilddep=BTHeight(bt->rchild);//求右子樹的高度

return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);

}}6.4二叉樹的基本運(yùn)算算法83/115（4）求二叉樹結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法求二叉樹bt中結(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(bt)如下：f(bt)=0 當(dāng)bt=NULLf(bt)=f(bt->lchild)+f(bt->rchild)+1 其他情況intNodeCount(BTNode*bt)

//求二叉樹bt的結(jié)點(diǎn)個(gè)數(shù){intnum1,num2;

if(bt==NULL) //為空樹時(shí)返回0return0;

else

{num1=NodeCount(bt->lchild); //求左子樹結(jié)點(diǎn)個(gè)數(shù)

num2=NodeCount(bt->rchild); //求右子樹結(jié)點(diǎn)個(gè)數(shù)

return(num1+num2+1); //返回和加上1

}}6.4二叉樹的基本運(yùn)算算法84/115（5）求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法求二叉樹bt中葉子結(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(bt)如下：f(bt)=0

當(dāng)bt=NULLf(bt)=1

當(dāng)bt為葉子結(jié)點(diǎn)f(bt)=f(bt->lchild)+f(bt->rchild) 其他情況intLeafCount(BTNode*bt) //求二叉樹bt的葉子結(jié)點(diǎn)個(gè)數(shù){intnum1,num2;

if(bt==NULL) //空樹返回0 return0;

elseif(bt->lchild==NULL&&bt->rchild==NULL) return1; //為葉子結(jié)點(diǎn)時(shí)返回1

else

{ num1=LeafCount(bt->lchild); //求左子樹葉子結(jié)點(diǎn)個(gè)數(shù)

num2=LeafCount(bt->rchild); //求右子樹葉子結(jié)點(diǎn)個(gè)數(shù)

return(num1+num2); //返回和

}}6.4二叉樹的基本運(yùn)算算法85/115（6）以括號(hào)表示法輸出二叉樹運(yùn)算算法對(duì)于非空二叉樹bt，先輸出其元素值。當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí)，輸出一個(gè)'('符號(hào)。遞歸處理左子樹。有右子樹時(shí)輸出一個(gè)','符號(hào)。遞歸處理右子樹。最后輸出一個(gè)')'符號(hào)。6.4二叉樹的基本運(yùn)算算法根（左子樹，右子樹）86/115voidDispBTree(BTNode*bt){if(bt!=NULL)

{printf("%c",bt->data);

if(bt->lchild!=NULL||bt->rchild!=NULL)

{printf("(");

//有子樹時(shí)輸出'('

DispBTree(bt->lchild); //遞歸處理左子樹

if(bt->rchild!=NULL) //有右子樹時(shí)輸出','

printf(",");

DispBTree(bt->rchild); //遞歸處理右子樹

printf(")"); //輸出一個(gè)')'

}

}}6.4二叉樹的基本運(yùn)算算法87/1156.5二叉樹的遍歷6.5.1常用的二叉樹遍歷算法二叉樹的遍歷是指按一定的次序訪問樹中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次。其中遍歷次序保證了二叉樹上每個(gè)結(jié)點(diǎn)均被訪問一次且僅有一次。二叉樹常用的遍歷有先序（根）遍歷、中序（根）遍歷、后序（根）遍歷和層次遍歷。所謂先序、中序、后序，區(qū)別在于訪問根結(jié)點(diǎn)的順序。6.5二叉樹的遍歷88/115若二叉樹非空，則：①訪問根結(jié)點(diǎn)；②先序遍歷左子樹；③先序遍歷右子樹。voidPreOrder(BTNode*bt){if(bt!=NULL)

{ printf("%c",bt->data);

PreOrder(bt->lchild);

PreOrder(bt->rchild);

}}先序遍歷序列的特點(diǎn)：其第一個(gè)元素值為二叉樹中根結(jié)點(diǎn)值。1．先序遍歷6.5二叉樹的遍歷89/115若二叉樹非空，則：①中序遍歷左子樹；②訪問根結(jié)點(diǎn)；③中序遍歷右子樹。voidInOrder(BTNode*bt){if(bt!=NULL)

{ InOrder(bt->lchild); printf("%c",bt->data);

InOrder(bt->rchild);

}}中序遍歷序列的特點(diǎn)：若已知二叉樹的根結(jié)點(diǎn)值，以該值為界，將中序遍歷序列分為兩部分，前半部分為左子樹的中序遍歷序列，后半部分為右子樹的中序遍歷序列。2．中序遍歷6.5二叉樹的遍歷90/115若二叉樹非空，則：①后序遍歷左子樹；②后序遍歷右子樹；③訪問根結(jié)點(diǎn)。voidPostOrder(BTNode*bt){if(bt!=NULL)

{ PostOrder(bt->lchild);

PostOrder(bt->rchild); printf("%c",bt->data);

}}后序遍歷序列的特點(diǎn)：最后一個(gè)元素值為二叉樹中根結(jié)點(diǎn)值。3．后序遍歷6.5二叉樹的遍歷91/115層次遍歷是從根結(jié)點(diǎn)出發(fā)，按照從上向下，同一層從左向右的次序訪問所有的結(jié)點(diǎn)。采用層次遍歷得到的訪問結(jié)點(diǎn)序列稱為層次遍歷序列。層次遍歷序列的特點(diǎn)：其第一個(gè)元素值為二叉樹中根結(jié)點(diǎn)值。4.層次遍歷算法6.5二叉樹的遍歷92/115在層次遍歷算法中采用一個(gè)循環(huán)隊(duì)列qu來實(shí)現(xiàn)。層次遍歷算法的實(shí)現(xiàn)過程：先將根結(jié)點(diǎn)進(jìn)隊(duì)，在隊(duì)不空時(shí)循環(huán)：從隊(duì)列中出隊(duì)一個(gè)結(jié)點(diǎn)p，訪問它；若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)；若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)。如此操作直到隊(duì)空為止。6.5二叉樹的遍歷93/115voidLevelOrder(BTNode*bt){BTNode*p;

BTNode*qu[MaxSize]; //定義循環(huán)隊(duì)列,存放二叉鏈結(jié)點(diǎn)指針

intfront,rear; //定義隊(duì)頭和隊(duì)尾指針

front=rear=0;

//置隊(duì)列為空隊(duì)列

rear++;qu[rear]=bt; //根結(jié)點(diǎn)指針進(jìn)入隊(duì)列

while(front!=rear) //隊(duì)列不為空循環(huán)

{ front=(front+1)%MaxSize; p=qu[front];

//出隊(duì)結(jié)點(diǎn)p printf("%c",p->data); //訪問該結(jié)點(diǎn)

if(p->lchild!=NULL) //有左孩子時(shí)將其進(jìn)隊(duì)

{rear=(rear+1)%MaxSize;

qu[rear]=p->lchild; }

if(p->rchild!=NULL) //有右孩子時(shí)將其進(jìn)隊(duì)

{rear=(rear+1)%MaxSize;

qu[rear]=p->rchild; }

}}6.5二叉樹的遍歷94/1156.5.2遍歷算法的應(yīng)用

【例6.9】假設(shè)以二叉鏈作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法求二叉樹中單分支結(jié)點(diǎn)個(gè)數(shù)。采用后序遞歸遍歷方式求解。6.5二叉樹的遍歷空樹返回0.先求出左子樹中單分支結(jié)點(diǎn)個(gè)數(shù)m，再求出右子樹中單分支結(jié)點(diǎn)個(gè)數(shù)n。若根結(jié)點(diǎn)是單分支結(jié)點(diǎn)，則返回m+n+1，否則返回m+n。95/115intonenodes1(BTNode*bt){intm,n;

if(bt!=NULL)

{m=onenodes1(bt->lchild);

n=onenodes1(bt->lchild);

if((bt->lchild==NULL&&bt->rchild!=NULL) //單分支

||(bt->lchild!=NULL&&bt->rchild==NULL))

return(1+m+n);

else

//其他情況

return(m+n);

}

elsereturn0; //空樹返回0}6.5二叉樹的遍歷96/115也可以直接采用遞歸的方法：設(shè)f(bt)求二叉樹bt的單分支結(jié)點(diǎn)個(gè)數(shù)，則f(bt->lchild)求二叉樹bt的左子樹的單分支結(jié)點(diǎn)個(gè)數(shù)，f(bt->rchild)求二叉樹bt的右子樹的單分支結(jié)點(diǎn)個(gè)數(shù)。f(bt)=0 當(dāng)bt=NULLf(bt)=1+f(bt->lchild)+f(bt->rchild) 當(dāng)bt為單分支結(jié)點(diǎn)f(bt)=f(bt->lchild)+f(bt->rchild) 其他情況遞歸模型6.5二叉樹的遍歷97/115intonenodes2(BTNode*bt){intm,n;

if(bt==NULL) //空樹返回0

return0;

m=onenodes2(bt->lchild);

n=onenodes2(bt->rchild);

if((bt->lchild==NULL&&bt->rchild!=NULL)//單分支

||(bt->lchild!=NULL&&bt->rchild==NULL))

return(1+m+n);else

//其他情況return(m+n);}從中看到，兩種求解方式得到的結(jié)果是相同的。先序、中序和后序三種遍歷方法本身就是遞歸的，所以采用遞歸模型設(shè)計(jì)方法求解更加基礎(chǔ)。6.5二叉樹的遍歷98/115

【例6.11】假設(shè)以二叉鏈作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法復(fù)制一棵二叉樹。btbt->lchildbt->rchildntnt->lchildnt->rchildf(bt->lchild，nt->lchild)f(bt->rchild，nt->rchild)6.5二叉樹的遍歷設(shè)計(jì)思路99/115f(bt,nt)

nt=NULL當(dāng)bt=NULLf(bt,nt)

由bt根結(jié)點(diǎn)復(fù)制產(chǎn)生nt根結(jié)點(diǎn);

當(dāng)bt≠NULL

f(bt->lchild,nt->lchild);

f(bt->rchild,nt->rchild);遞歸模型6.5二叉樹的遍歷100/115voidCopyBTree(BTNode*bt,BTNode*&nt)//由二叉樹bt復(fù)制產(chǎn)生二叉樹nt{if(bt!=NULL)

{ nt=(BTNode*)malloc(sizeof(BTNode)); //復(fù)制根結(jié)點(diǎn)

nt->data=bt->data; CopyBTree(bt->lchild,nt->lchild); //遞歸復(fù)制左子樹

CopyBTree(bt->rchild,nt->rchild); //遞歸復(fù)制左子樹

}

elsent=NULL; //bt為空樹時(shí)nt也為空樹}6.5二叉樹的遍歷101/115

【例6.12】設(shè)計(jì)一個(gè)算法，由給定的二叉樹的二叉鏈存儲(chǔ)結(jié)構(gòu)建立其對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)。sb初始時(shí)是一個(gè)所有元素為'#'的一維數(shù)組，它的空間是由系統(tǒng)自動(dòng)分配的。二叉樹中某一個(gè)結(jié)點(diǎn)值存放在sb[i]中，應(yīng)由sb[i]指定一個(gè)結(jié)點(diǎn)而不僅僅是sb。在二叉樹的二叉鏈存儲(chǔ)結(jié)構(gòu)bt中，bt指向根結(jié)點(diǎn)。應(yīng)由根結(jié)點(diǎn)bt修改sb中sb[1]元素值。6.5二叉樹的遍歷設(shè)計(jì)思路102/115f(bt,sb,i)

sb[i]='#' 當(dāng)bt=NULLf(bt,sb,i)

sb[i]=bt->data;

其他情況

f(bt->lchild,sb,2*i);

f(bt->rchild,sb,2*i+1);voidtrans1(BTNode*bt,SqBinTree&sb,inti){

//i的初值為根結(jié)點(diǎn)編號(hào)1if(bt!=NULL)

{sb[i]=bt->data; //創(chuàng)建根結(jié)點(diǎn)

trans1(bt->lchild,sb,2*i); //遞歸建立左子樹

trans1(bt->rchild,sb,2*i+1); //遞歸建立右子樹}

elsesb[i]='#'; //不存在的結(jié)點(diǎn)的對(duì)應(yīng)位置值為'#'}設(shè)f(bt,sb,i)的功能是由bt所指結(jié)點(diǎn)建立sb[i]結(jié)點(diǎn)：6.5二叉樹的遍歷103/115

【例6.13】設(shè)計(jì)一個(gè)算法，由給定的二叉樹順序存儲(chǔ)結(jié)構(gòu)建立其對(duì)應(yīng)的二叉鏈存儲(chǔ)結(jié)構(gòu)。6.5二叉樹的遍歷對(duì)于sb[i]結(jié)點(diǎn)，如果有左孩子，左孩子為sb[2*i]，如果有右孩子，右孩子為sb[2*i+1]。i2i2i+1設(shè)計(jì)思路104/115void*trans2(BTNode*&bt,SqBinTreesb,inti){//i的初值為根結(jié)點(diǎn)編號(hào)1if(i<Maxsize&&sb[i]!='#') //存在有效結(jié)點(diǎn)時(shí){ bt=(BTNode*)malloc(sizeof(BTNode));

//創(chuàng)建根結(jié)點(diǎn)

bt->data=sb[i];

trans2(bt->lchild,sb,2*i); //遞歸建立左子樹

trans2(bt->rchild,sb,2*i+1); //遞歸建立右子樹

}

elsebt=NULL; //無(wú)效結(jié)點(diǎn)對(duì)應(yīng)的二叉鏈為NULL}6.5二叉樹的遍歷105/115

【例6.14】假設(shè)以二叉鏈作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法，輸出每個(gè)葉子結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。并給出下圖的二叉樹的求解結(jié)果。

ABDEGHCFK6.5二叉樹的遍歷106/115解法1：采用先序遍歷的遞歸方法求解。用path數(shù)組保存從根結(jié)點(diǎn)開始的路徑，pathlen保存path中的元素個(gè)數(shù)。在先序遍歷時(shí)，當(dāng)找到某個(gè)葉子結(jié)點(diǎn)時(shí)，path中恰好保存了它的所有祖先結(jié)點(diǎn)，輸出即可。若不是葉子結(jié)點(diǎn)，將其保存到path中，再在左子樹中遞歸查找，之后再在右子樹中遞歸查找。6.5二叉樹的遍歷107/115voidancestor1(BTNode*bt,ElemTypepath[],intpathlen){inti;

if(bt!=NULL)

{if(bt->lchild==NULL&&bt->rchild==NULL)//bt為葉結(jié)點(diǎn){printf("%c結(jié)點(diǎn)的所有祖先結(jié)點(diǎn):",bt->data);

for(i=pathlen-1;i>=0;i--)

printf("%c",path[i]);

printf("\n");

}

else

{path[pathlen]=bt->data; //將當(dāng)前結(jié)點(diǎn)放入路徑中

pathle