精品數(shù)據(jù)結(jié)構(gòu)樹形結(jié)構(gòu)2.ppt

1、第第7 7章章 樹形結(jié)構(gòu)樹形結(jié)構(gòu)7.1 7.1 樹的基本概念樹的基本概念 7.2 7.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì)7.3 7.3 二叉樹存儲結(jié)構(gòu)二叉樹存儲結(jié)構(gòu)7.4 7.4 二叉樹的遍歷二叉樹的遍歷7.5 7.5 二叉樹的基本運算及其實現(xiàn)二叉樹的基本運算及其實現(xiàn)7.6 7.6 二叉樹的構(gòu)造二叉樹的構(gòu)造7.8 7.8 哈夫曼樹哈夫曼樹 本章小結(jié)本章小結(jié)7.7 7.7 線索二叉樹線索二叉樹7.1 7.1 樹的基本概念樹的基本概念 7.1.1 7.1.1 樹的定義樹的定義 7.1.3 7.1.3 樹的基本術(shù)語樹的基本術(shù)語 7.1.2 7.1.2 樹的表示樹的表示7.1.4 7.1.4 樹的性

2、質(zhì)樹的性質(zhì)7.1.5 7.1.5 樹的基本運算樹的基本運算7.1.6 7.1.6 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)7.1.1 7.1.1 樹的定義樹的定義 形式化定義：形式化定義： 樹：樹：tk,r。k是包含是包含n個結(jié)點的有窮集合個結(jié)點的有窮集合(n0),關(guān)系關(guān)系r滿足以下條件滿足以下條件: （1）有且僅有一個結(jié)點）有且僅有一個結(jié)點k0k,它對于關(guān)系它對于關(guān)系r來來說沒有前驅(qū)結(jié)點說沒有前驅(qū)結(jié)點,結(jié)點結(jié)點k0稱作樹的根。稱作樹的根。 （2）除結(jié)點）除結(jié)點k0外外,k中的每個結(jié)點對于關(guān)系中的每個結(jié)點對于關(guān)系r來來說都有且僅有一個前驅(qū)結(jié)點。說都有且僅有一個前驅(qū)結(jié)點。 （3）k中每個結(jié)點對于關(guān)系中每個結(jié)點對

3、于關(guān)系r來說可以有多個來說可以有多個后繼結(jié)點。后繼結(jié)點。遞歸定義：遞歸定義： 樹是由樹是由n（n0）個結(jié)點組成的有限集合（記為）個結(jié)點組成的有限集合（記為t）。其中，）。其中， 如果如果n=0，它是一棵空樹，這是樹的特例；，它是一棵空樹，這是樹的特例； 如果如果n0，這，這n個結(jié)點中存在（有僅存在）一個結(jié)個結(jié)點中存在（有僅存在）一個結(jié)點作為樹的根結(jié)點，簡稱為根（點作為樹的根結(jié)點，簡稱為根（root），其余結(jié)點可），其余結(jié)點可分為分為m （m0）個互不相交的有限集）個互不相交的有限集t1,，t2，tm，其中每一棵子集本身又是一棵符合本定義的樹，其中每一棵子集本身又是一棵符合本定義的樹，稱為根稱為

4、根root的子樹。的子樹。7.1.2 7.1.2 樹的表示樹的表示 （1）樹形表示法。這是樹的最基本的表示）樹形表示法。這是樹的最基本的表示,使用使用一棵倒置的樹表示樹結(jié)構(gòu)一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。下圖就非常直觀和形象。下圖就是采用這種表示法。是采用這種表示法。 a c g j b e d f i h m k l 樹形表示法樹形表示法 （2）文氏圖表示法。使用集合以及集）文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文合的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文氏圖表示法。氏圖表示法。 h l d k i m c g j e b f 文氏圖表示法文氏圖表示法 a （3

5、）凹入表示法。使用線段的伸縮描述樹）凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。結(jié)構(gòu)。下圖是樹的凹入表示法。 （4）括號表示法。將樹的根結(jié)點寫在括號）括號表示法。將樹的根結(jié)點寫在括號的左邊的左邊,除根結(jié)點之外的其余結(jié)點寫在括號中并除根結(jié)點之外的其余結(jié)點寫在括號中并用逗號間隔來描述樹結(jié)構(gòu)。下圖是樹的括號表示用逗號間隔來描述樹結(jié)構(gòu)。下圖是樹的括號表示法。法。7.1.3 7.1.3 樹的基本術(shù)語樹的基本術(shù)語 1. 結(jié)點的度與樹的度：樹中某個結(jié)點的子樹的結(jié)點的度與樹的度：樹中某個結(jié)點的子樹的個數(shù)稱為該結(jié)點的度。樹中各結(jié)點的度的最大值稱個數(shù)稱為該結(jié)點的度。樹中各結(jié)點的度的最大值稱為樹的度

6、，通常將度為為樹的度，通常將度為m的樹稱為的樹稱為m次樹或次樹或m叉樹。叉樹。 2. 分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非終端結(jié)點，又叫分支結(jié)點。度為零的結(jié)點稱為終端終端結(jié)點，又叫分支結(jié)點。度為零的結(jié)點稱為終端結(jié)點或葉結(jié)點。在分支結(jié)點中，每個結(jié)點的分支數(shù)結(jié)點或葉結(jié)點。在分支結(jié)點中，每個結(jié)點的分支數(shù)就是該結(jié)點的度。如對于度為就是該結(jié)點的度。如對于度為1的結(jié)點，其分支數(shù)為的結(jié)點，其分支數(shù)為1，被稱為單分支結(jié)點；對于度為，被稱為單分支結(jié)點；對于度為2的結(jié)點，其分支的結(jié)點，其分支數(shù)為數(shù)為2，被稱為雙分支結(jié)點，其余類推。，被稱為雙分支結(jié)點，其余類推。 3. 路徑與

7、路徑長度：對于任意兩個結(jié)點路徑與路徑長度：對于任意兩個結(jié)點ki和和kj，若樹中存在一個結(jié)點序列若樹中存在一個結(jié)點序列ki，ki1，ki2，kin，kj，使得序列中除使得序列中除ki外的任一結(jié)點都是其在序列中的前一外的任一結(jié)點都是其在序列中的前一個結(jié)點的后繼，則稱該結(jié)點序列為由個結(jié)點的后繼，則稱該結(jié)點序列為由ki到到kj的一條路的一條路徑，用路徑所通過的結(jié)點序列徑，用路徑所通過的結(jié)點序列(ki,ki1,ki2,kj)表示這表示這條路徑。路徑的長度等于路徑所通過的結(jié)點數(shù)目減條路徑。路徑的長度等于路徑所通過的結(jié)點數(shù)目減1（即路徑上分支數(shù)目）?？梢?，路徑就是從（即路徑上分支數(shù)目）?？梢?，路徑就是從ki

