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

第6章樹和二叉樹6.1樹6.2二叉樹6.3遞歸算法設(shè)計方法6.4二叉樹的基本運算算法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）個結(jié)點，當(dāng)n=0時，稱為空樹；非空樹的定義如下：

T=(D，R)其中，D為樹中結(jié)點的有限集合，關(guān)系R滿足以下條件：有且僅有一個結(jié)點d0∈D，它對于關(guān)系R來說沒有前驅(qū)結(jié)點，結(jié)點d0稱作樹的根結(jié)點。除根結(jié)點d0外，D中的每個結(jié)點有且僅有一個前驅(qū)結(jié)點，但可以有多個后繼結(jié)點。D中可以有多個終端結(jié)點。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é)點，其余結(jié)點分成三個互不相交的子集：

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

樹中的結(jié)點數(shù)等于所有結(jié)點的度數(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個結(jié)點（i≥1）。6.1樹22/115

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

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

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

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

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

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

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

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

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

先根遍歷后根遍歷層次遍歷注意：先根和后根遍歷算法都是遞歸的。6.1樹28/115先根遍歷:若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。后根遍歷:若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。層次遍歷:若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。6.1樹29/115ABCDEFGHJIK先根遍歷的頂點訪問次序：ABEFCDGHIJK后根遍歷的頂點訪問次序：EFBCIJKHGDA層次遍歷的頂點訪問次序：ABCDEFGHIJK6.1樹30/1156.1.6樹的存儲結(jié)構(gòu)

這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu)，用一組連續(xù)空間存儲樹的所有結(jié)點，同時在每個結(jié)點中附設(shè)一個偽指針指示其雙親結(jié)點的位置。1.雙親存儲結(jié)構(gòu)ABCDEFHG位置dataparent0A-11B02C03D04E25F26G37H46.1樹31/115孩子鏈存儲結(jié)構(gòu)可按樹的度（即樹中所有結(jié)點度的最大值）設(shè)計結(jié)點的孩子結(jié)點指針域個數(shù)。2.孩子鏈存儲結(jié)構(gòu)ABCDEFHG6.1樹32/115孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設(shè)計三個域：一個數(shù)據(jù)元素域，一個該結(jié)點的第一個孩子結(jié)點指針域，一個該結(jié)點的下一個兄弟結(jié)點指針域。3.孩子兄弟鏈存儲結(jié)構(gòu)ABCDEFHG6.1樹33/1156.2二叉樹6.2.1二叉樹的定義二叉樹的遞歸定義：二叉樹或者是一棵空樹?；蛘呤且豢糜梢粋€根結(jié)點和兩棵互不相交的分別稱做根結(jié)點的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。6.2二叉樹34/115注意：二叉樹與度為2的樹是不同的。度為2的樹至少有3個結(jié)點，而二叉樹的結(jié)點數(shù)可以為0。度為2的樹不區(qū)分子樹的次序，而二叉樹中的每個結(jié)點最多有兩個孩子結(jié)點，且必須要區(qū)分左右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。6.2二叉樹35/115歸納起來，二叉樹的5種形態(tài)：?(a)空二叉樹(b)只有一個根結(jié)點的二叉樹(c)右子樹為空的二叉樹(d)左子樹為空的二叉樹(e)左、右子樹非空的二叉樹6.2二叉樹36/115

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

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

【例6.4】一棵二叉樹中總結(jié)點個數(shù)為200，其中單分支結(jié)點個數(shù)為19，求其葉子結(jié)點個數(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é)點個數(shù)為91。6.2二叉樹39/115性質(zhì)2非空二叉樹上第i層上至多有2i-1個結(jié)點，這里應(yīng)有i≥1。

由樹的性質(zhì)2可推出。性質(zhì)3高度為h的二叉樹至多有2h-1個結(jié)點（h≥1）。

由樹的性質(zhì)3可推出。6.2二叉樹40/115滿二叉樹：在一棵二叉樹中，當(dāng)?shù)趇層的結(jié)點數(shù)為2i-1個時，則稱此層的結(jié)點數(shù)是滿的，當(dāng)一棵二叉樹中的每一層都滿時，且葉子結(jié)點在同一層上，則稱此樹為滿二叉樹。滿二叉樹特性：除葉子結(jié)點以外的其他結(jié)點的度皆為2。

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

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

