數(shù)據(jù)結(jié)構(gòu) 樹形

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

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

3、K中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系R來說可以有多個(gè)后來說可以有多個(gè)后繼結(jié)點(diǎn)。繼結(jié)點(diǎn)。遞歸定義：遞歸定義： 樹是由樹是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合個(gè)結(jié)點(diǎn)組成的有限集合(記為記為T)。其。其中中, 如果如果n=0,它是一棵空樹它是一棵空樹,這是樹的特例；這是樹的特例； 如果如果n0,這這n個(gè)結(jié)點(diǎn)中存在個(gè)結(jié)點(diǎn)中存在(有僅存在有僅存在)一個(gè)結(jié)點(diǎn)作一個(gè)結(jié)點(diǎn)作為樹的根結(jié)點(diǎn)為樹的根結(jié)點(diǎn),簡(jiǎn)稱為根簡(jiǎn)稱為根(root),其余結(jié)點(diǎn)可分為其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相交的有限集個(gè)互不相交的有限集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

5、(3) 凹入表示法。使用線段的伸縮描述樹結(jié)凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。構(gòu)。下圖是樹的凹入表示法。 (4) 括號(hào)表示法。將樹的根結(jié)點(diǎn)寫在括號(hào)的左括號(hào)表示法。將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來描述樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法。號(hào)間隔來描述樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法。 括號(hào)表示法括號(hào)表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 7.1.3 7.1.3 樹的基本術(shù)語樹的基本術(shù)語 1. 結(jié)點(diǎn)的度與樹的度：樹中某個(gè)結(jié)點(diǎn)的子樹的結(jié)點(diǎn)的度與樹的度：樹中某個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該

6、結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的度的最大值稱個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的度的最大值稱為樹的度為樹的度,通常將度為通常將度為m的樹稱為的樹稱為m次樹次樹。 2. 分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非非終端結(jié)點(diǎn)終端結(jié)點(diǎn),又叫又叫分支結(jié)點(diǎn)分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱為。度為零的結(jié)點(diǎn)稱為終端結(jié)終端結(jié)點(diǎn)點(diǎn)或或葉結(jié)點(diǎn)葉結(jié)點(diǎn)。在分支結(jié)點(diǎn)中。在分支結(jié)點(diǎn)中,每個(gè)結(jié)點(diǎn)的分支數(shù)就是每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)的度。如對(duì)于度為該結(jié)點(diǎn)的度。如對(duì)于度為1的結(jié)點(diǎn)的結(jié)點(diǎn),其分支數(shù)為其分支數(shù)為1,被稱被稱為為單分支結(jié)點(diǎn)單分支結(jié)點(diǎn)；對(duì)于度為；對(duì)于度為2的結(jié)點(diǎn)的結(jié)點(diǎn),其分支數(shù)為其分支數(shù)為2,被稱被稱為為雙

7、分支結(jié)點(diǎn)雙分支結(jié)點(diǎn),其余類推。其余類推。 3. 路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和和kj,若若樹中存在一個(gè)結(jié)點(diǎn)序列樹中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,kin,kj,使得序列中使得序列中除除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼繼,則稱該結(jié)點(diǎn)序列為由則稱該結(jié)點(diǎn)序列為由ki到到kj的一條路徑的一條路徑,用路徑所用路徑所通過的結(jié)點(diǎn)序列通過的結(jié)點(diǎn)序列(ki,ki1,ki2,kj)表示這條路徑。路徑表示這條路徑。路徑的長(zhǎng)度等于路徑所通過的結(jié)點(diǎn)數(shù)目減的長(zhǎng)度等于路徑所通過的結(jié)點(diǎn)數(shù)目減1(即路徑上分支即路徑上分支數(shù)目

8、數(shù)目)?？梢??？梢?路徑路徑就是從就是從ki出發(fā)出發(fā)“自上而下自上而下”到達(dá)到達(dá)kj所通過的樹中結(jié)點(diǎn)序列。顯然所通過的樹中結(jié)點(diǎn)序列。顯然,從樹的根結(jié)點(diǎn)到樹中從樹的根結(jié)點(diǎn)到樹中其余結(jié)點(diǎn)均存在一條路徑。其余結(jié)點(diǎn)均存在一條路徑。 4. 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹中孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹中,每個(gè)結(jié)點(diǎn)的后繼每個(gè)結(jié)點(diǎn)的后繼,被稱作該結(jié)點(diǎn)的被稱作該結(jié)點(diǎn)的孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)(或子女結(jié)或子女結(jié)點(diǎn)點(diǎn))。相應(yīng)地。相應(yīng)地,該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)雙親結(jié)點(diǎn)(或父或父母結(jié)點(diǎn)母結(jié)點(diǎn))。具有同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。具有同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。進(jìn)一步推廣這些

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

10、1。樹中。樹中結(jié)點(diǎn)的最大層次稱為結(jié)點(diǎn)的最大層次稱為樹的高度樹的高度(或樹的深度或樹的深度)。 6. 有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的照一定的次序從左向右安排的,且相對(duì)次序是不能隨且相對(duì)次序是不能隨意變換的意變換的,則稱為則稱為有序樹有序樹,否則稱為否則稱為無序樹無序樹。 7. 森林：森林：n(n0)個(gè)互不相交的樹的集合稱個(gè)互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近為森林。森林的概念與樹的概念十分相近,因?yàn)橐驗(yàn)橹灰褬涞母Y(jié)點(diǎn)刪去就成了森林。反之只要把樹的根結(jié)點(diǎn)刪去就成了森林。反之,只要只要給給n棵獨(dú)立的樹加上一

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

