數(shù)據(jù)結(jié)構(gòu)與算法-第五章Trees

1、信息工程學(xué)院信息工程學(xué)院School of Information Engineering2第第5 5章章 樹形結(jié)構(gòu)樹形結(jié)構(gòu)(Trees)(Trees)5.1 5.1 樹的基本概念樹的基本概念(Basic concept of tree)(Basic concept of tree) 5.2 5.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì)(Property and concept of binary tree)(Property and concept of binary tree)5.3 5.3 二叉樹存儲(chǔ)結(jié)構(gòu)二叉樹存儲(chǔ)結(jié)構(gòu)(Physical storage structure of binary

2、 tree)(Physical storage structure of binary tree)5.4 5.4 二叉樹的遍歷二叉樹的遍歷(Binary tree traversals)(Binary tree traversals)35.5 5.5 二叉樹的基本運(yùn)算及其實(shí)現(xiàn)二叉樹的基本運(yùn)算及其實(shí)現(xiàn)(Algorithm implementation and basic operations of binary tree)5.6 5.6 二叉樹的構(gòu)造二叉樹的構(gòu)造(Construction of binary tree)(Construction of binary tree)5.8 5.8 哈夫

3、曼樹哈夫曼樹(Huffman tree)(Huffman tree) SummarySummary5.7 5.7 線索二叉樹線索二叉樹(Threaded binary tree)(Threaded binary tree)45.1.1 5.1.1 樹的定義樹的定義(Definition)(Definition) 5.1.3 5.1.3 樹的基本術(shù)語(yǔ)樹的基本術(shù)語(yǔ)(Basic terminology) (Basic terminology) 5.1.2 5.1.2 樹的表示樹的表示(Representation)(Representation)5.1.4 5.1.4 樹的性質(zhì)樹的性質(zhì)(Proper

4、ty)(Property)5.1.5 5.1.5 樹的基本運(yùn)算樹的基本運(yùn)算(Basic operation)(Basic operation)5.1.6 5.1.6 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)(Physical structure)(Physical structure)5.1 5.1 樹的基本概念樹的基本概念(Basic concept of tree)(Basic concept of tree) 55.1.1 5.1.1 樹的定義樹的定義(Definition)(Definition) 形式化定義：形式化定義： 樹：樹：TK,R。K是包含是包含n個(gè)結(jié)點(diǎn)的有窮集合個(gè)結(jié)點(diǎn)的有窮集合(n0),關(guān)

5、系關(guān)系R滿足以下條件滿足以下條件: (1) 有且僅有一個(gè)結(jié)點(diǎn)有且僅有一個(gè)結(jié)點(diǎn)k0K,它對(duì)于關(guān)系它對(duì)于關(guān)系R來(lái)說(shuō)來(lái)說(shuō)沒(méi)有前驅(qū)結(jié)點(diǎn)沒(méi)有前驅(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來(lái)說(shuō)來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。 (3) K中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)可以有多個(gè)后來(lái)說(shuō)可以有多個(gè)后繼結(jié)點(diǎn)。繼結(jié)點(diǎn)。6遞歸定義：遞歸定義： 樹是由樹是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合個(gè)結(jié)點(diǎn)組成的有限集合(記為記為T)。其。其中中, 如果如果n=0,它是一棵空樹它是一棵空樹,這是樹的特例；這是樹的特例； 如果如