8、出發(fā)出發(fā)“自上而下自上而下”到達(dá)到達(dá)kj所通過的樹中結(jié)點序列。顯然，所通過的樹中結(jié)點序列。顯然，從樹的根結(jié)點到樹中其余結(jié)點均存在一條路徑。從樹的根結(jié)點到樹中其余結(jié)點均存在一條路徑。 4. 孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點：在一棵樹中，孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點：在一棵樹中，每個結(jié)點的后繼，被稱作該結(jié)點的孩子結(jié)點（或子每個結(jié)點的后繼，被稱作該結(jié)點的孩子結(jié)點（或子女結(jié)點）。相應(yīng)地，該結(jié)點被稱作孩子結(jié)點的雙親女結(jié)點）。相應(yīng)地，該結(jié)點被稱作孩子結(jié)點的雙親結(jié)點（或父母結(jié)點）。具有同一雙親的孩子結(jié)點互結(jié)點（或父母結(jié)點）。具有同一雙親的孩子結(jié)點互為兄弟結(jié)點。進(jìn)一步推廣這些關(guān)系，可以把每個結(jié)為兄弟結(jié)點。進(jìn)一步推

9、廣這些關(guān)系，可以把每個結(jié)點的所有子樹中的結(jié)點稱為該結(jié)點的子孫結(jié)點，從點的所有子樹中的結(jié)點稱為該結(jié)點的子孫結(jié)點，從樹根結(jié)點到達(dá)該結(jié)點的路徑上經(jīng)過的所有結(jié)點被稱樹根結(jié)點到達(dá)該結(jié)點的路徑上經(jīng)過的所有結(jié)點被稱作該結(jié)點的祖先結(jié)點。作該結(jié)點的祖先結(jié)點。 5. 結(jié)點的層次和樹的高度：樹中的每個結(jié)點都結(jié)點的層次和樹的高度：樹中的每個結(jié)點都處在一定的層次上。結(jié)點的層次從樹根開始定義，處在一定的層次上。結(jié)點的層次從樹根開始定義，根結(jié)點為第一層（有的教材從第根結(jié)點為第一層（有的教材從第0層開始），它的孩層開始），它的孩子結(jié)點為第二層，以此類推，一個結(jié)點所在的層次子結(jié)點為第二層，以此類推，一個結(jié)點所在的層次為其雙親結(jié)

10、點所在的層次加為其雙親結(jié)點所在的層次加1。樹中結(jié)點的最大層次。樹中結(jié)點的最大層次稱為樹的高度（或樹的深度）。稱為樹的高度（或樹的深度）。 7. 有序樹和無序樹：若樹中各結(jié)點的子樹是按有序樹和無序樹：若樹中各結(jié)點的子樹是按照一定的次序從左向右安排的，且相對次序是不能照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹。隨意變換的，則稱為有序樹，否則稱為無序樹。 7. 森林：森林：n（n0）個互不相交的樹的集合）個互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近，稱為森林。森林的概念與樹的概念十分相近，因為只要把樹的根結(jié)點刪去就成了森林。反之，因為只要把樹的

11、根結(jié)點刪去就成了森林。反之，只要給只要給n棵獨立的樹加上一個結(jié)點，并把這棵獨立的樹加上一個結(jié)點，并把這n棵棵樹作為該結(jié)點的子樹，則森林就變成了樹。樹作為該結(jié)點的子樹，則森林就變成了樹。7.1.4 7.1.4 樹的性質(zhì)樹的性質(zhì)性質(zhì)性質(zhì)1 樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。 證明：根據(jù)樹的定義，在一棵樹中，除樹根結(jié)點證明：根據(jù)樹的定義，在一棵樹中，除樹根結(jié)點外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點。也就是說，外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點。也就是說，每個結(jié)點與指向它的一個分支一一對應(yīng)，所以除樹每個結(jié)點與指向它的一個分支一一對應(yīng)，所以除樹根之外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)

12、（度數(shù)），根之外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)（度數(shù)），從而可得樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加從而可得樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。 性質(zhì)性質(zhì)2 度為度為m的樹中第的樹中第i層上至多有層上至多有mi-1個結(jié)點，這個結(jié)點，這里應(yīng)有里應(yīng)有i1。 證明（采用數(shù)學(xué)歸納法）證明（采用數(shù)學(xué)歸納法） 對于第一層，因為樹中的第一層上只有一個結(jié)點，對于第一層，因為樹中的第一層上只有一個結(jié)點，即整個樹的根結(jié)點，而由即整個樹的根結(jié)點，而由i=1代入代入mi-1，得，得mi-1=m1-1=1，也同樣得到只有一個結(jié)點，顯然結(jié)論成立。也同樣得到只有一個結(jié)點，顯然結(jié)論成立。 假設(shè)對于第假設(shè)對于第(i-1)層（層（i1

13、）命題成立，即度為）命題成立，即度為m的的樹中第樹中第(i-1)層上至多有層上至多有mi-2個結(jié)點，則根據(jù)樹的度的定個結(jié)點，則根據(jù)樹的度的定義，度為義，度為m的樹中每個結(jié)點至多有的樹中每個結(jié)點至多有m個孩子結(jié)點，所個孩子結(jié)點，所以第以第i層上的結(jié)點數(shù)至多為第層上的結(jié)點數(shù)至多為第(i-1)層上結(jié)點數(shù)的層上結(jié)點數(shù)的m倍，倍，即至多為即至多為mi-2m=mi-1個，這與命題相同，故命題成個，這與命題相同，故命題成立。立。 性質(zhì)性質(zhì)3 高度為高度為h的的m次樹至多有次樹至多有 個結(jié)點。個結(jié)點。 證明：由樹的性質(zhì)證明：由樹的性質(zhì)2可知，第可知，第i層上最多結(jié)點數(shù)為層上最多結(jié)點數(shù)為mi-1（i=1，2，h