12、的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。 性質(zhì)性質(zhì)2 度為度為m的樹中第的樹中第i層上至多有層上至多有mi-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),這這里應(yīng)有里應(yīng)有i1。 證明證明(采用數(shù)學(xué)歸納法采用數(shù)學(xué)歸納法) 對(duì)于第一層對(duì)于第一層,因?yàn)闃渲械牡谝粚由现挥幸粋€(gè)結(jié)點(diǎn)因?yàn)闃渲械牡谝粚由现挥幸粋€(gè)結(jié)點(diǎn),即即整個(gè)樹的根結(jié)點(diǎn)整個(gè)樹的根結(jié)點(diǎn),而由而由i=1代入代入mi-1,得得mi-1=m1-1=1,也同樣也同樣得到只有一個(gè)結(jié)點(diǎn)得到只有一個(gè)結(jié)點(diǎn),顯然結(jié)論成立。顯然結(jié)論成立。 假設(shè)對(duì)于第假設(shè)對(duì)于第(i-1)層層(i1)命題成立命題成立,即度為即度為m的樹中第的樹中第(i-1)層上至多有層上至多有mi-2個(gè)結(jié)點(diǎn)個(gè)

13、結(jié)點(diǎn),則根據(jù)樹的度的定義則根據(jù)樹的度的定義,度為度為m的樹中每個(gè)結(jié)點(diǎn)至多有的樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)個(gè)孩子結(jié)點(diǎn),所以第所以第i層上的結(jié)層上的結(jié)點(diǎn)數(shù)至多為第點(diǎn)數(shù)至多為第(i-1)層上結(jié)點(diǎn)數(shù)的層上結(jié)點(diǎn)數(shù)的m倍倍,即至多為即至多為mi-2m=mi-1個(gè)個(gè),這與命題相同這與命題相同,故命題成立。故命題成立。 性質(zhì)性質(zhì)3 高度為高度為h的的m次樹至多有次樹至多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 證明：由樹的性質(zhì)證明：由樹的性質(zhì)2可知可知,第第i層上最多結(jié)點(diǎn)數(shù)為層上最多結(jié)點(diǎn)數(shù)為mi-1(i=1,2,h),顯然當(dāng)高度為顯然當(dāng)高度為h的的m次樹次樹(即度為即度為m的樹的樹)上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí)上每一層都達(dá)到最多

14、結(jié)點(diǎn)數(shù)時(shí),整個(gè)整個(gè)m次樹具有最多結(jié)次樹具有最多結(jié)點(diǎn)數(shù)點(diǎn)數(shù),因此有：因此有：整個(gè)樹的最多結(jié)點(diǎn)數(shù)整個(gè)樹的最多結(jié)點(diǎn)數(shù)=每一層最多結(jié)點(diǎn)數(shù)之和每一層最多結(jié)點(diǎn)數(shù)之和=m0+m1+m2+mh-1 = 。11 mmh11 mmh 性質(zhì)性質(zhì)4 具有具有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的m次樹的最小高度為次樹的最小高度為 logm(n(m-1)+1) 。 證明：設(shè)具有證明：設(shè)具有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的m次樹的高度為次樹的高度為h,若在該若在該樹中前樹中前h-1層都是滿的層都是滿的,即每一層的結(jié)點(diǎn)數(shù)都等于即每一層的結(jié)點(diǎn)數(shù)都等于mi-1個(gè)個(gè)(1ih-1),第第h層層(即最后一層即最后一層)的結(jié)點(diǎn)數(shù)可能滿的結(jié)點(diǎn)數(shù)可能滿,也可也可能不滿能不

15、滿,則該樹具有最小的高度。其高度則該樹具有最小的高度。其高度h可計(jì)算如下：可計(jì)算如下：根據(jù)樹的性質(zhì)根據(jù)樹的性質(zhì)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對(duì)數(shù)后得：為底取對(duì)數(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.1 含含n個(gè)結(jié)點(diǎn)的三次樹的最小高度是多少？個(gè)結(jié)點(diǎn)的三次樹的最小高度是多少？最大高度是多少？最大高度是多少？ 解：設(shè)含解：設(shè)含n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的(為

16、完全三次樹時(shí)高度最為完全三次樹時(shí)高度最小小)的三次樹的最小高度為的三次樹的最小高度為h,則有：則有： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2 3h-12n+13h 即：即：h= log3(2n+1) 最大高度為最大高度為n-2。7.1.5 7.1.5 樹的基本運(yùn)算樹的基本運(yùn)算 樹的運(yùn)算主要分為三大類：樹的運(yùn)算主要分為三大類： 第一類第一類, ,尋找滿足某種特定關(guān)系的結(jié)點(diǎn)尋找滿足某種特定關(guān)系的結(jié)點(diǎn), ,如尋如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； 第二類第二類, ,插入或刪除某個(gè)結(jié)點(diǎn)插入或刪除某個(gè)結(jié)點(diǎn), ,如在樹的當(dāng)前如在樹的當(dāng)前結(jié)點(diǎn)上

17、插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i i個(gè)個(gè)孩子結(jié)點(diǎn)等；孩子結(jié)點(diǎn)等； 第三類第三類, ,遍歷樹中每個(gè)結(jié)點(diǎn)遍歷樹中每個(gè)結(jié)點(diǎn), ,這里著重介紹。這里著重介紹。 樹的遍歷運(yùn)算是指按某種方式訪問樹中的每一個(gè)樹的遍歷運(yùn)算是指按某種方式訪問樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問一次。樹的遍歷運(yùn)算的結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問一次。樹的遍歷運(yùn)算的算法主要有先根遍歷和后根遍歷兩種。注意算法主要有先根遍歷和后根遍歷兩種。注意,下面的下面的先根遍歷和后根遍歷算法都是遞歸的。先根遍歷和后根遍歷算法都是遞歸的。 1. 先根遍歷先根遍歷 先根遍歷過程為：先根遍歷過程為： (1) 訪問根結(jié)點(diǎn)

18、；訪問根結(jié)點(diǎn)； (2) 按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹。子樹。 2. 后根遍歷后根遍歷 后根遍歷過程為：后根遍歷過程為： (1) 按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一棵子樹；棵子樹； (2) 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。7.1.6 7.1.6 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)1. 1. 雙親存儲(chǔ)結(jié)構(gòu)雙親存儲(chǔ)結(jié)構(gòu) 這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu), ,用一組連用一組連續(xù)空間存儲(chǔ)樹的所有結(jié)點(diǎn)續(xù)空間存儲(chǔ)樹的所有結(jié)點(diǎn), ,同時(shí)在每個(gè)結(jié)點(diǎn)中附同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置。設(shè)