6、果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,其中每一棵其中每一棵子集本身又是一棵符合本定義的樹子集本身又是一棵符合本定義的樹,稱為根稱為根root的子的子樹。樹。7A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹85.1.2 5.1.2 樹的表示樹的表示(Representation)(Representation) ( (1) 樹形表示法。樹形表示法。這是樹的最基本的表示這是樹的最基本的表示,使用一使

7、用一棵倒置的樹表示樹結(jié)構(gòu)棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。下圖就是非常直觀和形象。下圖就是采用這種表示法。采用這種表示法。 A C G J B E D F I H M K L 樹形表示法樹形表示法 9 (2) 文氏圖表示法。文氏圖表示法。使用集合以及集合使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文氏的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文氏圖表示法。圖表示法。 H L D K I M C G J E B F 文氏圖表示法文氏圖表示法 A 10 (3) 凹入表示法。凹入表示法。使用線段的伸縮描述樹結(jié)使用線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。構(gòu)。下圖是樹的凹入表示法。11 (4) 括

8、號(hào)表示法。括號(hào)表示法。 將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊,除根結(jié)點(diǎn)之外除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述樹結(jié)的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法。構(gòu)。下圖是樹的括號(hào)表示法。 括括號(hào)號(hào)表表示示法法 A(B(E,F),C(G(J),D(H,I(K,L,M) 125.1.3 5.1.3 樹的基本術(shù)語(yǔ)樹的基本術(shù)語(yǔ)( (Basic terminology)結(jié)點(diǎn)(node)度不為零的結(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é)點(diǎn)的度(deg

9、ree)結(jié)點(diǎn)擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點(diǎn)孩子(child)在一棵樹中，每個(gè)結(jié)點(diǎn)的后繼雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的兄弟(sibling)同一雙親的孩子樹的度(degree)一棵樹中最大的結(jié)點(diǎn)度數(shù)13結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù)祖先(ancestor)-從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)堂兄弟(cousin)雙親在同一層次的結(jié)點(diǎn)有序樹(ordered tree)將樹中結(jié)點(diǎn)的各個(gè)子樹看成從左至右是有次序的第一孩子(first child)-有序樹中最左邊的子樹的根森林(forest)m(m0)

10、棵互不相交的樹的集合 對(duì)樹中各個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林14ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先155.1.4 5.1.4 樹的性質(zhì)樹的性質(zhì)(Property)(Property) Property 1 樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。 Prove：根據(jù)樹的定義根據(jù)樹的定義,在一棵樹中

11、在一棵樹中,除樹根結(jié)點(diǎn)外除樹根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。也就是說(shuō)也就是說(shuō),每個(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ù)),從而可得樹中從而可得樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。16 Property 2 度為度為m的樹中第的樹中第i層上至多有層上至多有mi-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),這里應(yīng)有這里應(yīng)有i1。 Prove(采用數(shù)學(xué)歸納法采用數(shù)學(xué)歸納法) 對(duì)于第一層對(duì)于第一層,因?yàn)闃渲械牡谝粚由现挥幸粋€(gè)結(jié)點(diǎn)因?yàn)闃渲械牡谝?/p>

12、層上只有一個(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è)結(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è),這與命題相同這與命題

13、相同,故命題成立。故命題成立。17 Property 3 高度為高度為h的的m次樹至多有次樹至多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 Prove：由樹的性質(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á)到最多結(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 mmh18 Property 4 具有具有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)

14、點(diǎn)的m次樹的最小高度為次樹的最小高度為 logm(n(m-1)+1) 。 Prove：設(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ù)可能滿,也可也可能不滿能不滿,則該樹具有最小的高度。其高度則該樹具有最小的高度。其高度h可計(jì)算如下：可計(jì)算如下：19根據(jù)樹的性質(zhì)根據(jù)樹的性質(zhì)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對(duì)數(shù)后得：為底取對(duì)數(shù)后得：h-1logm(n(m

15、-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 mmh205.1.5 5.1.5 樹的基本運(yùn)算樹的基本運(yùn)算(Basic operation)(Basic operation) Tree operation can be classfied into Tree operation can be classfied into three types:three types: First,First,尋找滿足某種特定關(guān)系的結(jié)點(diǎn)尋找滿足某種特定關(guān)系的結(jié)點(diǎn),

16、,如尋找如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； Second,Second,插入或刪除某個(gè)結(jié)點(diǎn)插入或刪除某個(gè)結(jié)點(diǎn), ,如在樹的當(dāng)前如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(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)等； Third,Third,遍歷樹中每個(gè)結(jié)點(diǎn)遍歷樹中每個(gè)結(jié)點(diǎn), ,這里著重介紹。這里著重介紹。21 樹的遍歷樹的遍歷(traversal)運(yùn)算運(yùn)算是指按某種方式訪問(wèn)是指按某種方式訪問(wèn)樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。樹的遍歷運(yùn)算的算法主要有先根遍歷和后根遍歷樹的遍歷運(yùn)算的算法主要有先根遍

17、歷和后根遍歷兩種。兩種。 注意注意,下面的先根遍歷和后根遍歷算法都是遞歸下面的先根遍歷和后根遍歷算法都是遞歸的的。 1. 先根遍歷先根遍歷(Preorder Traversal) 先根遍歷過(guò)程為：先根遍歷過(guò)程為： (1) 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； (2) 按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹。一棵子樹。 22 2. 后根遍歷后根遍歷(Postorder Traversal) 后根遍歷過(guò)程為：后根遍歷過(guò)程為： (1) 按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一棵子樹；棵子樹； (2) 訪問(wèn)根結(jié)點(diǎn)。訪問(wèn)根結(jié)點(diǎn)。23ABC

18、DEFGHIJKLMNO先根遍歷：后根遍歷：層次遍歷：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO245.1.6 5.1.6 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)(Physical structure)(Physical structure)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è)偽設(shè)一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置指針指示其雙親結(jié)點(diǎn)的位置