14、），顯然當(dāng)高度為），顯然當(dāng)高度為h的的m次樹次樹（即度為（即度為m的樹）上每一層都達(dá)到最多結(jié)點數(shù)時，整的樹）上每一層都達(dá)到最多結(jié)點數(shù)時，整個個m次樹具有最多結(jié)點數(shù)，因此有：次樹具有最多結(jié)點數(shù)，因此有：整個樹的最多結(jié)點數(shù)整個樹的最多結(jié)點數(shù)=每一層最多結(jié)點數(shù)之和每一層最多結(jié)點數(shù)之和=m0+m1+m2+mh-1 = 。11 mmh11 mmh 性質(zhì)性質(zhì)4 具有具有n個結(jié)點的個結(jié)點的m次樹的最小高度為次樹的最小高度為 logm(n(m-1)+1) 。 證明：設(shè)具有證明：設(shè)具有n個結(jié)點的個結(jié)點的m次樹的高度為次樹的高度為h，若在，若在該樹中前該樹中前h-1層都是滿的，即每一層的結(jié)點數(shù)都等于層都是滿的，即

15、每一層的結(jié)點數(shù)都等于mi-1個（個（1ih-1），第），第h層（即最后一層）的結(jié)點數(shù)層（即最后一層）的結(jié)點數(shù)可能滿，也可能不滿，則該樹具有最小的高度。其高可能滿，也可能不滿，則該樹具有最小的高度。其高度度h可計算如下：可計算如下：根據(jù)樹的性質(zhì)根據(jù)樹的性質(zhì)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對數(shù)后得：為底取對數(shù)后得：h-1logm(n(m-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整數(shù)，所以只能取整數(shù)，所以 h= logm(n(m-1)+1) 結(jié)論得證。結(jié)論得證。111 mmh11 mmh 例例7.

16、1 含含n個結(jié)點的三次樹的最小高度是多少？個結(jié)點的三次樹的最小高度是多少？ 解：設(shè)含解：設(shè)含n個結(jié)點的個結(jié)點的(為完全三次樹時高度最小為完全三次樹時高度最小)的三的三次樹的最小高度為次樹的最小高度為h，則有：，則有： 1+3+9+3h-2+1n1+3+9+3h-1 (3h-1-1)/2 +1n (3h-1)/2 3h-1 2n-1 3h-2 即：即：h= log3(2n-1) +1或：或： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2 3h-12n+13h 即：即：h= log3(2n+1) 7.1.5 7.1.5 樹的基本運算樹的基本運算 樹的運算主

17、要分為三大類：樹的運算主要分為三大類： 第一類，尋找滿足某種特定關(guān)系的結(jié)點，如第一類，尋找滿足某種特定關(guān)系的結(jié)點，如尋找當(dāng)前結(jié)點的雙親結(jié)點等；尋找當(dāng)前結(jié)點的雙親結(jié)點等； 第二類，插入或刪除某個結(jié)點，如在樹的當(dāng)?shù)诙?，插入或刪除某個結(jié)點，如在樹的當(dāng)前結(jié)點上插入一個新結(jié)點或刪除當(dāng)前結(jié)點的第前結(jié)點上插入一個新結(jié)點或刪除當(dāng)前結(jié)點的第i i個孩子結(jié)點等；個孩子結(jié)點等； 第三類，遍歷樹中每個結(jié)點，這里著重介紹。第三類，遍歷樹中每個結(jié)點，這里著重介紹。 樹的遍歷運算是指按某種方式訪問樹中的每一個樹的遍歷運算是指按某種方式訪問樹中的每一個結(jié)點且每一個結(jié)點只被訪問一次。樹的遍歷運算的結(jié)點且每一個結(jié)點只被訪問一次

18、。樹的遍歷運算的算法主要有先根遍歷和后根遍歷兩種。注意，下面算法主要有先根遍歷和后根遍歷兩種。注意，下面的先根遍歷和后根遍歷算法都是遞歸的。的先根遍歷和后根遍歷算法都是遞歸的。 1. 先根遍歷先根遍歷 先根遍歷算法為：先根遍歷算法為： （1）訪問根結(jié)點；）訪問根結(jié)點； （2）按照從左到右的次序先根遍歷根結(jié)點的每一）按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹?？米訕洹?2. 后根遍歷后根遍歷 后根遍歷算法為：后根遍歷算法為： （1）按照從左到右的次序后根遍歷根結(jié)點的每一）按照從左到右的次序后根遍歷根結(jié)點的每一棵子樹；棵子樹； （2）訪問根結(jié)點。）訪問根結(jié)點。7.1.6 7.1.6 樹的存儲結(jié)構(gòu)

19、樹的存儲結(jié)構(gòu)1. 1. 雙親存儲結(jié)構(gòu)雙親存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu)，用一組連這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu)，用一組連續(xù)空間存儲樹的所有結(jié)點，同時在每個結(jié)點中附續(xù)空間存儲樹的所有結(jié)點，同時在每個結(jié)點中附設(shè)一個偽指針指示其雙親結(jié)點的位置。設(shè)一個偽指針指示其雙親結(jié)點的位置。 a d b c g e f a -1 b 0 c 0 d 0 e 2 f 2 g 2 0 1 2 3 4 5 6 (a) (b) 2. 孩子鏈存儲結(jié)構(gòu)孩子鏈存儲結(jié)構(gòu) 孩子鏈存儲結(jié)構(gòu)可按樹的度（即樹中所有結(jié)點度的孩子鏈存儲結(jié)構(gòu)可按樹的度（即樹中所有結(jié)點度的最大值）設(shè)計結(jié)點的孩子結(jié)點指針域個數(shù)。下圖（最大值）設(shè)計結(jié)點的

20、孩子結(jié)點指針域個數(shù)。下圖（a）的樹對應(yīng)的孩子鏈存儲結(jié)構(gòu)如圖（的樹對應(yīng)的孩子鏈存儲結(jié)構(gòu)如圖（b）所示。）所示。 a b c f d e (a) g a b c d e f g (b) 3. 孩子兄弟鏈存儲結(jié)構(gòu)孩子兄弟鏈存儲結(jié)構(gòu) 孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設(shè)計三個域：孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設(shè)計三個域：一個數(shù)據(jù)元素域，一個該結(jié)點的第一個孩子結(jié)點指一個數(shù)據(jù)元素域，一個該結(jié)點的第一個孩子結(jié)點指針域，一個該結(jié)點的下一個兄弟結(jié)點指針域。下圖針域，一個該結(jié)點的下一個兄弟結(jié)點指針域。下圖（a）的樹對應(yīng)的孩子兄弟鏈存儲結(jié)構(gòu)如圖（）的樹對應(yīng)的孩子兄弟鏈存儲結(jié)構(gòu)如圖（b）所）所示。示。 a b c f d