19、一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置。 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) 樹的雙親存儲(chǔ)結(jié)構(gòu)示意圖樹的雙親存儲(chǔ)結(jié)構(gòu)示意圖2. 孩子鏈存儲(chǔ)結(jié)構(gòu)孩子鏈存儲(chǔ)結(jié)構(gòu) 孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹的度孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹的度(即樹中所有結(jié)點(diǎn)度的即樹中所有結(jié)點(diǎn)度的最大值最大值)設(shè)計(jì)結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針域個(gè)數(shù)。下圖設(shè)計(jì)結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針域個(gè)數(shù)。下圖(a)的樹的樹對(duì)應(yīng)的孩子鏈存儲(chǔ)結(jié)構(gòu)如圖對(duì)應(yīng)的孩子鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B C D E F G (b) 樹的樹的孩子鏈孩子鏈存儲(chǔ)結(jié)構(gòu)示意圖

20、存儲(chǔ)結(jié)構(gòu)示意圖3. 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)孩子兄弟鏈存儲(chǔ)結(jié)構(gòu) 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)域：孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)數(shù)據(jù)元素域一個(gè)數(shù)據(jù)元素域,一個(gè)該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)指一個(gè)該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)指針域針域,一個(gè)該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)指針域。下圖一個(gè)該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)指針域。下圖(a)的樹對(duì)應(yīng)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)如圖的樹對(duì)應(yīng)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B D C E G F (b) 樹的樹的孩子兄弟鏈孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖存儲(chǔ)結(jié)構(gòu)示意圖7.2 7.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì) 7.2.1 7.2

21、.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é)點(diǎn)它是有限的結(jié)點(diǎn)集合集合,這個(gè)集合或者是空這個(gè)集合或者是空,或者由一個(gè)根結(jié)點(diǎn)和兩棵互或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。不相交的稱為左子樹和右子樹的二叉樹組成。 二叉樹的定義是一種遞歸定義。二叉樹的定義是一種遞歸定義。 二叉樹有五種基本形態(tài)二叉樹有五種基本形態(tài), ,如下圖所示如下圖所示, ,任何復(fù)雜任何復(fù)雜的二叉

22、樹都是這五種基本形態(tài)的復(fù)合。的二叉樹都是這五種基本形態(tài)的復(fù)合。 從定義看到從定義看到,二叉樹是一種特殊的樹二叉樹是一種特殊的樹,其表示其表示法也與樹的表示法一樣法也與樹的表示法一樣,有樹形表示法、文氏圖有樹形表示法、文氏圖表示法、凹入表示法和括號(hào)表示法等。表示法、凹入表示法和括號(hào)表示法等。 在一棵二叉樹中在一棵二叉樹中, ,如果所有分支結(jié)點(diǎn)都有左孩子如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)結(jié)點(diǎn)和右孩子結(jié)點(diǎn), ,并且葉結(jié)點(diǎn)都集中在二叉樹的最并且葉結(jié)點(diǎn)都集中在二叉樹的最下一層下一層, ,這樣的二叉樹稱為這樣的二叉樹稱為滿二叉樹滿二叉樹。下圖所示就是。下圖所示就是一棵滿二叉樹。可以對(duì)滿二叉樹的結(jié)點(diǎn)

23、進(jìn)行連續(xù)編號(hào)一棵滿二叉樹?？梢詫?duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào), ,約定編號(hào)從樹根為約定編號(hào)從樹根為1 1開始開始, ,按照層數(shù)從小到大、同一層按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。該結(jié)點(diǎn)的編號(hào)。 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é)點(diǎn)的度數(shù)可若二叉樹中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于以小于2 2, ,并且最下面一層的葉結(jié)點(diǎn)并且最下面一層的葉結(jié)點(diǎn) 都依次排列

24、在該都依次排列在該層最左邊的位置上層最左邊的位置上, ,則這樣的二叉樹稱為則這樣的二叉樹稱為完全二叉樹完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉樹中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)樹中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào), ,編號(hào)的方法同滿二叉樹編號(hào)的方法同滿二叉樹相同。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。相同。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 7.2.2 7.2.2 二叉樹性質(zhì)二叉樹性質(zhì) 性質(zhì)性質(zhì)1 非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)