19、。 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)示意圖252. 孩子鏈存儲(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)示意圖存儲(chǔ)結(jié)構(gòu)示意圖263. 孩

20、子兄弟鏈存儲(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è)一個(gè)數(shù)據(jù)元素域數(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)示意圖275.2.1 5.2.1 二叉樹概念二叉樹概念(Concept)(Concept)5.2

21、.2 5.2.2 二叉樹性質(zhì)二叉樹性質(zhì)(Property)(Property)5.2.3 5.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換(Transformation between binary tree and (Transformation between binary tree and tree, binary tree and forest)tree, binary tree and forest)5.2 5.2 二叉樹概念和性質(zhì)二叉樹概念和性質(zhì)(Property and concept of binary tree)(Property and concept of

22、 binary tree)285.2.1 二叉樹的概念(Binary tree)另一種樹型結(jié)構(gòu)。 Characteristic 每個(gè)結(jié)點(diǎn)至多只有二棵子樹(即不存在度大于2的結(jié)點(diǎn)) 二叉樹的子樹有左、右之分，且其次序不能任意顛倒 Basic formsA只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空29 在一棵二叉樹中在一棵二叉樹中, ,如果所有分支結(jié)點(diǎn)都有左孩子如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)結(jié)點(diǎn)和右孩子結(jié)點(diǎn), ,并且葉結(jié)點(diǎn)都集中在二叉樹的最并且葉結(jié)點(diǎn)都集中在二叉樹的最下一層下一層, ,稱為稱為滿二叉樹滿二叉樹(Full Binary Tree)(Ful

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

24、結(jié)點(diǎn)都依次排列在該層最左邊的位置上最左邊的位置上, ,稱為稱為完全二叉樹完全二叉樹(Complete Binary (Complete Binary Tree)Tree)。 深度為深度為k，有，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為深度為k的滿二叉樹中編號(hào)從的滿二叉樹中編號(hào)從1至至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 311231145891213671014151231145891267101234567123456325

25、.2.2 5.2.2 二叉樹性質(zhì)二叉樹性質(zhì)(Property)(Property) Property 1 非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加數(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)

26、以外,每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指向它向它,因此二叉樹中有：因此二叉樹中有： 總的分支數(shù)總的分支數(shù)=總結(jié)點(diǎn)數(shù)總結(jié)點(diǎn)數(shù)-1。 由上述三個(gè)等式可得：由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+133 Property 2 非空二叉樹上第非空二叉樹上第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),這里應(yīng)有這里應(yīng)有i1。 證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)， 是對(duì)的 假設(shè)對(duì)所有j(1jdata); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ PreOrder(b-lchild); PreOrder(b-rchild); A B C E F D G