21、 e (a) g a b d c e g f (b) 7.2 7.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì) 7.2.1 7.2.1 二叉樹概念二叉樹概念7.2.2 7.2.2 二叉樹性二叉樹性質(zhì)質(zhì)7.2.3 7.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換7.2.1 7.2.1 二叉樹概念二叉樹概念 二叉樹也稱為二次樹或二分樹，它是有限的結(jié)點二叉樹也稱為二次樹或二分樹，它是有限的結(jié)點集合，這個集合或者是空，或者由一個根結(jié)點和兩集合，這個集合或者是空，或者由一個根結(jié)點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成?？没ゲ幌嘟坏姆Q為左子樹和右子樹的二叉樹組成。 二叉樹的定義是一種遞歸定

22、義。二叉樹的定義是一種遞歸定義。 二叉樹有五種基本形態(tài)，如下圖所示，任何復(fù)二叉樹有五種基本形態(tài)，如下圖所示，任何復(fù)雜的二叉樹都是這五種基本形態(tài)的復(fù)合。雜的二叉樹都是這五種基本形態(tài)的復(fù)合。 從定義看到，二叉樹是一種特殊的樹，其表從定義看到，二叉樹是一種特殊的樹，其表示法也與樹的表示法一樣，有樹形表示法、文氏示法也與樹的表示法一樣，有樹形表示法、文氏圖表示法、凹入表示法和括號表示法等。圖表示法、凹入表示法和括號表示法等。 在一棵二叉樹中，如果所有分支結(jié)點都有左孩子在一棵二叉樹中，如果所有分支結(jié)點都有左孩子結(jié)點和右孩子結(jié)點，并且葉結(jié)點都集中在二叉樹的最結(jié)點和右孩子結(jié)點，并且葉結(jié)點都集中在二叉樹的最下

23、一層，這樣的二叉樹稱為滿二叉樹。下圖所示就是下一層，這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫M二叉樹的結(jié)點進(jìn)行連續(xù)編號，一棵滿二叉樹?？梢詫M二叉樹的結(jié)點進(jìn)行連續(xù)編號，約定編號從樹根為約定編號從樹根為1 1開始，按照層數(shù)從小到大、同一開始，按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個結(jié)點外邊的數(shù)字為層從左到右的次序進(jìn)行。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編號。對該結(jié)點的編號。 a b c d e h i j k f g l m n o 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿二叉樹滿二叉樹 若二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可若

24、二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可以小于以小于2 2，并且最下面一層的葉結(jié)點，并且最下面一層的葉結(jié)點 都依次排列在都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二叉樹中每個結(jié)點進(jìn)行連續(xù)編號，編號的方法同滿二二叉樹中每個結(jié)點進(jìn)行連續(xù)編號，編號的方法同滿二叉樹相同。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編叉樹相同。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編號。號。 a b c d e h i j k f g 1 2 3 4 5 6 7 8 9 10 11

25、 完全二叉樹完全二叉樹 7.2.2 7.2.2 二叉樹性質(zhì)二叉樹性質(zhì) 性質(zhì)性質(zhì)1 非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1。 證明：設(shè)二叉樹上葉結(jié)點數(shù)為證明：設(shè)二叉樹上葉結(jié)點數(shù)為n0，單分支結(jié)點數(shù)，單分支結(jié)點數(shù)為為n1，雙分支結(jié)點數(shù)為，雙分支結(jié)點數(shù)為n2，則總結(jié)點數(shù)，則總結(jié)點數(shù)=n0+n1+n2。在。在一棵二叉樹中，所有結(jié)點的分支數(shù)（即度數(shù)）應(yīng)等于一棵二叉樹中，所有結(jié)點的分支數(shù)（即度數(shù)）應(yīng)等于單分支結(jié)點數(shù)加上雙分支結(jié)點數(shù)的單分支結(jié)點數(shù)加上雙分支結(jié)點數(shù)的2倍，即總的分支倍，即總的分支數(shù)數(shù)=n1+2n2。 由于二叉樹中除根結(jié)點以外，每個結(jié)點都有惟一的由于二叉樹

26、中除根結(jié)點以外，每個結(jié)點都有惟一的一個分支指向它，因此二叉樹中有：總的分支數(shù)一個分支指向它，因此二叉樹中有：總的分支數(shù)=總總結(jié)點數(shù)結(jié)點數(shù)-1。 由上述三個等式可得：由上述三個等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1 性質(zhì)性質(zhì)2 非空二叉樹上第非空二叉樹上第i層上至多有層上至多有2i-1個結(jié)點，這個結(jié)點，這里應(yīng)有里應(yīng)有i1。 由樹的性質(zhì)由樹的性質(zhì)2可推出?？赏瞥?。 性質(zhì)性質(zhì)3 高度為高度為h的二叉樹至多有的二叉樹至多有2h-1個結(jié)點個結(jié)點（h1）。）。 由樹的性質(zhì)由樹的性質(zhì)3可推出?？赏瞥?。 性質(zhì)性質(zhì)4 對完全二叉樹中編號為對完全二叉樹中編號為i的結(jié)點（的結(jié)點（1in，

27、n1，n為結(jié)點數(shù)）有：為結(jié)點數(shù)）有： （1）若）若i n/2 ，即，即2in，則編號為，則編號為i的結(jié)點為分的結(jié)點為分支結(jié)點，否則為葉子結(jié)點。支結(jié)點，否則為葉子結(jié)點。 （2）若）若n為奇數(shù)，則每個分支結(jié)點都既有左孩為奇數(shù)，則每個分支結(jié)點都既有左孩子結(jié)點，也有右孩子結(jié)點；若子結(jié)點，也有右孩子結(jié)點；若n為偶數(shù)，則編號最為偶數(shù)，則編號最大的分支結(jié)點（編號為）只有左孩子結(jié)點，沒有右大的分支結(jié)點（編號為）只有左孩子結(jié)點，沒有右孩子結(jié)點，其余分支結(jié)點都有左、右孩子結(jié)點。孩子結(jié)點，其余分支結(jié)點都有左、右孩子結(jié)點。 （3）若編號為）若編號為i的結(jié)點有左孩子結(jié)點，則左孩子的結(jié)點有左孩子結(jié)點，則左孩子結(jié)點的編號為