25、數(shù)加非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。 證明：設(shè)二叉樹上葉結(jié)點(diǎn)數(shù)為證明：設(shè)二叉樹上葉結(jié)點(diǎn)數(shù)為n0,單分支結(jié)點(diǎn)數(shù)為單分支結(jié)點(diǎn)數(shù)為n1,雙分支結(jié)點(diǎn)數(shù)為雙分支結(jié)點(diǎn)數(shù)為n2,則總結(jié)點(diǎn)數(shù)則總結(jié)點(diǎn)數(shù)=n0+n1+n2。在一棵。在一棵二叉樹中二叉樹中,所有結(jié)點(diǎn)的分支數(shù)所有結(jié)點(diǎn)的分支數(shù)(即度數(shù)即度數(shù))應(yīng)等于單分支結(jié)應(yīng)等于單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的2倍倍,即總的分支數(shù)即總的分支數(shù)=n1+2n2。 由于二叉樹中除根結(jié)點(diǎn)以外由于二叉樹中除根結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)都有惟一的一每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指向它個(gè)分支指向它,因此二叉樹中有：總的分支數(shù)因此二叉樹中有：總的分支數(shù)=總結(jié)點(diǎn)總結(jié)點(diǎn)數(shù)

26、數(shù)-1。 由上述三個(gè)等式可得：由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1 性質(zhì)性質(zhì)2 非空二叉樹上第非空二叉樹上第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),這這里應(yīng)有里應(yīng)有i1。 由樹的性質(zhì)由樹的性質(zhì)2可推出?？赏瞥?。 性質(zhì)性質(zhì)3 高度為高度為h的二叉樹至多有的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(h1)。 由樹的性質(zhì)由樹的性質(zhì)3可推出?？赏瞥?。 性 質(zhì)性 質(zhì) 4 對(duì) 完 全 二 叉 樹 中 編 號(hào) 為對(duì) 完 全 二 叉 樹 中 編 號(hào) 為 i 的 結(jié) 點(diǎn)的 結(jié) 點(diǎn)(1in,n1,n為結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù))有：有： (1) 若若i n/2 ,即即2in,則編號(hào)為則編號(hào)

27、為i的結(jié)點(diǎn)為分支結(jié)的結(jié)點(diǎn)為分支結(jié)點(diǎn)點(diǎn),否則為葉子結(jié)點(diǎn)。否則為葉子結(jié)點(diǎn)。 (2) 若若n為奇數(shù)為奇數(shù),則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn)點(diǎn),也有右孩子結(jié)點(diǎn)；若也有右孩子結(jié)點(diǎn)；若n為偶數(shù)為偶數(shù),則編號(hào)最大的分支則編號(hào)最大的分支結(jié)點(diǎn)結(jié)點(diǎn)(編號(hào)為編號(hào)為)只有左孩子結(jié)點(diǎn)只有左孩子結(jié)點(diǎn),沒有右孩子結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn),其余其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。 (3) 若編號(hào)為若編號(hào)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn)的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則左孩子結(jié)點(diǎn)則左孩子結(jié)點(diǎn)的編號(hào)為的編號(hào)為2i；若編號(hào)為；若編號(hào)為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則右孩則右孩子結(jié)點(diǎn)的編號(hào)為子結(jié)點(diǎn)的編

28、號(hào)為(2i+1)。 (4) 除樹根結(jié)點(diǎn)外除樹根結(jié)點(diǎn)外,若一個(gè)結(jié)點(diǎn)的編號(hào)為若一個(gè)結(jié)點(diǎn)的編號(hào)為i,則它的則它的雙親結(jié)點(diǎn)的編號(hào)為雙親結(jié)點(diǎn)的編號(hào)為 i/2 ,也就是說也就是說,當(dāng)當(dāng)i為偶數(shù)時(shí)為偶數(shù)時(shí),其雙其雙親結(jié)點(diǎn)的編號(hào)為親結(jié)點(diǎn)的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)當(dāng)i為奇數(shù)時(shí)為奇數(shù)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2,它是雙親結(jié)點(diǎn)它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。的右孩子結(jié)點(diǎn)。 性質(zhì)性質(zhì)5 具有具有n個(gè)個(gè)(n0)結(jié)點(diǎn)的完全二叉樹的高度結(jié)點(diǎn)的完全二叉樹的高度為為 log2n+1 或或 log2n +1。 由完全二叉樹的定義和樹的性質(zhì)由完全二叉樹的定義和樹的性質(zhì)3

29、可推出?？赏瞥?。7.2.3 7.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換1森林、樹轉(zhuǎn)換為二叉樹森林、樹轉(zhuǎn)換為二叉樹 步驟如下：步驟如下： (1) 在所有相鄰兄弟結(jié)點(diǎn)在所有相鄰兄弟結(jié)點(diǎn)(森林中每棵樹的根結(jié)點(diǎn)森林中每棵樹的根結(jié)點(diǎn)可看成是兄弟結(jié)點(diǎn)可看成是兄弟結(jié)點(diǎn))之間加一水平連線。之間加一水平連線。 (2) 對(duì)每個(gè)非葉結(jié)點(diǎn)對(duì)每個(gè)非葉結(jié)點(diǎn)k,除了其最左邊的孩子結(jié)點(diǎn)外除了其最左邊的孩子結(jié)點(diǎn)外,刪去刪去k與其他孩子結(jié)點(diǎn)的連線。與其他孩子結(jié)點(diǎn)的連線。 (3) 所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度。度。 通過以上步驟通過以上步驟,原來的森林就轉(zhuǎn)