27、A B C D E F G (a) (b) 先序遍歷序列： ABDGCEF5.4.2 5.4.2 二叉樹遍歷遞歸算法二叉樹遍歷遞歸算法(Recursive algorithm of binary tree traversal) 51 void InOrder(BTNode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ InOrder(b-rchild); A B C E F D G A B C D E F G (a) (b) 中序遍歷序列： DGBAEC

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

29、訪問(wèn)第2層的所有結(jié)點(diǎn)；層的所有結(jié)點(diǎn)；（3）從左到右訪問(wèn)第）從左到右訪問(wèn)第3層的所有結(jié)點(diǎn)、層的所有結(jié)點(diǎn)、第、第h層的所有結(jié)點(diǎn)。層的所有結(jié)點(diǎn)。 A B C E F D G A B C D E F G (a) (b) 層次遍歷序列： ABCDEFG54void 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é)

30、點(diǎn)指針進(jìn)入隊(duì)列根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/ while (front!=rear)/*隊(duì)列不為空隊(duì)列不為空*/ front=(front+1)%MaxSize; p=qufront;/*隊(duì)頭出隊(duì)列隊(duì)頭出隊(duì)列*/ printf(%c ,p-data);/*訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn)*/55if (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;

31、56 Example 5.2 假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ),試設(shè)計(jì)一個(gè)算法試設(shè)計(jì)一個(gè)算法,輸出一棵給定二叉樹的所有葉子結(jié)輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。點(diǎn)。 Solution：輸出一棵二叉樹的所有葉子結(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) 其他情況其他情況57 void DispLeaf(BTNode *b) if (b!=NULL)

32、 if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); 58先序遍歷非遞歸算法先序遍歷非遞歸算法 先將根結(jié)點(diǎn)進(jìn)棧，在棧不空時(shí)循環(huán)：先將根結(jié)點(diǎn)進(jìn)棧，在棧不空時(shí)循環(huán)： 出棧出棧p p，訪問(wèn)，訪問(wèn)* *p p結(jié)點(diǎn)，若右孩子不空將該右結(jié)點(diǎn)，若右孩子不空將該右孩子結(jié)點(diǎn)進(jìn)棧，若左孩子不空再將該左孩子結(jié)孩子結(jié)點(diǎn)進(jìn)棧，若左孩子不空再將該左孩子結(jié)點(diǎn)進(jìn)棧。點(diǎn)進(jìn)棧。5.4.3 5.4.3 二叉樹遍歷非遞歸算法二叉樹遍歷非遞歸算法 (Non-recursive al

33、gorithm of binary tree traversal) 59void 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-; /退棧并訪問(wèn)該結(jié)點(diǎn)退棧并訪問(wèn)該結(jié)點(diǎn) printf(%c ,p-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)入棧 to

34、p+; Sttop=p-lchild; 602. 中序遍歷非遞歸算法中序遍歷非遞歸算法 由中序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)由中序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，點(diǎn)指針，先掃描（并非訪問(wèn)）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它先掃描（并非訪問(wèn)）根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧。們一一進(jìn)棧。 然后出棧一個(gè)結(jié)點(diǎn)然后出棧一個(gè)結(jié)點(diǎn)，顯然該結(jié)點(diǎn)沒(méi)有左孩子結(jié)點(diǎn)或者，顯然該結(jié)點(diǎn)沒(méi)有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)已訪問(wèn)過(guò)（進(jìn)一步說(shuō)明該結(jié)點(diǎn)的左子樹均已訪左孩子結(jié)點(diǎn)已訪問(wèn)過(guò)（進(jìn)一步說(shuō)明該結(jié)點(diǎn)的左子樹均已訪問(wèn)），則訪問(wèn)它。問(wèn)），則訪問(wèn)它。然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，將其進(jìn)棧

35、，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，棧，再掃描該右孩子結(jié)點(diǎn)的所有左結(jié)點(diǎn)并一一進(jìn)棧，如此如此這樣，直到?？諡橹埂＿@樣，直到棧空為止。61 void InOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;p=b;while (top-1 | p!=NULL) while (p!=NULL) /掃描掃描*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); /訪問(wèn)之訪問(wèn)之 p=p-rchi