28、結(jié)點的編號為2i；若編號為；若編號為i的結(jié)點有右孩子結(jié)點，的結(jié)點有右孩子結(jié)點，則右孩子結(jié)點的編號為則右孩子結(jié)點的編號為(2i+1)。 （4）除樹根結(jié)點外，若一個結(jié)點的編號為）除樹根結(jié)點外，若一個結(jié)點的編號為i，則，則它的雙親結(jié)點的編號為它的雙親結(jié)點的編號為 i/2 ，也就是說，當(dāng)，也就是說，當(dāng)i為偶數(shù)為偶數(shù)時，其雙親結(jié)點的編號為時，其雙親結(jié)點的編號為i/2，它是雙親結(jié)點的左孩，它是雙親結(jié)點的左孩子結(jié)點，當(dāng)子結(jié)點，當(dāng)i為奇數(shù)時，其雙親結(jié)點的編號為為奇數(shù)時，其雙親結(jié)點的編號為(i-1)/2，它是雙親結(jié)點的右孩子結(jié)點。它是雙親結(jié)點的右孩子結(jié)點。 性質(zhì)性質(zhì)5 具有具有n個（個（n0）結(jié)點的完全二叉樹的

29、）結(jié)點的完全二叉樹的高度為高度為 log2n+1 或或 log2n +1。 由完全二叉樹的定義和樹的性質(zhì)由完全二叉樹的定義和樹的性質(zhì)3可推出?？赏瞥?。7.2.3 7.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換1森林、樹轉(zhuǎn)換為二叉樹森林、樹轉(zhuǎn)換為二叉樹 （1）在所有相鄰兄弟結(jié)點（森林中每棵樹的根）在所有相鄰兄弟結(jié)點（森林中每棵樹的根結(jié)點可看成是兄弟結(jié)點）之間加一水平連線。結(jié)點可看成是兄弟結(jié)點）之間加一水平連線。 （2）對每個非葉結(jié)點）對每個非葉結(jié)點k，除了其最左邊的孩子結(jié)，除了其最左邊的孩子結(jié)點外，刪去點外，刪去k與其他孩子結(jié)點的連線。與其他孩子結(jié)點的連線。 （3）所有水平線段

30、以左邊結(jié)點為軸心順時針旋）所有水平線段以左邊結(jié)點為軸心順時針旋轉(zhuǎn)轉(zhuǎn)45度。度。 通過以上步驟，原來的森林就轉(zhuǎn)換為一棵二叉通過以上步驟，原來的森林就轉(zhuǎn)換為一棵二叉樹。一般的樹是森林中的特殊情況，由一般的樹轉(zhuǎn)樹。一般的樹是森林中的特殊情況，由一般的樹轉(zhuǎn)換的二叉樹的根結(jié)點的右孩子結(jié)點始終為空，原因換的二叉樹的根結(jié)點的右孩子結(jié)點始終為空，原因是一般的樹的根結(jié)點不存在兄弟結(jié)點和相鄰的樹。是一般的樹的根結(jié)點不存在兄弟結(jié)點和相鄰的樹。 a b c d e f g h i a b e f g c d h i (a) (c) a b c d e f g h i (b) 將森林轉(zhuǎn)換為二叉樹的過程將森林轉(zhuǎn)換為二叉樹

31、的過程2. 2. 二叉樹還原為森林、樹二叉樹還原為森林、樹 （1）對于一棵二叉樹中任一結(jié)點）對于一棵二叉樹中任一結(jié)點k0，沿著，沿著k1右孩子結(jié)點的右子樹方向搜索所有右孩子結(jié)點，右孩子結(jié)點的右子樹方向搜索所有右孩子結(jié)點，即搜索結(jié)點序列即搜索結(jié)點序列k2，k3，km，其中，其中ki+1為為ki的的右孩子結(jié)點右孩子結(jié)點(1im)，km沒有右孩子結(jié)點。沒有右孩子結(jié)點。 （2）刪去）刪去k1，k2，km之間連線。之間連線。 （3）若）若k1有雙親結(jié)點有雙親結(jié)點k，則連接，則連接k與與ki（2im）。）。 （4）將圖形規(guī)整化，使各結(jié)點按層次排列）將圖形規(guī)整化，使各結(jié)點按層次排列。 a d h b f c

32、 g e a b d c f e h g (a) (c) a b d c f e h g (b) 將一棵二叉樹還原為樹的過程將一棵二叉樹還原為樹的過程7.3 7.3 二叉樹存儲結(jié)構(gòu)二叉樹存儲結(jié)構(gòu) 7.3.1 7.3.1 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 7.3.2 7.3.2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.1 7.3.1 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：對該樹中每個結(jié)點進(jìn)行編號，其編號從小到大的對該樹中每個結(jié)點進(jìn)行編號，其編號從小到大的順序就是結(jié)點存放在連續(xù)存儲單元的先后次序。順

33、序就是結(jié)點存放在連續(xù)存儲單元的先后次序。若把二叉樹存儲到一維數(shù)組中，則該編號就是下若把二叉樹存儲到一維數(shù)組中，則該編號就是下標(biāo)值加標(biāo)值加1（注意，（注意，c/c+語言中數(shù)組的起始下標(biāo)為語言中數(shù)組的起始下標(biāo)為0）。樹中各結(jié)點的編號與等高度的完全二叉樹）。樹中各結(jié)點的編號與等高度的完全二叉樹中對應(yīng)位置上結(jié)點的編號相同。中對應(yīng)位置上結(jié)點的編號相同。 利用二叉樹的性質(zhì)利用二叉樹的性質(zhì)4 4。 a b c d e h i j k f g 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 a b c d e f g h i j k123456789101112131415順序存儲結(jié)構(gòu)順

34、序存儲結(jié)構(gòu)7.3.2 7.3.2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 在二叉樹的鏈接存儲中在二叉樹的鏈接存儲中,結(jié)點的結(jié)構(gòu)如下結(jié)點的結(jié)構(gòu)如下: typedef struct node elemtype data; struct node *lchild,*rchild; btnode; 其中，其中，data表示值域，用于存儲對應(yīng)的數(shù)據(jù)元素，表示值域，用于存儲對應(yīng)的數(shù)據(jù)元素，lchild和和rchild分別表示左指針域和右指針域，用于分分別表示左指針域和右指針域，用于分別存儲左孩子結(jié)點和右孩子結(jié)點（即左、右子樹的根別存儲左孩子結(jié)點和右孩子結(jié)點（即左、右子樹的根結(jié)點）的存儲位置。結(jié)點）的存儲

35、位置。 a b c e f d g a b c d e f g (a) (b) 二叉樹及其鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹及其鏈?zhǔn)酱鎯Y(jié)構(gòu) 7.4 7.4 二叉樹的遍歷二叉樹的遍歷7.4.1 7.4.1 二叉樹遍歷的概念二叉樹遍歷的概念7.4.2 7.4.2 二叉樹遍歷遞歸算法二叉樹遍歷遞歸算法7.4.1 7.4.1 二叉樹遍歷的概念二叉樹遍歷的概念 二叉樹的遍歷是指按照一定次序訪問樹中所有二叉樹的遍歷是指按照一定次序訪問樹中所有結(jié)點，并且每個結(jié)點僅被訪問一次的過程。它是最結(jié)點，并且每個結(jié)點僅被訪問一次的過程。它是最基本的運算，是二叉樹中所有其他運算的基礎(chǔ)?；镜倪\算，是二叉樹中所有其他運算的基礎(chǔ)。 1.