30、換為一棵二叉樹。原來的森林就轉(zhuǎn)換為一棵二叉樹。一般的樹是森林中的特殊情況一般的樹是森林中的特殊情況,由一般的樹轉(zhuǎn)換的二由一般的樹轉(zhuǎn)換的二叉樹的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)始終為空叉樹的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)始終為空,原因是一般的原因是一般的樹的根結(jié)點(diǎn)不存在兄弟結(jié)點(diǎn)和相鄰的樹。樹的根結(jié)點(diǎn)不存在兄弟結(jié)點(diǎn)和相鄰的樹。 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)換為二叉樹的過程2. 2. 二叉樹還原為森林、樹二叉樹還原為森林、樹 步驟如下：步驟如下： (1) 對(duì)于一棵二叉樹中任一結(jié)點(diǎn)對(duì)于一棵二叉

31、樹中任一結(jié)點(diǎn)k0,沿著沿著k0的左的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)k1的右子樹方向搜索所有右孩子結(jié)點(diǎn)的右子樹方向搜索所有右孩子結(jié)點(diǎn),即即搜索結(jié)點(diǎn)序列搜索結(jié)點(diǎn)序列k2,k3,km,其中其中ki+1為為ki的右孩子結(jié)的右孩子結(jié)點(diǎn)點(diǎn)(1im),km沒有右孩子結(jié)點(diǎn)。沒有右孩子結(jié)點(diǎn)。 (2) 刪去刪去k1,k2,km之間連線。之間連線。 (3) 若若k1有雙親結(jié)點(diǎn)有雙親結(jié)點(diǎn)k,則連接則連接k與與ki(2im)。 (4) 將圖形規(guī)整化將圖形規(guī)整化,使各結(jié)點(diǎn)按層次排列使各結(jié)點(diǎn)按層次排列。 A D H B F C G E A B D C F E H G (a) (c) A B D C F E H G (b) 將一棵二叉樹

32、還原為樹的過程將一棵二叉樹還原為樹的過程7.3 7.3 二叉樹存儲(chǔ)結(jié)構(gòu)二叉樹存儲(chǔ)結(jié)構(gòu) 7.3.1 7.3.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu) 7.3.2 7.3.2 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.1 7.3.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu) 二叉樹的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：二叉樹的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：對(duì)該樹中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)對(duì)該樹中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào),其編號(hào)從小到大的順其編號(hào)從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉樹存儲(chǔ)到一維數(shù)組中把二叉樹存儲(chǔ)到一維數(shù)組中,則該編號(hào)就是下標(biāo)值

33、則該編號(hào)就是下標(biāo)值加加1(注意注意,C/C+語言中數(shù)組的起始下標(biāo)為語言中數(shù)組的起始下標(biāo)為0)。樹。樹中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹中對(duì)應(yīng)位中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同。置上結(jié)點(diǎn)的編號(hào)相同。 利用二叉樹的性質(zhì)利用二叉樹的性質(zhì)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順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)7.3.2 7.3.2 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在二叉樹的鏈接存儲(chǔ)中在二叉樹的鏈接存儲(chǔ)中,結(jié)點(diǎn)的

34、結(jié)構(gòu)如下結(jié)點(diǎn)的結(jié)構(gòu)如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素素,lchild和和rchild分別表示左指針域和右指針域分別表示左指針域和右指針域,用于用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹的即左、右子樹的根結(jié)點(diǎn)根結(jié)點(diǎn))的存儲(chǔ)位置。的存儲(chǔ)位置。 A B C E F D G A B C D E F G (a) (b) 二叉樹及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 7.4 7

35、.4 二叉樹的遍歷二叉樹的遍歷7.4.1 7.4.1 二叉樹遍歷的概念二叉樹遍歷的概念7.4.2 7.4.2 二叉樹遍歷遞歸算法二叉樹遍歷遞歸算法7.4.3 7.4.3 二叉樹遍歷非遞歸算法二叉樹遍歷非遞歸算法 7.4.1 7.4.1 二叉樹遍歷的概念二叉樹遍歷的概念 二叉樹的遍歷是指按照一定次序訪問樹中所有二叉樹的遍歷是指按照一定次序訪問樹中所有結(jié)點(diǎn)結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。它是最基并且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。它是最基本的運(yùn)算本的運(yùn)算,是二叉樹中所有其他運(yùn)算的基礎(chǔ)。是二叉樹中所有其他運(yùn)算的基礎(chǔ)。1. 先序遍歷先序遍歷先序遍歷二叉樹的過程是：先序遍歷二叉樹的過程是：(1) 訪問

36、根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；(2) 先序遍歷左子樹；先序遍歷左子樹；(3) 先序遍歷右子樹。先序遍歷右子樹。2. 中序遍歷中序遍歷中序遍歷二叉樹的過程是：中序遍歷二叉樹的過程是：(1) 中序遍歷左子樹；中序遍歷左子樹；(2) 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；(3) 中序遍歷右子樹。中序遍歷右子樹。 3. 后序遍歷后序遍歷后序遍歷二叉樹的過程是：后序遍歷二叉樹的過程是：(1) 后序遍歷左子樹；后序遍歷左子樹；(2) 后序遍歷右子樹；后序遍歷右子樹；(3) 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。7.4.2 7.4.2 二叉樹遍歷遞歸算法二叉樹遍歷遞歸算法 由二叉樹的三種遍歷過程直接得到如下三種遞歸算由二叉樹的三種遍歷過程直接得

37、到如下三種遞歸算法如下：法如下： void PreOrder(BTNode *b) /*先序遍歷的遞歸算法先序遍歷的遞歸算法*/ if (b!=NULL) printf(%c ,b-data); /*訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)*/ PreOrder(b-lchild); PreOrder(b-rchild); void InOrder(BTNode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)*/ InOrder(b-rchild); void PostOrder