（3）若編號為i的結(jié)點有左孩子結(jié)點，則左孩子結(jié)點的編號為2i；若編號為i的結(jié)點有右孩子結(jié)點，則右孩子結(jié)點的編號為(2i+1)。

（4）除樹根結(jié)點外,若一個結(jié)點的編號為i，則它的雙親結(jié)點的編號為

i/2，也就是說，當(dāng)i為偶數(shù)時，其雙親結(jié)點的編號為i/2,它是雙親結(jié)點的左孩子結(jié)點，當(dāng)i為奇數(shù)時，其雙親結(jié)點的編號為(i-1)/2，它是雙親結(jié)點的右孩子結(jié)點。i/2i2i2i+16.2二叉樹46/115【例6.5】一棵完全二叉樹中總結(jié)點個數(shù)為200，求其葉子結(jié)點個數(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é)點個數(shù)為100。6.2二叉樹47/1156.2.3二叉樹的存儲結(jié)構(gòu)1．順序存儲結(jié)構(gòu)順序存儲一棵二叉樹時，就是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點。由二叉樹的性質(zhì)4可知，對于完全二叉樹（或滿二叉樹），樹中結(jié)點層序編號可以唯一地反映出結(jié)點之間的邏輯關(guān)系，所以可以用一維數(shù)組按從上到下、從左到右的順序存儲樹中所有結(jié)點值，通過數(shù)組元素的下標(biāo)關(guān)系反映完全二叉樹或滿二叉樹中結(jié)點之間的邏輯關(guān)系。6.2二叉樹48/115一棵完全二叉樹的順序存儲結(jié)構(gòu)1234567891011121314…ABCDEFGHIJKL###位置dataABDHIEJKCFLG1248951011361276.2二叉樹49/115一般的二叉樹的順序存儲結(jié)構(gòu)設(shè)計：ABDEGHCFKABDEGHCFK1248951011361271413增添空結(jié)點補齊為一棵完全二叉樹并對所有結(jié)點進行編號6.2二叉樹50/115ABDEGHCFK12489510113612714131234567891011121314…ABCDE#F##GH##K#位置data僅保留實際存在的結(jié)點值，其他為空6.2二叉樹51/115二叉樹順序存儲結(jié)構(gòu)的類型定義如下：typedefElemTypeSqBinTree[MaxSize];其中，ElemType為二叉樹中結(jié)點的數(shù)據(jù)值類型，MaxSize為順序表的最大長度。為了方便運算，通常將下標(biāo)為0的位置空著，值為'#'的結(jié)點為空結(jié)點。

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

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

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

B

∧D∧

E

∧G∧

∧H∧

∧C

F∧

∧K∧