36、先序遍歷先序遍歷先序遍歷二叉樹的過程是：先序遍歷二叉樹的過程是： （1）訪問根結(jié)點；）訪問根結(jié)點； （2）先序遍歷左子樹；）先序遍歷左子樹； （3）先序遍歷右子樹。）先序遍歷右子樹。2. 中序遍歷中序遍歷中序遍歷二叉樹的過程是：中序遍歷二叉樹的過程是： （1）中序遍歷左子樹；）中序遍歷左子樹； （2）訪問根結(jié)點；）訪問根結(jié)點； （3）中序遍歷右子樹。）中序遍歷右子樹。 3. 后序遍歷后序遍歷后序遍歷二叉樹的過程是：后序遍歷二叉樹的過程是： （1）后序遍歷左子樹；）后序遍歷左子樹； （2）后序遍歷右子樹；）后序遍歷右子樹； （3）訪問根結(jié)點。）訪問根結(jié)點。7.4.2 7.4.2 二叉樹遍歷遞歸算

37、法二叉樹遍歷遞歸算法 由二叉樹的三種遍歷過程直接得到如下三種遞歸算由二叉樹的三種遍歷過程直接得到如下三種遞歸算法如下：法如下： void preorder(btnode *b) /*先序遍歷的遞歸算法先序遍歷的遞歸算法*/ if (b!=null) printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ preorder(b-lchild); preorder(b-rchild); void inorder(btnode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法*/ if (b!=null) inorder(b-lchild); printf(%c ,b-data); /

38、*訪問根結(jié)點訪問根結(jié)點*/ inorder(b-rchild); void postorder(btnode *b) /*后序遍歷遞歸算法后序遍歷遞歸算法*/ if (b!=null) postorder(b-lchild); postorder(b-rchild); printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ 例例7.2 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，試設(shè)假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，試設(shè)計一個算法，輸出一棵給定二叉樹的所有葉子結(jié)點。計一個算法，輸出一棵給定二叉樹的所有葉子結(jié)點。 解：輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型解：輸出一棵二叉樹的所有葉子結(jié)點的遞

39、歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=null f(b)：輸出：輸出*b結(jié)點的結(jié)點的data域域 若若*b為葉子結(jié)點為葉子結(jié)點 f(b)：f(b-lchild);f(b-rchild) 其他情況其他情況 void displeaf(btnode *b) if (b!=null) if (b-lchild=null & b-rchild=null) printf(%c ,b-data); else displeaf(b-lchild); displeaf(b-rchild); 7.5 7.5 二叉樹的基本運算及其實現(xiàn)二叉樹的基本運算及其實現(xiàn)7.5.1 7.5.1

40、 二叉樹的基本運算概述二叉樹的基本運算概述7.5.2 7.5.2 二叉樹的基本運算算法實現(xiàn)二叉樹的基本運算算法實現(xiàn)7.5.1 7.5.1 二叉樹的基本運算概述二叉樹的基本運算概述 歸納起來，二叉樹有以下基本運算：歸納起來，二叉樹有以下基本運算： （1）創(chuàng)建二叉樹）創(chuàng)建二叉樹createbtnode(*b,*str)：根據(jù)：根據(jù)二叉樹括號表示法的字符串二叉樹括號表示法的字符串*str生成對應(yīng)的鏈?zhǔn)酱鎯ι蓪?yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。結(jié)構(gòu)。 （2）查找結(jié)點）查找結(jié)點findnode(*b,x)：在二叉樹：在二叉樹b中尋中尋找找data域值為域值為x的結(jié)點，并返回指向該結(jié)點的指針。的結(jié)點，并返回指向該結(jié)點的

41、指針。 （3）找孩子結(jié)點）找孩子結(jié)點lchildnode(p)和和rchildnode(p)：分別求二叉樹中結(jié)點分別求二叉樹中結(jié)點*p的左孩子結(jié)點和右孩子結(jié)點。的左孩子結(jié)點和右孩子結(jié)點。 （4）求高度）求高度btnodedepth(*b)：求二叉樹：求二叉樹b的高的高度。若二叉樹為空，則其高度為度。若二叉樹為空，則其高度為0；否則，其高度等；否則，其高度等于左子樹與右子樹中的最大高度加于左子樹與右子樹中的最大高度加l。 （5）輸出二叉樹）輸出二叉樹dispbtnode(*b)：以括號表示：以括號表示法輸出一棵二叉樹。法輸出一棵二叉樹。7.5.2 7.5.2 二叉樹的基本運算算法實現(xiàn)二叉樹的基本

42、運算算法實現(xiàn)（1）創(chuàng)建二叉樹）創(chuàng)建二叉樹createbtnode(*b,*str) 用用ch掃描采用括號表示法表示二叉樹的字符串。分掃描采用括號表示法表示二叉樹的字符串。分以下幾種情況：以下幾種情況： 若若ch=(：則將前面剛創(chuàng)建的結(jié)點作為雙親結(jié)點：則將前面剛創(chuàng)建的結(jié)點作為雙親結(jié)點進(jìn)棧，并置進(jìn)棧，并置k=1，表示其后創(chuàng)建的結(jié)點將作為這個結(jié)點，表示其后創(chuàng)建的結(jié)點將作為這個結(jié)點的左孩子結(jié)點；的左孩子結(jié)點； 若若ch=)：表示棧中結(jié)點的左右孩子結(jié)點處理完：表示棧中結(jié)點的左右孩子結(jié)點處理完畢，退棧；畢，退棧； 若若ch=,：表示其后創(chuàng)建的結(jié)點為右孩子結(jié)點；：表示其后創(chuàng)建的結(jié)點為右孩子結(jié)點； 其他情況，