38、(BTNode *b) /*后序遍歷遞歸算法后序遍歷遞歸算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)*/ 層次遍歷層次遍歷其過程是：其過程是：若二叉樹非空（假設(shè)其高度為若二叉樹非空（假設(shè)其高度為h），則：），則：（1）訪問根結(jié)點(diǎn)（第）訪問根結(jié)點(diǎn)（第1層）；層）；（2）從左到右訪問第）從左到右訪問第2層的所有結(jié)點(diǎn)；層的所有結(jié)點(diǎn)；（3）從左到右訪問第）從左到右訪問第3層的所有結(jié)點(diǎn)、層的所有結(jié)點(diǎn)、第、第h層的所有結(jié)點(diǎn)。層的所有結(jié)點(diǎn)。 A B C E F D G

39、A B C D E F G (a) (b) 層次遍歷序列：層次遍歷序列：A、B、C、D、E、F、Gvoid LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;/*定義環(huán)形隊(duì)列定義環(huán)形隊(duì)列,存放結(jié)點(diǎn)指針存放結(jié)點(diǎn)指針*/ int front,rear;/*定義隊(duì)頭和隊(duì)尾指針定義隊(duì)頭和隊(duì)尾指針*/ front=rear=-1;/*置隊(duì)列為空隊(duì)列置隊(duì)列為空隊(duì)列*/ rear+; qurear=b;/*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/ while (front!=rear)/*隊(duì)列不為空隊(duì)列不為空*/ front=(front+1)%MaxSi

40、ze; p=qufront;/*隊(duì)頭出隊(duì)列隊(duì)頭出隊(duì)列*/ printf(%c ,p-data);/*訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)*/if (p-lchild!=NULL)/*有左孩子時(shí)將其進(jìn)隊(duì)有左孩子時(shí)將其進(jìn)隊(duì)*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子時(shí)將其進(jìn)隊(duì)有右孩子時(shí)將其進(jìn)隊(duì)*/ rear=(rear+1)%MaxSize; qurear=p-rchild; 例例7.2 假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ),試設(shè)試設(shè)計(jì)一個(gè)算法計(jì)一個(gè)算法,輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。輸出一棵給

41、定二叉樹的所有葉子結(jié)點(diǎn)。 解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b結(jié)點(diǎn)的結(jié)點(diǎn)的data域域 若若*b為葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn) 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); DispLea

42、f(b-rchild); 7.4.3 7.4.3 二叉樹遍歷非遞歸算法二叉樹遍歷非遞歸算法 1. 1. 先序遍歷先序遍歷非遞歸算法非遞歸算法（1）第一種方法）第一種方法由先序遍歷的定義可知，其遞歸模型由先序遍歷的定義可知，其遞歸模型f()如下：如下： f(p)：不做任何事件：不做任何事件 若若p=NULL f(p)：輸出：輸出*p結(jié)點(diǎn)的結(jié)點(diǎn)的data域值域值;其他情況其他情況 f(p-lchild); f(p-rchild); 遞歸等價(jià)關(guān)系遞歸等價(jià)關(guān)系（非相等關(guān)系）（非相等關(guān)系）void PreOrder1(BTNode *b)BTNode *p;struct BTNode *pt; int

43、tag; /1:未訪問，未訪問，0:可訪問可訪問 StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/棧不空時(shí)循環(huán)棧不空時(shí)循環(huán) if (Sttop.tag=1)/不能直接訪問的情況不能直接訪問的情況 p=Sttop.pt;top-;if (p!=NULL)/(2)式式 top+;/右孩子結(jié)點(diǎn)進(jìn)棧右孩子結(jié)點(diǎn)進(jìn)棧 Sttop.pt=p-rchild;Sttop.tag=1; top+;/左孩子結(jié)點(diǎn)進(jìn)棧左孩子結(jié)點(diǎn)進(jìn)棧 Sttop.pt=p-lchild;Sttop.tag=1; top+;/根結(jié)點(diǎn)進(jìn)棧根結(jié)點(diǎn)進(jìn)棧 Sttop.p

44、t=p;Sttop.tag=0; /end of if (Sttop.tag=1) if (Sttop.tag=0)/直接訪問的情況直接訪問的情況 printf(%c ,Sttop.pt-data); top-; /while （2）第二種方法（常規(guī)方法）第二種方法（常規(guī)方法） void PreOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;top+; Sttop=b; /根結(jié)點(diǎn)入棧根結(jié)點(diǎn)入棧while (top-1) /棧不為空時(shí)循環(huán)棧不為空時(shí)循環(huán) p=Sttop; top-; /退棧并訪問該結(jié)點(diǎn)退棧并訪問該結(jié)點(diǎn) printf(%c ,p

45、-data); if (p-rchild!=NULL) /右孩子結(jié)點(diǎn)入棧右孩子結(jié)點(diǎn)入棧 top+; Sttop=p-rchild; if (p-lchild!=NULL)/左孩子結(jié)點(diǎn)入棧左孩子結(jié)點(diǎn)入棧 top+; Sttop=p-lchild; 2. 中序遍歷非遞歸算法中序遍歷非遞歸算法（2）第二種方法（常規(guī)方法）第二種方法（常規(guī)方法） 由中序遍歷過程可知，采用一個(gè)棧保存需要返回的結(jié)由中序遍歷過程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，先掃描（并非訪問）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它點(diǎn)指針，先掃描（并非訪問）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧。們一一進(jìn)棧。 然后出棧一個(gè)結(jié)點(diǎn)，顯然該結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)