36、ld; /掃描掃描*p的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn) /end of while(top-1 | p!=NULL) 找找*b的最左下的最左下結(jié)點(diǎn)結(jié)點(diǎn)623. 后序遍歷非遞歸算法后序遍歷非遞歸算法 由后序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指由后序遍歷過(guò)程可知，采用一個(gè)棧保存需要返回的結(jié)點(diǎn)指針，先掃描根結(jié)點(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)前結(jié)點(diǎn)，然后掃描該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)并入棧，再掃描該即當(dāng)前結(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)

37、的左右孩子結(jié)點(diǎn)均訪問(wèn)后再訪問(wèn)該結(jié)點(diǎn)，如此這樣，直到?？諡橹?。均訪問(wèn)后再訪問(wèn)該結(jié)點(diǎn)，如此這樣，直到?？諡橹埂?難點(diǎn)：難點(diǎn)：如何判斷一個(gè)結(jié)點(diǎn)如何判斷一個(gè)結(jié)點(diǎn)*b的右孩子結(jié)點(diǎn)已訪問(wèn)過(guò)的右孩子結(jié)點(diǎn)已訪問(wèn)過(guò)，為此，為此用用p保存剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)（初值為保存剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)（初值為NULL），若），若b-rchild=p成立（成立（在后序遍歷中，在后序遍歷中，*b的右孩子結(jié)點(diǎn)一定剛好在的右孩子結(jié)點(diǎn)一定剛好在*b之前訪之前訪問(wèn)問(wèn)），說(shuō)明），說(shuō)明*b的左右子樹均已訪問(wèn)，現(xiàn)在應(yīng)訪問(wèn)的左右子樹均已訪問(wèn)，現(xiàn)在應(yīng)訪問(wèn)*b。 63void PostOrder2(BTNode *b)BTNode *StMaxSize;

38、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è)已訪問(wèn)的結(jié)點(diǎn)指向棧頂結(jié)點(diǎn)的前一個(gè)已訪問(wèn)的結(jié)點(diǎn) flag=1; /設(shè)置設(shè)置b的訪問(wèn)標(biāo)記為已訪問(wèn)過(guò)的訪問(wèn)標(biāo)記為已訪問(wèn)過(guò)找最左下結(jié)點(diǎn)找最左下結(jié)點(diǎn)64 while (top!=-1 & flag=1) b=Sttop; /取出當(dāng)前的棧頂元素取出當(dāng)前的棧頂元素 if (b-rchild=p) printf(%c ,b-data);/訪問(wèn)訪問(wèn)*b

39、結(jié)點(diǎn)結(jié)點(diǎn)top-;p=b;/p指向則被訪問(wèn)的結(jié)點(diǎn)指向則被訪問(wèn)的結(jié)點(diǎn) else b=b-rchild; /b指向右孩子結(jié)點(diǎn)指向右孩子結(jié)點(diǎn) flag=0;/設(shè)置未被訪問(wèn)的標(biāo)記設(shè)置未被訪問(wèn)的標(biāo)記 /end of while (top!=-1 & flag=1) while (top!=-1); b b的右孩子不存在或已訪問(wèn)過(guò)的右孩子不存在或已訪問(wèn)過(guò)65 從上述過(guò)程可知，棧中保存的是當(dāng)前從上述過(guò)程可知，棧中保存的是當(dāng)前結(jié)點(diǎn)結(jié)點(diǎn)*b的所有祖先結(jié)點(diǎn)（均未訪問(wèn)過(guò)）。的所有祖先結(jié)點(diǎn)（均未訪問(wèn)過(guò)）。 例如，書中例子求一個(gè)結(jié)點(diǎn)的所有祖例如，書中例子求一個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。先結(jié)點(diǎn)。665.5.1 5.5.

40、1 二叉樹的基本運(yùn)算概述二叉樹的基本運(yùn)算概述（Basic operations of binary tree)5.5.2 5.5.2 二叉樹的基本運(yùn)算算法實(shí)現(xiàn)二叉樹的基本運(yùn)算算法實(shí)現(xiàn)(Algorithm implementation of basic operations)5.5 5.5 二叉樹的基本運(yùn)算及其實(shí)現(xiàn)二叉樹的基本運(yùn)算及其實(shí)現(xiàn)(Algorithm implementation and basic operations (Algorithm implementation and basic operations of binary tree)of binary tree)67歸納起來(lái)歸