43、表示要創(chuàng)建一個結(jié)點，并根據(jù)其他情況，表示要創(chuàng)建一個結(jié)點，并根據(jù)k值值建立它與棧中結(jié)點之間的聯(lián)系，當(dāng)建立它與棧中結(jié)點之間的聯(lián)系，當(dāng)k=1時，表示這個時，表示這個結(jié)點作為棧中結(jié)點的左孩子結(jié)點，當(dāng)結(jié)點作為棧中結(jié)點的左孩子結(jié)點，當(dāng)k=2時，表示這時，表示這個結(jié)點作為棧中結(jié)點的右孩子結(jié)點。如此循環(huán)直到個結(jié)點作為棧中結(jié)點的右孩子結(jié)點。如此循環(huán)直到str處理完畢。算法中使用一個棧處理完畢。算法中使用一個棧st保存雙親結(jié)點，保存雙親結(jié)點，top為其棧指針，為其棧指針，k指定其后處理的結(jié)點是雙親結(jié)點指定其后處理的結(jié)點是雙親結(jié)點（保存在棧中）的左孩子結(jié)點（保存在棧中）的左孩子結(jié)點（k=1）還是右孩子結(jié)）還是右孩子

44、結(jié)點（點（k=2）。）。 void createbtnode(btnode * &b,char *str) btnode *stmaxsize,*p=null; int top=-1,k,j=0; char ch; b=null;/*建立的二叉樹初始時為空建立的二叉樹初始時為空*/ ch=strj; while (ch!=0) /*str未掃描完時循環(huán)未掃描完時循環(huán)*/ switch(ch) case (:top+;sttop=p;k=1; break; /*為左孩子結(jié)點為左孩子結(jié)點*/ case ):top-;break; case ,:k=2; break; /*為孩子結(jié)點右結(jié)點為孩子結(jié)點

45、右結(jié)點*/ default:p=(btnode *)malloc(sizeof(btnode); p-data=ch;p-lchild=p-rchild=null; if (b=null) /*p為二叉樹的根結(jié)點為二叉樹的根結(jié)點*/ b=p; else /*已建立二叉樹根結(jié)點已建立二叉樹根結(jié)點*/ switch(k) case 1:sttop-lchild=p;break; case 2:sttop-rchild=p;break; j+;ch=strj; 例 如 ， 對 于 括 號 表 示 法 字 符 串例 如 ， 對 于 括 號 表 示 法 字 符 串a(chǎn)(b(d(,g),c(e,f)，建立二

46、叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)的過，建立二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)的過程如下表所示。程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作st中元素中元素a建立建立a結(jié)點，結(jié)點，b指向該結(jié)點指向該結(jié)點空空(a結(jié)點進(jìn)棧，結(jié)點進(jìn)棧，k=1ab建立建立b結(jié)點，因結(jié)點，因k=1，將其作為，將其作為a結(jié)點結(jié)點的左孩子結(jié)點的左孩子結(jié)點a(b結(jié)點進(jìn)棧，結(jié)點進(jìn)棧，k=1abd建立建立d結(jié)點，因結(jié)點，因k=1，將其作為，將其作為b結(jié)點結(jié)點的左孩子結(jié)點的左孩子結(jié)點ab(d結(jié)點進(jìn)棧，結(jié)點進(jìn)棧，k=1abd,k=2abdg建立建立e結(jié)點，因結(jié)點，因k=2，將其作為，將其作為d結(jié)點的右孩子結(jié)點結(jié)點的右孩子結(jié)點abd)退棧一次退棧一次ab)退棧一次退

47、棧一次a,k=2ac建立建立c結(jié)點，因結(jié)點，因k=2，將其作為，將其作為a結(jié)點的右孩子結(jié)點結(jié)點的右孩子結(jié)點a(c結(jié)點進(jìn)棧，結(jié)點進(jìn)棧，k=1ace建立建立e結(jié)點，因結(jié)點，因k=1，將其作為，將其作為c結(jié)點的左孩子結(jié)點結(jié)點的左孩子結(jié)點ac,k=2acf建立建立f結(jié)點，因結(jié)點，因k=2，將其作為，將其作為c結(jié)點的結(jié)點的右孩子結(jié)點右孩子結(jié)點ac)退棧一次退棧一次a)退棧一次退棧一次空空ch掃描完畢掃描完畢算法結(jié)束算法結(jié)束 a b c d e f g （2）查找結(jié)點）查找結(jié)點findnode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的結(jié)點。找到后返的結(jié)點。找到后返回其指針，

48、否則返回回其指針，否則返回null。算法如下：。算法如下： btnode *findnode(btnode *b,elemtype x) btnode *p;if (b=null) return null;else if (b-data=x) return b;else p=findnode(b-lchild,x); if (p!=null) return p; else return findnode(b-rchild,x); （3）找孩子結(jié)點）找孩子結(jié)點lchildnode(p)和和rchildnode(p) 直接返回直接返回*p結(jié)點的左孩子結(jié)點或右孩子結(jié)點的指結(jié)點的左孩子結(jié)點或右孩子結(jié)點

49、的指針。算法如下：針。算法如下： btnode *lchildnode(btnode *p) return p-lchild; btnode *rchildnode(btnode *p) return p-rchild; （4）求高度）求高度btnodedepth(*b)求二叉樹的高度的遞歸模型求二叉樹的高度的遞歸模型f()如下：如下： f(null)=0 f(b)=maxf(b-lchild),f(b-rchild)+1 其他情況其他情況對應(yīng)的算法如下：對應(yīng)的算法如下：int btnodedepth(btnode *b) int lchilddep,rchilddep; if (b=null

50、) return(0); /*空樹的高度為空樹的高度為0*/ else lchilddep=btnodedepth(b-lchild);/*求左子樹的高度為求左子樹的高度為lchilddep*/ rchilddep=btnodedepth(b-rchild);/*求右子樹的高度為求右子樹的高度為rchilddep*/ return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); （5）輸出二叉樹）輸出二叉樹dispbtnode(*b) 其過程是：對于非空二叉樹其過程是：對于非空二叉樹b，先輸出其元素值，先輸出其元素值，當(dāng)存在左孩子結(jié)點或右孩子

51、結(jié)點時，輸出一個當(dāng)存在左孩子結(jié)點或右孩子結(jié)點時，輸出一個“(”符符號，然后遞歸處理左子樹，輸出一個號，然后遞歸處理左子樹，輸出一個“,”符號，遞歸符號，遞歸處理右子樹，最后輸出一個處理右子樹，最后輸出一個“)”符號。對應(yīng)的遞歸算符號。對應(yīng)的遞歸算法如下：法如下：void dispbtnode(btnode *b) if (b!=null) printf(%c,b-data); if (b-lchild!=null | b-rchild!=null) printf(); dispbtnode(b-lchild);/*遞歸處理左子樹遞歸處理左子樹*/ if (b-rchild!=null) pri