46、或者然后出棧一個(gè)結(jié)點(diǎn)，顯然該結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)已訪問過（進(jìn)一步說明該結(jié)點(diǎn)的左子樹均已訪左孩子結(jié)點(diǎn)已訪問過（進(jìn)一步說明該結(jié)點(diǎn)的左子樹均已訪問），則訪問它。然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)問），則訪問它。然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，如此棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，如此這樣，直到棧空為止。這樣，直到?？諡橹埂?void InOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;p=b;while (top-1 | p!=NULL) while (p!=NULL) /掃

47、描掃描*p的所有左結(jié)點(diǎn)并進(jìn)棧的所有左結(jié)點(diǎn)并進(jìn)棧 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出棧出棧*p結(jié)點(diǎn)結(jié)點(diǎn) printf(%c ,p-data); /訪問之訪問之 p=p-rchild; /掃描掃描*p的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn) /end of while(top-1 | p!=NULL) 找找*b的最左下的最左下結(jié)點(diǎn)結(jié)點(diǎn)3. 后序遍歷非遞歸算法后序遍歷非遞歸算法 （2）第二種方法（常規(guī)方法）第二種方法（常規(guī)方法） 由后遍歷過程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，由后遍歷過程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，先掃描根結(jié)

48、點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，出棧一個(gè)結(jié)點(diǎn)先掃描根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，出棧一個(gè)結(jié)點(diǎn)*b即當(dāng)即當(dāng)前結(jié)點(diǎn)，然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)并入棧，再掃描該右孩前結(jié)點(diǎn)，然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)并入棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧。當(dāng)一個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)均訪子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧。當(dāng)一個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)均訪問后再訪問該結(jié)點(diǎn)，如此這樣，直到?？諡橹?。問后再訪問該結(jié)點(diǎn)，如此這樣，直到棧空為止。 難點(diǎn)：難點(diǎn)：如何判斷一個(gè)結(jié)點(diǎn)如何判斷一個(gè)結(jié)點(diǎn)*b的右孩子結(jié)點(diǎn)已訪問過的右孩子結(jié)點(diǎn)已訪問過，為此，為此用用p保存剛剛訪問過的結(jié)點(diǎn)（初值為保存剛剛訪問過的結(jié)點(diǎn)（初值為NULL），若），若b-rchild=

49、p成立（成立（在后序遍歷中，在后序遍歷中，*b的右孩子結(jié)點(diǎn)一定剛好在的右孩子結(jié)點(diǎn)一定剛好在*b之前訪之前訪問問），說明），說明*b的左右子樹均已訪問，現(xiàn)在應(yīng)訪問的左右子樹均已訪問，現(xiàn)在應(yīng)訪問*b。 void PostOrder2(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;/棧指針置初值棧指針置初值do while (b!=NULL) /將將*b的所有左結(jié)點(diǎn)進(jìn)棧的所有左結(jié)點(diǎn)進(jìn)棧 top+; Sttop=b; b=b-lchild; p=NULL; /p指向棧頂結(jié)點(diǎn)的前一個(gè)已訪問的結(jié)點(diǎn)指向棧頂結(jié)點(diǎn)的前一個(gè)已訪問的結(jié)點(diǎn) flag=1;

50、 /設(shè)置設(shè)置b的訪問標(biāo)記為已訪問過的訪問標(biāo)記為已訪問過找最左下結(jié)點(diǎn)找最左下結(jié)點(diǎn) while (top!=-1 & flag=1) b=Sttop; /取出當(dāng)前的棧頂元素取出當(dāng)前的棧頂元素 if (b-rchild=p) printf(%c ,b-data);/訪問訪問*b結(jié)點(diǎn)結(jié)點(diǎn)top-;p=b;/p指向則被訪問的結(jié)點(diǎn)指向則被訪問的結(jié)點(diǎn) else b=b-rchild; /b指向右孩子結(jié)點(diǎn)指向右孩子結(jié)點(diǎn) flag=0;/設(shè)置未被訪問的標(biāo)記設(shè)置未被訪問的標(biāo)記 /end of while (top!=-1 & flag=1) while (top!=-1); b b的右孩子不存在或

51、已訪問過的右孩子不存在或已訪問過 從上述過程可知，棧中保存的是當(dāng)前從上述過程可知，棧中保存的是當(dāng)前結(jié)點(diǎn)結(jié)點(diǎn)*b的所有祖先結(jié)點(diǎn)（均未訪問過）。的所有祖先結(jié)點(diǎn)（均未訪問過）。 例如，求一個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。例如，求一個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。7.5 7.5 二叉樹的基本運(yùn)算及其實(shí)現(xiàn)二叉樹的基本運(yùn)算及其實(shí)現(xiàn)7.5.1 7.5.1 二叉樹的基本運(yùn)算概述二叉樹的基本運(yùn)算概述7.5.2 7.5.2 二叉樹的基本運(yùn)算算法實(shí)現(xiàn)二叉樹的基本運(yùn)算算法實(shí)現(xiàn)7.5.1 7.5.1 二叉樹的基本運(yùn)算概述二叉樹的基本運(yùn)算概述 歸納起來歸納起來,二叉樹有以下基本運(yùn)算：二叉樹有以下基本運(yùn)算： (1)創(chuàng)建二叉樹創(chuàng)建二叉樹Crea

52、teBTNode(*b,*str)：根據(jù)二叉：根據(jù)二叉樹括號(hào)表示法的字符串樹括號(hào)表示法的字符串*str生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 (2)查找結(jié)點(diǎn)查找結(jié)點(diǎn)FindNode(*b,x)：在二叉樹：在二叉樹b中尋找中尋找data域值為域值為x的結(jié)點(diǎn)的結(jié)點(diǎn),并返回指向該結(jié)點(diǎn)的指針。并返回指向該結(jié)點(diǎn)的指針。 (3)找孩子結(jié)點(diǎn)找孩子結(jié)點(diǎn)LchildNode(p)和和RchildNode(p)：分別求二叉樹中結(jié)點(diǎn)分別求二叉樹中結(jié)點(diǎn)*p的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。 (4)求高度求高度BTNodeDepth(*b)：求二叉樹：求二叉樹b的高度。的高度。若二叉樹為空若

53、二叉樹為空,則其高度為則其高度為0；否則；否則,其高度等于左子其高度等于左子樹與右子樹中的最大高度加樹與右子樹中的最大高度加l。 (5)輸出二叉樹輸出二叉樹DispBTNode(*b)：以括號(hào)表示法：以括號(hào)表示法輸出一棵二叉樹。輸出一棵二叉樹。7.5.2 7.5.2 二叉樹的基本運(yùn)算算法實(shí)現(xiàn)二叉樹的基本運(yùn)算算法實(shí)現(xiàn) (1) 創(chuàng)建二叉樹創(chuàng)建二叉樹CreateBTNode(*b,*str) 用用ch掃描采用括號(hào)表示法表示二叉樹的字符串。分掃描采用括號(hào)表示法表示二叉樹的字符串。分以下幾種情況：以下幾種情況： 若若ch=(：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧進(jìn)棧,并

54、置并置k=1,表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；左孩子結(jié)點(diǎn)； 若若ch=)：表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完：表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完畢畢,退棧；退棧； 若若ch=,：表示其后創(chuàng)建的結(jié)點(diǎn)為右孩子結(jié)點(diǎn)；：表示其后創(chuàng)建的結(jié)點(diǎn)為右孩子結(jié)點(diǎn)； 其他情況其他情況,表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn),并根據(jù)并根據(jù)k值建值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系立它與棧中結(jié)點(diǎn)之間的聯(lián)系,當(dāng)當(dāng)k=1時(shí)時(shí),表示這個(gè)結(jié)點(diǎn)表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)當(dāng)k=2時(shí)時(shí),表示這個(gè)結(jié)點(diǎn)表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到作為棧中結(jié)點(diǎn)的