41、納起來(lái),二叉樹有以下基本運(yùn)算：二叉樹有以下基本運(yùn)算： (1)創(chuàng)建二叉樹創(chuàng)建二叉樹CreateBTNode(*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)。5.5.1 5.5.1

42、 二叉樹的基本運(yùn)算概述二叉樹的基本運(yùn)算概述（Basic operations of binary tree)68 (4)求高度求高度BTNodeDepth(*b)：求二叉樹求二叉樹b的高度。的高度。若二叉樹為空若二叉樹為空,則其高度為則其高度為0；否則；否則,其高度等于左子其高度等于左子樹與右子樹中的最大高度加樹與右子樹中的最大高度加l。 (5)輸出二叉樹輸出二叉樹DispBTNode(*b)：以括號(hào)表示法以括號(hào)表示法輸出一棵二叉樹。輸出一棵二叉樹。69 (1) 創(chuàng)建二叉樹創(chuàng)建二叉樹CreateBTNode(*b,*str) 用用ch掃描采用括號(hào)表示法表示二叉樹的字符串。分掃描采用括號(hào)表示法表

43、示二叉樹的字符串。分以下幾種情況：以下幾種情況： 若若ch=(：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧進(jìn)棧,并置并置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)；5.5.2 5.5.2 二叉樹的基本運(yùn)算算法實(shí)現(xiàn)二叉樹的基本運(yùn)算算法實(shí)現(xiàn)(Algorithm implementation of basic operations)70 其他情

44、況其他情況,表示要?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)作為棧中結(jié)點(diǎn)的左孩表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)子結(jié)點(diǎn),當(dāng)當(dāng)k=2時(shí)時(shí),表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到右孩子結(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

45、)。71 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!=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)*

46、/72 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) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+;ch=strj; 73 例如例如,對(duì)于括號(hào)表示串對(duì)于括號(hào)表示串A(B(D(,G),C(E,F),建立建立二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程如下表所示。二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)

47、程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素A建立建立A結(jié)點(diǎn)結(jié)點(diǎn),b指向該結(jié)點(diǎn)指向該結(jié)點(diǎn)(A為樹的根）為樹的根） 空空(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)的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)AB74ch算法執(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)退棧一次退棧一

48、次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=2AC75ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素F建立建立F結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為C結(jié)點(diǎn)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)AC)退棧一次退棧一次A)退棧一次退棧一次空空ch掃描完畢掃描完畢算法結(jié)束算法結(jié)束 A B C D E F G 生成的二叉樹生成的二叉樹76 (2) 查找結(jié)點(diǎn)查找結(jié)點(diǎn)FindNode(*b,x) 采用采用先序遍歷先序遍歷遞歸算法查找

49、值為遞歸算法查找值為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(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); 77 (3) 找孩子結(jié)點(diǎn)找孩子結(jié)點(diǎn)LchildNode(p)和和RchildNode(p) 直接

50、返回直接返回*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; 78(4) 求高度求高度BTNodeDepth(*b)求二叉樹的高度的遞歸模型求二叉樹的高度的遞歸模型f()如下：如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情況其他情況對(duì)應(yīng)的算法如下：對(duì)應(yīng)的算法如下：79int BTNodeDepth(BTNo

51、de *b) int lchilddep, rchilddep; if (b=NULL) return(0); /*空樹的高度為空樹的高度為0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子樹的高度為求左子樹的高度為lchilddep*/ rchilddep=BTNodeDepth(b-rchild);/*求右子樹的高度為求右子樹的高度為rchilddep*/ return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); 80 (5) 輸出二叉樹輸出二叉樹DispBTNode(*b) 其過(guò)程是：其過(guò)程