b6.2二叉樹57/1156.3遞歸算法設(shè)計方法6.3.1什么是遞歸在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱之為遞歸。若調(diào)用自身，稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q，而q又調(diào)用p，稱之為間接遞歸。后面主要介紹直接遞歸。6.3遞歸算法設(shè)計方法58/115例如，有以下遞歸函數(shù)：對應(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è)計方法59/115計算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è)計方法60/115遞歸樹fun(5)fun(4)fun(3)fun(2)fun(1)fun(2)fun(3)fun(2)fun(1)6.3遞歸算法設(shè)計方法61/115一般地，遞歸模型由兩部分組成，一部分為遞歸出口，它給出了遞歸的終止條件。另一部分為遞歸體，它確定遞歸求解時的遞推關(guān)系。例如，前面例子中的f(1)=1和f(2)=1就是遞歸出口；f(n)=f(n-1)+f(n-2)就是遞歸體。6.3遞歸算法設(shè)計方法62/115遞歸算法求解過程的特征：先將不能直接求解的問題轉(zhuǎn)換成若干個相似的小問題，通過分別求解各子問題，最后獲得整個問題的解。當(dāng)這些子問題不能直接求解時，還可以再將它們轉(zhuǎn)換成若干個更小的子問題，如此反復(fù)進行，直到遇到遞歸出口為止。這種自上而下將問題分解、求解，再自上而下引用、合并，求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計方法。6.3遞歸算法設(shè)計方法63/1156.3.2遞歸算法設(shè)計一般方法遞歸算法的設(shè)計方法是，先確定對應(yīng)的遞歸模型，再將其轉(zhuǎn)換為遞歸算法。其核心思想是把問題簡化分解為幾個子問題，其中子問題的形式和算法與原問題算法相似，只是比原來簡化。6.3遞歸算法設(shè)計方法64/115獲取求解問題的遞歸模型的一般步驟對原問題f(s)進行分析，假設(shè)出合理的“小問題”f(s')（與數(shù)學(xué)歸納法中假設(shè)n=k-1時等式成立相似）；假設(shè)f(s')是可解的，在此基礎(chǔ)上確定f(s)的解，即給出f(s)與f(s')之間的關(guān)系（與數(shù)學(xué)歸納法中求證n=k時等式成立的過程相似）；確定一個特定情況（如f(1)或f(0)）的解，由此作為遞歸出口（與數(shù)學(xué)歸納法中求證n=1或時n=0式成立相似）。6.3遞歸算法設(shè)計方法65/115【例6.7】設(shè)計一個遞歸算法求一個整數(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è)計方法設(shè)f(i)為整數(shù)數(shù)組a中a[0]～a[i-1]這i個元素之和，這是原問題。

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

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

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

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

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

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

當(dāng)L中只有一個結(jié)點時f1(L)=max{L->data，f1(L->next)}

其他情況6.3遞歸算法設(shè)計方法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中只有一個結(jié)點時f1(L)=max{L->data，f1(L->next)}

其他情況6.3遞歸算法設(shè)計方法69/115（2）分析同（1）小題。對應(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è)計方法70/115

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

假設(shè)f3(L->next)已輸出，顯然f3(L)等價于先輸出L->data值，再調(diào)用f3(L->next))。當(dāng)單鏈表L為空時，不做任何輸出。a1a2an∧…LL->nextf(L->next)f(L)6.3遞歸算法設(shè)計方法71/115對應(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);

}}其中“

”表示等價關(guān)系。6.3遞歸算法設(shè)計方法72/115（4）分析同（3）小題。對應(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è)計方法73/1156.3.3二叉樹的遞歸算法設(shè)計遞歸算法設(shè)計便是從遞歸數(shù)據(jù)結(jié)構(gòu)的基本遞歸運算入手的。對于二叉樹，以二叉鏈為存儲結(jié)構(gòu)，其基本遞歸運算就是求一個結(jié)點p的左子樹（p->lchild）和右子樹（p->rchild）。p->lchild和p->rchild一定是一棵二叉樹（這是為什么二叉樹的定義中空樹也是二叉樹的原因）。6.3遞歸算法設(shè)計方法74/115對于二叉樹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或只有一個結(jié)點的特殊情況，從而得到遞歸出口。一般地，二叉樹的遞歸結(jié)構(gòu)如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)6.3遞歸算法設(shè)計方法75/115例如，假設(shè)二叉樹中所有結(jié)點值為整數(shù)，采用二叉鏈存儲結(jié)構(gòu)，求該二叉樹b中所有結(jié)點值之和。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è)計方法設(shè)f(b)為二叉樹b中所有結(jié)點值之和，則f(b->lchild)和f(b->rchild)分別求根結(jié)點b的左、右子樹的所有結(jié)點值之和。顯然有f(b)=b->data+f(b->lchild)+f(b->rchild)。當(dāng)b=NULL時f(b)=0。76/1156.4二叉樹的基本運算算法6.4.1二叉樹的基本運算一般地，二叉樹有如下幾個基本運算：CreateBTree(bt,str)：根據(jù)二叉樹的括號表示法str建立二叉鏈存儲結(jié)構(gòu)bt。DestroyBTree(bt)：釋放二叉樹bt占用的內(nèi)存空間。BTHeight(bt)：求一棵二叉樹bt的高度。NodeCount(bt)：求一棵二叉樹bt的結(jié)點個數(shù)。LeafCount(bt)：求一棵二叉樹bt的葉子結(jié)點個數(shù)。DispBTree(bt)：以括號表示法輸出一棵二叉樹bt。6.4二叉樹的基本運算算法77/1156.4.2二叉樹基本運算實現(xiàn)算法本小節(jié)采用二叉鏈存儲結(jié)構(gòu)，討論二叉樹基本運算算法。（1）創(chuàng)建二叉樹CreateBTree(bt,str)

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

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