55、右孩子結(jié)點(diǎn)。如此循環(huán)直到str處理處理完畢。算法中使用一個(gè)棧完畢。算法中使用一個(gè)棧St保存雙親結(jié)點(diǎn)保存雙親結(jié)點(diǎn),top為其棧為其棧指針指針,k指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)(保存在棧中保存在棧中)的左孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)(k=1)還是右孩子結(jié)點(diǎn)還是右孩子結(jié)點(diǎn)(k=2)。 void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/*建立的二叉樹初始時(shí)為空建立的二叉樹初始時(shí)為空*/ ch=strj; while (ch

56、!=0) /*str未掃描完時(shí)循環(huán)未掃描完時(shí)循環(huán)*/ switch(ch) case (:top+;Sttop=p;k=1; break; /*為左孩子結(jié)點(diǎn)為左孩子結(jié)點(diǎn)*/ case ):top-;break; case ,:k=2; break; /*為孩子結(jié)點(diǎn)右結(jié)點(diǎn)為孩子結(jié)點(diǎn)右結(jié)點(diǎn)*/ default:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /*p為二叉樹的根結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)*/ b=p; else /*已建立二叉樹根結(jié)點(diǎn)已建立二叉樹根結(jié)點(diǎn)*/ switch(k)

57、case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+;ch=strj; 例如例如,對(duì)于括號(hào)表示串對(duì)于括號(hào)表示串A(B(D(,G),C(E,F),建立建立二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程如下表所示。二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素A建立建立A結(jié)點(diǎn)結(jié)點(diǎn),b指向該結(jié)點(diǎn)指向該結(jié)點(diǎn)空空(A結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1AB建立建立B結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為A結(jié)點(diǎn)的左結(jié)點(diǎn)的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)A(B結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ABD建立建立D結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為B結(jié)點(diǎn)的左結(jié)點(diǎn)

58、的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)ABch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素(D結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ABD,k=2ABDG建立建立G結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為D結(jié)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)點(diǎn)的右孩子結(jié)點(diǎn)ABD)退棧一次退棧一次AB)退棧一次退棧一次A,k=2AC建立建立C結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為A結(jié)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)點(diǎn)的右孩子結(jié)點(diǎn)A(C結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ACE建立建立E結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為C結(jié)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)點(diǎn)的左孩子結(jié)點(diǎn)AC,k=2ACch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素F建立建立F結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為C結(jié)點(diǎn)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)

59、的右孩子結(jié)點(diǎn)AC)退棧一次退棧一次A)退棧一次退棧一次空空ch掃描完畢掃描完畢算法結(jié)束算法結(jié)束 A B C D E F G 生成的二叉樹生成的二叉樹 (2) 查找結(jié)點(diǎn)查找結(jié)點(diǎn)FindNode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的結(jié)點(diǎn)。找到后返的結(jié)點(diǎn)。找到后返回其指針回其指針,否則返回否則返回NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; else p=FindNode

60、(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); (3) 找孩子結(jié)點(diǎn)找孩子結(jié)點(diǎn)LchildNode(p)和和RchildNode(p) 直接返回直接返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)的指結(jié)點(diǎn)的左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)的指針。算法如下：針。算法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; (4) 求高度求高度BTNodeDepth(*b)求二叉樹的高度的遞歸模型求二叉樹的高度的遞歸模型f()如下：如下： f(