52、ntf(,); dispbtnode(b-rchild);/*遞歸處理右子樹遞歸處理右子樹*/ printf(); 例例7.3 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法判斷兩棵二叉樹是否相似，所謂二叉樹個算法判斷兩棵二叉樹是否相似，所謂二叉樹t1和和t2是相似的指的是是相似的指的是t1和和t2都是空的二叉樹；或者都是空的二叉樹；或者t1和和t2的根結(jié)點是相似的，以及的根結(jié)點是相似的，以及t1的左子樹和的左子樹和t2的左子樹的左子樹是相似的且是相似的且t1的右子樹與的右子樹與t2的右子樹是相似的。的右子樹是相似的。 解：判斷兩棵二叉樹是否相似的遞歸模型解：判

53、斷兩棵二叉樹是否相似的遞歸模型f()如下：如下：f(t1,t2)=true 若若t1=t2=nullf(t1,t2)=false 若若t1、t2之一為之一為null,另一不為另一不為nullf(t1,t2)=f(t1-lchild,t2-lchild) & 其他情況其他情況 f(t1-rchild,t2-rchild) 對應(yīng)的算法如下：對應(yīng)的算法如下：int like(btnode *b1,btnode *b2)/*t1和和t2兩棵二叉樹相似時返回兩棵二叉樹相似時返回1，否則返回，否則返回0*/ int like1,like2; if (b1=null & b2=null) return 1;

54、 else if (b1=null | b2=null) return 0; else like1=like(b1-lchild,b2-lchild); like2=like(b1-rchild,b2-rchild); return (like1 & like2); /*返回返回like1和和like2的與的與*/ 例例7.4 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法level()求二叉樹中指定結(jié)點的層數(shù)。并利用本節(jié)的基本求二叉樹中指定結(jié)點的層數(shù)。并利用本節(jié)的基本運算編寫一個完整的程序，建立教材中圖運算編寫一個完整的程序，建立教材中圖7.8(a)的二

55、叉的二叉樹的二叉鏈，對于用戶輸入的任何結(jié)點值計算出在該二樹的二叉鏈，對于用戶輸入的任何結(jié)點值計算出在該二叉樹中的層次。叉樹中的層次。 解：本題采用遞歸算法，設(shè)解：本題采用遞歸算法，設(shè)h返回返回p所指結(jié)點的高度，所指結(jié)點的高度，其初值為其初值為0。找到指定的結(jié)點時返回其層次；否則返回。找到指定的結(jié)點時返回其層次；否則返回0。lh作為一個中間變量在計算搜索層次時使用，其初值為作為一個中間變量在計算搜索層次時使用，其初值為1。對應(yīng)的算法如下：。對應(yīng)的算法如下：void level(btnode *b,btnode *p,int &h,int lh) /*找到找到*p結(jié)點后結(jié)點后h為其層次為其層次,否

56、則為否則為0*/ if (b=null) h=0; /*空樹時返回空樹時返回0*/ else if (p=b) h=lh; /*找到結(jié)點找到結(jié)點p時時*/ else level(b-lchild,p,h,lh+1); /*在左子樹中遞歸查找在左子樹中遞歸查找*/ if (h=0) /*左子樹中未找到時在右子樹中遞歸查找左子樹中未找到時在右子樹中遞歸查找*/ level(b-rchild,p,h,lh+1);例例7.5 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法輸出從每個葉子結(jié)點到根結(jié)點的路徑。法輸出從每個葉子結(jié)點到根結(jié)點的路徑。 解：這里用層次遍歷方法，

57、設(shè)計的隊列為非循環(huán)順解：這里用層次遍歷方法，設(shè)計的隊列為非循環(huán)順序隊列（類似于第序隊列（類似于第3章章3.2.4小節(jié)中求解迷宮問題時使小節(jié)中求解迷宮問題時使用的隊列）將所有已掃描過的結(jié)點指針進(jìn)隊，并在隊用的隊列）將所有已掃描過的結(jié)點指針進(jìn)隊，并在隊列中保存雙親結(jié)點的位置。當(dāng)找到一個葉子結(jié)點時，列中保存雙親結(jié)點的位置。當(dāng)找到一個葉子結(jié)點時，在隊列中通過雙親結(jié)點的位置輸出該葉子結(jié)點到根結(jié)在隊列中通過雙親結(jié)點的位置輸出該葉子結(jié)點到根結(jié)點的路徑。對應(yīng)的算法如下：點的路徑。對應(yīng)的算法如下： void allpath(btnode *b) struct snode btnode *node;/*存放當(dāng)前結(jié)

58、點指針存放當(dāng)前結(jié)點指針*/ int parent;/*存放雙親結(jié)點在隊列中的位置存放雙親結(jié)點在隊列中的位置*/ qmaxsize;/*定義順序隊列定義順序隊列*/ int front,rear,p;/*定義隊頭和隊尾指針定義隊頭和隊尾指針*/ front=rear=-1;/*置隊列為空隊列置隊列為空隊列*/ rear+;qrear.node=b; /*根結(jié)點指針進(jìn)入隊列根結(jié)點指針進(jìn)入隊列*/ qrear.parent=-1; /*根結(jié)點沒有雙親結(jié)點根結(jié)點沒有雙親結(jié)點*/ while (frontlchild=null & b-rchild=null) printf(%c到根結(jié)點路徑到根結(jié)點路徑

59、:,b-data); p=front; while (qp.parent!=-1) printf(%c-,qp.node-data); p=qp.parent; printf(%cn,qp.node-data); if (b-lchild!=null) /*左孩子結(jié)點入隊列左孩子結(jié)點入隊列*/ rear+;qrear.node=b-lchild; qrear.parent=front; if (b-rchild!=null) /*右孩子結(jié)點入隊列右孩子結(jié)點入隊列*/ rear+; qrear.node=b-rchild; qrear.parent=front; /*end of while*/

60、 7.6 7.6 二叉樹的構(gòu)造二叉樹的構(gòu)造 同一棵二叉樹具有惟一先序序列、中序序列和后序同一棵二叉樹具有惟一先序序列、中序序列和后序序列，但不同的二叉樹可能具有相同的先序序列、序列，但不同的二叉樹可能具有相同的先序序列、中序序列和后序序列。中序序列和后序序列。 例如，如教材中圖例如，如教材中圖7.9所示的所示的5棵二叉樹，先序序棵二叉樹，先序序列都為列都為abc。如圖。如圖7.10所示的所示的5棵二叉樹，中序序列棵二叉樹，中序序列都為都為acb。如圖。如圖7.11所示的所示的5棵二叉樹，后序序列都棵二叉樹，后序序列都為為cba。 顯然，僅由一個先序序列（或中序序列、后序序顯然，僅由一個先序序列