52、是：對(duì)于非空二叉樹對(duì)于非空二叉樹b,先輸出其元素值先輸出其元素值,當(dāng)當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí),輸出一個(gè)輸出一個(gè)“(”符號(hào)符號(hào),然后遞歸處理左子樹然后遞歸處理左子樹,輸出一個(gè)輸出一個(gè)“,”符號(hào)符號(hào),遞歸處理右遞歸處理右子樹子樹,最后輸出一個(gè)最后輸出一個(gè)“)”符號(hào)。符號(hào)。 對(duì)應(yīng)的遞歸算法如下：對(duì)應(yīng)的遞歸算法如下：81 void DispBTNode(BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild

53、);/*遞歸處理左子樹遞歸處理左子樹*/ if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/*遞歸處理右子樹遞歸處理右子樹*/ printf(); 82 Example 5.5 假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu),設(shè)計(jì)設(shè)計(jì)一個(gè)算法輸出從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。一個(gè)算法輸出從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。 解：解：這里用層次遍歷方法這里用層次遍歷方法,設(shè)計(jì)的隊(duì)列為非循環(huán)順設(shè)計(jì)的隊(duì)列為非循環(huán)順序隊(duì)列序隊(duì)列(類似于第類似于第3章章3.2.4小節(jié)中求解迷宮問(wèn)題時(shí)使用小節(jié)中求解迷宮問(wèn)題時(shí)使用的隊(duì)列的隊(duì)列), 將所有已掃描過(guò)的

54、結(jié)點(diǎn)指針進(jìn)隊(duì)將所有已掃描過(guò)的結(jié)點(diǎn)指針進(jìn)隊(duì),并在隊(duì)列中并在隊(duì)列中保存雙親結(jié)點(diǎn)的位置。保存雙親結(jié)點(diǎn)的位置。 當(dāng)找到一個(gè)葉子結(jié)點(diǎn)時(shí)當(dāng)找到一個(gè)葉子結(jié)點(diǎn)時(shí),在隊(duì)列中通過(guò)雙親結(jié)點(diǎn)的在隊(duì)列中通過(guò)雙親結(jié)點(diǎn)的位置輸出該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。對(duì)應(yīng)的算法如位置輸出該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。對(duì)應(yīng)的算法如下：下： 83void AllPath(BTNode *b) struct snode BTNode *node;/*存放當(dāng)前結(jié)點(diǎn)指針存放當(dāng)前結(jié)點(diǎn)指針*/ int parent;/*存放雙親結(jié)點(diǎn)在隊(duì)列中的位置存放雙親結(jié)點(diǎn)在隊(duì)列中的位置*/ qMaxSize;/*定義順序隊(duì)列定義順序隊(duì)列*/ int front,rea

55、r,p;/*定義隊(duì)頭和隊(duì)尾指針定義隊(duì)頭和隊(duì)尾指針*/ front=rear=-1; /*置隊(duì)列為空隊(duì)列置隊(duì)列為空隊(duì)列*/ rear+;qrear.node=b; /*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/ qrear.parent=-1; /*根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)*/84 while (frontlchild=NULL & b-rchild=NULL) printf(%c到根結(jié)點(diǎn)路徑到根結(jié)點(diǎn)路徑:,b-data); p=front; while (qp.parent!=-1) printf(%c-,qp.node-data); p=qp.parent; printf(

56、%cn,qp.node-data); if (b-lchild!=NULL) /*左孩子結(jié)點(diǎn)入隊(duì)列左孩子結(jié)點(diǎn)入隊(duì)列*/ rear+;qrear.node=b-lchild; qrear.parent=front; if (b-rchild!=NULL)/*右孩子結(jié)點(diǎn)入隊(duì)列右孩子結(jié)點(diǎn)入隊(duì)列*/ rear+; qrear.node=b-rchild; qrear.parent=front; /*end of while*/ 85 同一棵二叉樹具有惟一先序序列、中序序列和同一棵二叉樹具有惟一先序序列、中序序列和后序序列后序序列,但不同的二叉樹可能具有相同的先序序列、但不同的二叉樹可能具有相同的先序序