inttop=-1,k,j=0;

charch;

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

ch=str[j];6.4二叉樹的基本運算算法80/115while(ch!='\0')

//str未掃描完時循環(huán)

{ switch(ch) { case'(':top++;St[top]=p;k=1;break;//為左孩子結(jié)點

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

//為右孩子結(jié)點

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

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

{switch(k)

{

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

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

} }}

j++;

ch=str[j];}}6.4二叉樹的基本運算算法81/115（2）銷毀二叉樹bt的運算算法銷毀二叉樹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二叉樹的基本運算算法82/115（3）求二叉樹高度運算算法求二叉樹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二叉樹的基本運算算法83/115（4）求二叉樹結(jié)點個數(shù)運算算法求二叉樹bt中結(jié)點個數(shù)的遞歸模型f(bt)如下：f(bt)=0 當(dāng)bt=NULLf(bt)=f(bt->lchild)+f(bt->rchild)+1 其他情況intNodeCount(BTNode*bt)

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

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

else

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

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

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

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

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

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

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

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

else

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

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

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

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

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

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

{printf("(");

//有子樹時輸出'('

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

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

printf(",");

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

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

}

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

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

PreOrder(bt->lchild);

PreOrder(bt->rchild);

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

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

InOrder(bt->rchild);

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

{ PostOrder(bt->lchild);

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

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

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

intfront,rear; //定義隊頭和隊尾指針

front=rear=0;

//置隊列為空隊列

rear++;qu[rear]=bt; //根結(jié)點指針進入隊列

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

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

//出隊結(jié)點p 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; }

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

【例6.9】假設(shè)以二叉鏈作為存儲結(jié)構(gòu)，設(shè)計一個算法求二叉樹中單分支結(jié)點個數(shù)。采用后序遞歸遍歷方式求解。6.5二叉樹的遍歷空樹返回0.先求出左子樹中單分支結(jié)點個數(shù)m，再求出右子樹中單分支結(jié)點個數(shù)n。若根結(jié)點是單分支結(jié)點，則返回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é)點個數(shù)，則f(bt->lchild)求二叉樹bt的左子樹的單分支結(jié)點個數(shù)，f(bt->rchild)求二叉樹bt的右子樹的單分支結(jié)點個數(shù)。f(bt)=0 當(dāng)bt=NULLf(bt)=1+f(bt->lchild)+f(bt->rchild) 當(dāng)bt為單分支結(jié)點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è)計方法求解更加基礎(chǔ)。6.5二叉樹的遍歷98/115

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

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

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

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

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

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

}

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

【例6.12】設(shè)計一個算法，由給定的二叉樹的二叉鏈存儲結(jié)構(gòu)建立其對應(yīng)的順序存儲結(jié)構(gòu)。sb初始時是一個所有元素為'#'的一維數(shù)組，它的空間是由系統(tǒng)自動分配的。二叉樹中某一個結(jié)點值存放在sb[i]中，應(yīng)由sb[i]指定一個結(jié)點而不僅僅是sb。在二叉樹的二叉鏈存儲結(jié)構(gòu)bt中，bt指向根結(jié)點。應(yīng)由根結(jié)點bt修改sb中sb[1]元素值。6.5二叉樹的遍歷設(shè)計思路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é)點編號1if(bt!=NULL)

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

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

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

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

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

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

bt->data=sb[i];

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

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

}

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

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

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

if(bt!=NULL)

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

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

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

printf("\n");

}

else

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

pathle