57、列、中序序列和后序序列。中序序列和后序序列。 例如例如, 教材中教材中P176 如圖如圖7.11所示的所示的5棵二叉樹棵二叉樹,先序序列都為先序序列都為ABC。 如圖如圖7.12所示的所示的5棵二叉樹棵二叉樹,中序序列都為中序序列都為ACB。 如圖如圖7.13所示的所示的5棵二叉樹棵二叉樹,后序序列都為后序序列都為CBA。 5.6 5.6 二叉樹的構(gòu)造二叉樹的構(gòu)造(Construction of binary tree)(Construction of binary tree)86 顯然顯然,僅由一個(gè)先序序列僅由一個(gè)先序序列(或中序序列、后序序列或中序序列、后序序列),無(wú)法確定這棵二叉樹的樹形

58、。無(wú)法確定這棵二叉樹的樹形。 如果同時(shí)知道一棵二叉樹的先序序列和中序序列如果同時(shí)知道一棵二叉樹的先序序列和中序序列,或者同時(shí)知道中序序列和后序序列或者同時(shí)知道中序序列和后序序列,就能確定這棵二叉就能確定這棵二叉樹。樹。 但是，同時(shí)知道先序序列和后序序列仍不能確定二但是，同時(shí)知道先序序列和后序序列仍不能確定二叉樹的樹形。如圖叉樹的樹形。如圖7.11和和7.13中除第一棵外的中除第一棵外的4棵二叉棵二叉樹先序序列都是樹先序序列都是ABC，后序序列都是，后序序列都是CBA。 87Theorem 5.1Theorem 5.1：任何：任何n(n0)n(n0)個(gè)不同結(jié)點(diǎn)的二又樹個(gè)不同結(jié)點(diǎn)的二又樹, ,都可

59、由它的中都可由它的中序序列和先序序列惟一地確定。序序列和先序序列惟一地確定。 采用數(shù)學(xué)歸納法證明。采用數(shù)學(xué)歸納法證明。 當(dāng)當(dāng)n=0時(shí)時(shí),二叉樹為空二叉樹為空,結(jié)論正確。結(jié)論正確。 假設(shè)結(jié)點(diǎn)數(shù)小于假設(shè)結(jié)點(diǎn)數(shù)小于n的任何二叉樹的任何二叉樹,都可以由其先序序列和中序都可以由其先序序列和中序序列惟一地確定。序列惟一地確定。 已知某棵二叉樹具有已知某棵二叉樹具有n(n0)個(gè)不同結(jié)點(diǎn)個(gè)不同結(jié)點(diǎn),其先序序列是其先序序列是a0a1an-1；中序序列是；中序序列是b0b1bk-1bkbk+1bn-1。 因?yàn)樵谙刃虮闅v過(guò)程中因?yàn)樵谙刃虮闅v過(guò)程中,訪問(wèn)根結(jié)點(diǎn)后訪問(wèn)根結(jié)點(diǎn)后,緊跟著遍歷左子樹緊跟著遍歷左子樹,最最后再

60、遍歷右子樹。所以后再遍歷右子樹。所以,a0必定是二叉樹的根結(jié)點(diǎn)必定是二叉樹的根結(jié)點(diǎn),而且而且a0必然在必然在中序序列中出現(xiàn)。中序序列中出現(xiàn)。也就是說(shuō)也就是說(shuō),在中序序列中必有某個(gè)在中序序列中必有某個(gè)bk(0kn-1)就是根結(jié)點(diǎn)就是根結(jié)點(diǎn)a0。88 由于由于bk是根結(jié)點(diǎn)是根結(jié)點(diǎn),而在中序遍歷過(guò)程中而在中序遍歷過(guò)程中,先遍歷左子先遍歷左子樹樹,再訪問(wèn)根結(jié)點(diǎn)再訪問(wèn)根結(jié)點(diǎn),最后再遍歷右子樹。最后再遍歷右子樹。所以在中序序列所以在中序序列中中,b0b1bk-1必是根結(jié)點(diǎn)必是根結(jié)點(diǎn)bk(也就是也就是a0)左子樹的中序序左子樹的中序序列列,即即bk的左子樹有的左子樹有k個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(注意注意,k=0表示結(jié)點(diǎn)表示結(jié)點(diǎn)bk沒(méi)有沒(méi)有左子樹。左子樹。