數(shù)據(jù)結(jié)構(gòu)陳d5 2樣式編輯母版文

1、第 2 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 樹是樹是 n (n0) 個(gè)結(jié)點(diǎn)的有限集合，在任意一個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：棵非空樹中： (1)有且僅有一個(gè)稱為根有且僅有一個(gè)稱為根root的結(jié)點(diǎn)。的結(jié)點(diǎn)。 (2)當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為若干個(gè)互不相時(shí)，其余結(jié)點(diǎn)可分為若干個(gè)互不相交的集合，且這些集合中的每一集合本身又是交的集合，且這些集合中的每一集合本身又是一棵樹，稱為根的子樹。一棵樹，稱為根的子樹。樹是遞歸結(jié)構(gòu)，樹的定義是遞歸定義。樹是遞歸結(jié)構(gòu)，樹的定義是遞歸定義。J JI IA AC CB BD DH HG GF FE E第 3 頁6.1 6.1 樹的定義與基本

2、術(shù)語樹的定義與基本術(shù)語 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R若若D為空集，則稱為空樹。為空集，則稱為空樹。否則：否則：(1) D中存在唯一稱為根的數(shù)據(jù)元素中存在唯一稱為根的數(shù)據(jù)元素root；(2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為 m ( m0 ) 個(gè)互不相交的有限集個(gè)互不相交的有限集T1, T2, , Tm，其中每，其中每一棵子集本身又是一棵樹，稱為根一棵子集本身又是一棵樹，稱為根root的子樹的子樹。第 4 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語例：有棵樹例：有棵樹 T。 T= A,B,C,D

3、,E,F,G, H,I,J A A是根，其余結(jié)點(diǎn)劃分為是根，其余結(jié)點(diǎn)劃分為3 3個(gè)互不相交的集合：個(gè)互不相交的集合： T1= B,E,F T2= C,G T3= D,H,I,J T1= B,E,F T2= C,G T3= D,H,I,J 每一集合又都是一棵樹，它們是根每一集合又都是一棵樹，它們是根A A的子樹。的子樹。 對(duì)于對(duì)于T1T1，B B 是根，其余結(jié)點(diǎn)可以劃分為兩個(gè)互是根，其余結(jié)點(diǎn)可以劃分為兩個(gè)互不相交的集合：不相交的集合： T11= E T12= F T11,T12 T11= E T12= F T11,T12是是B B的子樹。的子樹。J JI IA AC CB BD DH HG GF

4、 FE E第 5 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 2）除根外，其余結(jié)點(diǎn)有且僅一個(gè)前趨；）除根外，其余結(jié)點(diǎn)有且僅一個(gè)前趨； 3）樹中的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后繼；）樹中的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后繼； 4）除根之外的其它結(jié)點(diǎn)，都存在唯一一條）除根之外的其它結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑；從根到該結(jié)點(diǎn)的路徑； 5）樹是一種分支結(jié)構(gòu)。）樹是一種分支結(jié)構(gòu)。l從邏輯結(jié)構(gòu)看從邏輯結(jié)構(gòu)看l 1）樹中只有根）樹中只有根結(jié)點(diǎn)沒有前趨；結(jié)點(diǎn)沒有前趨；J JI IA AC CB BD DH HG GF FE E第 6 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的應(yīng)用樹的

5、應(yīng)用家族樹家族樹血統(tǒng)樹血統(tǒng)樹( 二叉樹二叉樹 )第 7 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的應(yīng)用樹的應(yīng)用l 常用的數(shù)據(jù)組織形式：計(jì)算機(jī)的文件系常用的數(shù)據(jù)組織形式：計(jì)算機(jī)的文件系統(tǒng)。統(tǒng)。l 不論是不論是DOSDOS文件系統(tǒng)還是文件系統(tǒng)還是windowwindow文件系統(tǒng)，文件系統(tǒng)，所有的文件都是用樹的形式進(jìn)行組織。所有的文件都是用樹的形式進(jìn)行組織。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾n1 n1 文件夾文件夾nm nm 文件文件n1 n1 文件文件nknkC C第 8 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的

6、應(yīng)用樹的應(yīng)用lDNS Name Space.DNS Name Space.“.”.comeducnedubittshuapku cs ee ss中國教育和科研網(wǎng)教育和科研網(wǎng)北理工校園網(wǎng)北理工校園網(wǎng)第 9 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的表示樹的表示l 1）圖示表示）圖示表示l 2）二元組表示）二元組表示l 3）文氏圖表示）文氏圖表示l 4）廣義表表示）廣義表表示l 5）凹入表示法（類似書的目錄）凹入表示法（類似書的目錄）J JI IA AC CB BD DH HG GF FE E第 10 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語T = A，B，C，D，

7、E，F(xiàn)，G，H，I，J R = , , , , , , , , l樹的表示樹的表示l2）二元組表示）二元組表示J JI IA AC CB BD DH HG GF FE E第 11 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的表示樹的表示l3）文氏圖表示）文氏圖表示ABCDEFGHIJMKLABCDEFGHIJMKL第 12 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 假設(shè)樹的根為假設(shè)樹的根為rootroot，子樹為，子樹為T1,T2,TnT1,T2,Tn，與該樹對(duì)應(yīng)的廣義表為與該樹對(duì)應(yīng)的廣義表為L L，則：，則：L=(L=(原子原子( (子表子表1,1,子表子表2,

8、 , 2, , 子表子表n)n)，其中原子對(duì)應(yīng)，其中原子對(duì)應(yīng) root root，子，子表表 i(1i=n) i(1i=n) 對(duì)應(yīng)對(duì)應(yīng) Ti Ti。l樹的表示樹的表示l4）廣義表表示）廣義表表示( A ( B(E,F), C, D) )( A ( B(E,F), C, D) )ABCDEFT1T3T2樹根樹根(A,(B,(E),(F),(C),(D)(A,(B,(E),(F),(C),(D)第 13 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的表示樹的表示l5）凹入表示）凹入表示ABCDEFGHIJMKLA A B B E E F F K K L L C C G G D D H

9、 H I I J J M M第 14 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :樹的度樹的度: :葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)元素?cái)?shù)據(jù)元素+ +若干指向子樹的分支若干指向子樹的分支分支的個(gè)數(shù)分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM有序樹：子樹之間有明確的次序關(guān)系。有序樹：子樹之間有明確的次序關(guān)系。無序樹：子樹之間沒有順序要求。無序樹：子樹之間沒有順序要求。第 15 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語( (從根到結(jié)點(diǎn)的從根到結(jié)點(diǎn)的

10、) )路徑：路徑：孩子結(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)所由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成經(jīng)分支和結(jié)點(diǎn)構(gòu)成假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1 1，第，第k k 層層結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)，在結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)，在 k+1 k+1 層層樹中葉子結(jié)點(diǎn)所在的最大層次樹中葉子結(jié)點(diǎn)所在的最大層次ABCDEFGHIJMKL第 16 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語任何一棵非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組Tree = （root，F(xiàn)） 其中：其

11、中：root 稱為根結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，F(xiàn) 稱為子樹森林。稱為子樹森林。森林：森林： m（m0）棵互不相交的樹的集合。）棵互不相交的樹的集合。ArootBEFKLCGDHIJMF第 17 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的基本操作樹的基本操作l1) InitTree( &T );1) InitTree( &T );l 構(gòu)造空樹構(gòu)造空樹 T T。l2) DestroyTree( &T );2) DestroyTree( &T );l 銷毀樹銷毀樹 T T。l3) CreateTree( &T, definition );3) Cre

12、ateTree( &T, definition );l 按按 definition definition 構(gòu)造樹構(gòu)造樹 T T。l4) ClearTree( &T );4) ClearTree( &T );l 將樹將樹 T T 清空。清空。l5) TreeEmpty( T );5) TreeEmpty( T );l 若樹若樹 T T 為空，返回為空，返回 TURE TURE，否則返回，否則返回 FALSEFALSE。l6) TreeDepth( T );6) TreeDepth( T );l 返回樹返回樹 T T 的深度。的深度。第 18 頁6.1 6.1 樹的定義與基

13、本術(shù)語樹的定義與基本術(shù)語l樹的基本操作樹的基本操作l7) Root( T );7) Root( T );l 返回返回 T T 的根結(jié)點(diǎn)。的根結(jié)點(diǎn)。l8) Value( T, &cur_e );8) Value( T, &cur_e );l 返回返回 T T 樹中樹中 cur_e cur_e 結(jié)點(diǎn)的值。結(jié)點(diǎn)的值。l9) Assign( T, cur_e, value );9) Assign( T, cur_e, value );l 將將 T T 樹中結(jié)點(diǎn)樹中結(jié)點(diǎn) cur_e cur_e 的值賦值的值賦值為為valuevalue。l10) Parent( T, cur_e );10

14、) Parent( T, cur_e );l 返回返回 T T 樹樹 cur_e cur_e 結(jié)點(diǎn)的雙親。結(jié)點(diǎn)的雙親。l11) LeftChild( T, cur_e );11) LeftChild( T, cur_e );l 返回返回 T T 樹樹 cur_e cur_e 結(jié)點(diǎn)的最左孩結(jié)點(diǎn)的最左孩子。子。第 19 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的基本操作樹的基本操作l12) RightSibling( T, cur_e );12) RightSibling( T, cur_e );l 返回返回 T T 樹樹 cur_e cur_e 結(jié)點(diǎn)的右兄弟。結(jié)點(diǎn)的右兄弟。l1

15、3) InsertChild( &T, &p, i, c );13) InsertChild( &T, &p, i, c );l 將將 c c 插入到樹插入到樹 T T 中中 p p 所指向的第所指向的第 i i 棵子樹中。棵子樹中。l14) DeleteChild( &T, &p, i );14) DeleteChild( &T, &p, i );l 刪除樹刪除樹 T T 中中 p p 所指向的第所指向的第 i i 棵子樹?？米訕洹15) TraverseTree( T, Visit( ) );15) TraverseTree

16、( T, Visit( ) );l 按某種次序?qū)Π茨撤N次序?qū)?T T 樹的每個(gè)結(jié)點(diǎn)調(diào)用函樹的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)數(shù)Visit( )Visit( )一次且至多一次。也稱為按照某一次且至多一次。也稱為按照某種次序?qū)溥M(jìn)行遍歷。種次序?qū)溥M(jìn)行遍歷。第 20 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼)

17、)其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )第 21 頁6.2 6.2 二叉樹二叉樹l定義定義l 一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。的、互不相交的二叉樹組成。第 22 頁6.2 6.2 二叉樹二叉樹。第 23 頁6.2 6.2 二叉樹二叉樹l定義定義ABCDEFGHK根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹第 24 頁6.2 6.2 二叉樹二叉樹NLRLRNNNl二叉樹的五種基本形態(tài)二

18、叉樹的五種基本形態(tài)空樹空樹只有只有根結(jié)點(diǎn)根結(jié)點(diǎn)只有只有左子樹左子樹只有只有右子樹右子樹左右子樹左右子樹均非空均非空第 25 頁6.2 6.2 二叉樹二叉樹 (a) (a)、(b)(b)是不同的二叉樹是不同的二叉樹(a)(a)的左子樹有四個(gè)結(jié)點(diǎn)，的左子樹有四個(gè)結(jié)點(diǎn)，(b)(b)的左子樹有兩個(gè)結(jié)點(diǎn)的左子樹有兩個(gè)結(jié)點(diǎn)(a)(a) A A G G E E D D B B C C F F(b)(b) A A F F G G E E D D C C B B第 26 頁6.2 6.2 二叉樹二叉樹 甲甲 乙乙甲甲 乙乙 甲甲 乙乙甲甲 乙乙 甲甲 乙乙甲甲 乙乙 甲甲 乙乙 甲甲 乙乙 甲甲 乙乙甲甲 乙甲

19、乙甲 乙乙 甲甲 乙甲乙甲 乙乙開始開始比賽規(guī)則：開局連贏兩局或五局三勝比賽規(guī)則：開局連贏兩局或五局三勝第 27 頁6.2 6.2 二叉樹二叉樹e ed dc cb bf fa a* */ /- - -+ +a + b a + b * * ( c d ) e / ( c d ) e / f fGAFEDCB描述結(jié)點(diǎn)的層次關(guān)系描述結(jié)點(diǎn)的層次關(guān)系第 28 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)1：l在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( i1)。i=1i=1：最多：最多1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)i=2i=2：最多：最多2 2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)i=3i=3：最多：最多4 4個(gè)

20、結(jié)點(diǎn)個(gè)結(jié)點(diǎn)GAFEDCB第 29 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)1：l在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)。用歸納法證明：用歸納法證明： 歸納基：歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)，層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2 i-1 = 2 0 = 1；假設(shè)對(duì)所有的假設(shè)對(duì)所有的 j, 1j i，命題成立；，命題成立；第第 i-1 層至多有層至多有 2i-2個(gè)結(jié)點(diǎn)，由于個(gè)結(jié)點(diǎn)，由于二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第則第 i 層結(jié)點(diǎn)數(shù)至多層結(jié)點(diǎn)數(shù)至多= 2i-22 = 2i-1

21、。第 30 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)2：l深度為深度為k (k1)的二叉樹上至多含的二叉樹上至多含2k-1個(gè)結(jié)個(gè)結(jié)點(diǎn)。點(diǎn)。證明：證明： 基于性質(zhì)基于性質(zhì)1，深度為，深度為 k 的二叉樹上的結(jié)點(diǎn)的二叉樹上的結(jié)點(diǎn)數(shù)至多為：數(shù)至多為：20 + 21 + . + 2k-1 = 2k - 1 l推論：推論：ln個(gè)結(jié)點(diǎn)的二叉樹，高個(gè)結(jié)點(diǎn)的二叉樹，高 h至少是至少是 log2n +1 。第 31 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)3：l 對(duì)任何一棵二叉樹，若它含有對(duì)任何一棵二叉樹，若它含有 n0 個(gè)個(gè)葉子結(jié)點(diǎn)、葉子結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)的結(jié)點(diǎn)，則必存在關(guān)系式：

22、系式：n0 = n2+1證明：證明：設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù)：二叉樹上結(jié)點(diǎn)總數(shù)：n = n0 + n1 + n2又又 二叉樹上分支總數(shù)二叉樹上分支總數(shù) b =從結(jié)點(diǎn)發(fā)出的邊：從結(jié)點(diǎn)發(fā)出的邊： b = n1 + 2n2而而 除根結(jié)點(diǎn)外除根結(jié)點(diǎn)外 n 個(gè)點(diǎn)需要個(gè)點(diǎn)需要 n-1 條邊連接：條邊連接：b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1第 32 頁6.2 6.2 二叉樹二叉樹l兩類特殊的二叉樹兩類特殊的二叉樹滿二叉樹：指的是深滿二叉樹：指的是深度為度為 k 且含有且含有 2k-1 個(gè)個(gè)結(jié)點(diǎn)的二叉樹。結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所完全二叉樹：樹中所含的

23、含的 n 個(gè)結(jié)點(diǎn)和滿二個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為叉樹中編號(hào)為 1 至至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij第 33 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)4：l具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。證明：證明：設(shè)設(shè) 完全二叉樹的深度為完全二叉樹的深度為 k 則根據(jù)則根據(jù) 性質(zhì)性質(zhì)2 得得 2k-1 n 2k 即即 k-1 log2 n n，則該結(jié)點(diǎn)無左孩子；否，則該結(jié)點(diǎn)無左孩子；否則，編號(hào)為則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；l(3) 若若 2i+1n，則該

24、結(jié)點(diǎn)無右孩子結(jié)，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)；否則，編號(hào)為點(diǎn)；否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。點(diǎn)。第 35 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)5： i/2 ii+12i2i+12i+22i+3(a) i 和和 i+1 結(jié)點(diǎn)在同一層結(jié)點(diǎn)在同一層 i+12i+22i+3i2i2i+1(b) i 和和 i+1 結(jié)點(diǎn)不在同一層結(jié)點(diǎn)不在同一層第 36 頁二叉樹二叉樹基本概念基本概念l性質(zhì)性質(zhì)5：l在此過程中，可以從（在此過程中，可以從（2）和（）和（3）推）推出（出（1），所以先證明（），所以先證明（2）和（）和（3）。）。l對(duì)于對(duì)于i1，由完全二叉樹的定義，其，由完全二叉樹

25、的定義，其左孩子是結(jié)點(diǎn)左孩子是結(jié)點(diǎn)2，若，若2n，即不存在結(jié)點(diǎn)，即不存在結(jié)點(diǎn)2，此，此是，結(jié)點(diǎn)是，結(jié)點(diǎn)i無孩子。結(jié)點(diǎn)無孩子。結(jié)點(diǎn)i的由孩子也只能是結(jié)的由孩子也只能是結(jié)點(diǎn)點(diǎn)3，若結(jié)點(diǎn)，若結(jié)點(diǎn)3不存在，即不存在，即3n，此時(shí)結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)i無無右孩子。右孩子。l對(duì)于對(duì)于i1，可分為兩種情況：，可分為兩種情況：l（1）設(shè)第）設(shè)第j（1=jn，則無左孩子：則無左孩子：第 37 頁二叉樹二叉樹基本概念基本概念l性質(zhì)性質(zhì)5：l其右孩子必定為第其右孩子必定為第j1層的第二個(gè)結(jié)層的第二個(gè)結(jié)點(diǎn)，編號(hào)為點(diǎn)，編號(hào)為2i1。若。若2i+1n，則無右孩子。，則無右孩子。l（2）假設(shè)第）假設(shè)第j（1=j=log2n)層上

26、層上的某個(gè)結(jié)點(diǎn)編號(hào)為的某個(gè)結(jié)點(diǎn)編號(hào)為i（2e(j-1)=i=2ej-1),且且2i11時(shí)，如果時(shí)，如果i為左孩子，即為左孩子，即2（i/2)=i,則則i/2是是i的雙親；如果的雙親；如果i為右孩子，為右孩子，i2p+1,i的雙親應(yīng)的雙親應(yīng)為為p，p（i1）/2=i/2. 證畢。證畢。第 38 頁6.2 6.2 二叉樹二叉樹l二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)l1. 二叉樹的順序結(jié)構(gòu)二叉樹的順序結(jié)構(gòu)l對(duì)于完全二叉樹，采用一組連續(xù)的內(nèi)存單對(duì)于完全二叉樹，采用一組連續(xù)的內(nèi)存單元，按編號(hào)順序依次存儲(chǔ)完全二叉樹的結(jié)點(diǎn)。元，按編號(hào)順序依次存儲(chǔ)完全二叉樹的結(jié)點(diǎn)。 1 2 3 4 5 6 7 m-1 1 2 3

27、 4 5 6 7 m-1 A B C D E F A B C D E FAFEDCB1 12 23 34 45 56 6第 39 頁6.2 6.2 二叉樹二叉樹 對(duì)于一棵一般的二叉樹，如果補(bǔ)齊構(gòu)成完全對(duì)于一棵一般的二叉樹，如果補(bǔ)齊構(gòu)成完全二叉樹所缺少的那些結(jié)點(diǎn)，便對(duì)二叉樹的結(jié)點(diǎn)二叉樹所缺少的那些結(jié)點(diǎn)，便對(duì)二叉樹的結(jié)點(diǎn)進(jìn)行編號(hào)。進(jìn)行編號(hào)。 A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 91010第 40 頁6.2 6.2 二叉樹二叉樹 將二叉樹原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單將二叉樹原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單元元“相應(yīng)相應(yīng)”的位置上。的位

28、置上。 1 2 3 4 5 6 7 8 9 10 m-1 1 2 3 4 5 6 7 8 9 10 m-1 A B C D E 0 F 0 0 G A B C D E 0 F 0 0 G A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 91010第 41 頁6.2 6.2 二叉樹二叉樹 對(duì)于一些對(duì)于一些“退化二叉樹退化二叉樹”，順序存儲(chǔ)，順序存儲(chǔ)結(jié)構(gòu)存在突出缺點(diǎn)：比較浪費(fèi)空間。結(jié)構(gòu)存在突出缺點(diǎn)：比較浪費(fèi)空間。A BCBT7ABCDBT15DACBACB第 42 頁6.2 6.2 二叉樹二叉樹2. 二叉鏈表二叉鏈表 二叉鏈表中每個(gè)結(jié)點(diǎn)包含

29、三個(gè)域：數(shù)據(jù)域、二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域。左指針域、右指針域。typedef struct BiTNodetypedef struct BiTNode ElemType data; ElemType data; struct BiTNode struct BiTNode * * lchild, lchild, * * rchild; rchild; BiTNode, BiTNode, * * BiTree; BiTree;數(shù)據(jù)域數(shù)據(jù)域指針域指針域指針域指針域結(jié)點(diǎn)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)數(shù)據(jù)元素指向右孩子指向右孩子指向左孩子指向左孩子第 43 頁6.2 6.2 二叉樹

30、二叉樹二叉樹的二叉鏈表表示二叉樹的二叉鏈表表示AFEDCB二叉鏈表圖示二叉鏈表圖示DABC E E F F T T第 44 頁6.2 6.2 二叉樹二叉樹3. 三叉鏈表三叉鏈表 三叉鏈表中每個(gè)結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、三叉鏈表中每個(gè)結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域。雙親指針域、左指針域、右指針域。結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：parent lchild data rchildtypedef struct BiTNodetypedef struct BiTNode ElemType data; ElemType data; struct BiTNode struct BiTNode *

31、 * lchild, lchild, * * rchild; rchild; struct BiTNode struct BiTNode * * parent; parent; BiTNode, BiTNode,* *BiTree;BiTree;第 45 頁6.2 6.2 二叉樹二叉樹二叉樹的三叉鏈表表示二叉樹的三叉鏈表表示rootADEBCF CEFDAB第 46 頁6.2 6.2 二叉樹二叉樹4. 靜態(tài)二叉鏈表靜態(tài)二叉鏈表 采用數(shù)組存貯。采用數(shù)組存貯。孩子結(jié)點(diǎn)在數(shù)組中孩子結(jié)點(diǎn)在數(shù)組中的位置。用的位置。用-1-1表示表示無左孩子或右孩子無左孩子或右孩子2 2 A 1 A 13 33 C 3

32、C -1-14 45 B 5 B -1-15 5-1 E -1 E -1-16 6-1 F -1 F -1-17 7-1 D -1 D 4 40 01 12 23 34 45 56 6Lchild data rchildLchild data rchildroot = 0AFEDCB第 47 頁6.2 6.2 二叉樹二叉樹4. 靜態(tài)二叉鏈表靜態(tài)二叉鏈表 typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int lchild, rchild ; BNode typedef struct BTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BNode nodes MAX

33、_TREE_SIZE ; int num_node; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BTree;第 48 頁6.2 6.2 二叉樹二叉樹5. 雙親鏈表雙親鏈表結(jié)點(diǎn)結(jié)點(diǎn)LRTag data parentGAFEDCB B 2 B 2 C 2 C 2 A -1 A -1 D 0 D 0 E 0 E 0 F 1 F 1 G 4 G 4 0 01 12 23 34 45 56 6 data parentLRLRLL第 49 頁6.2 6.2 二叉樹二叉樹5. 雙親鏈表雙親鏈表 typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemTyp

34、e data; int parent; / 指向雙親的指針指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodes MAX_TREE_SIZE ; int num_node; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BPTree;第 50 頁6.2 6.2 二叉樹二叉樹l創(chuàng)建二叉樹創(chuàng)建二叉樹l方法方法1：根據(jù)樹的廣義表表示生成二叉樹。：根據(jù)樹的廣義表表示生成二叉樹。l方法方法2：按完全二叉樹的層次順序，依次輸：按完全二叉樹的層次順序，依次

35、輸入結(jié)點(diǎn)信息建立二叉鏈表。入結(jié)點(diǎn)信息建立二叉鏈表。l基本思想：對(duì)一般的二叉樹添加若干個(gè)虛基本思想：對(duì)一般的二叉樹添加若干個(gè)虛結(jié)點(diǎn)使其成為完全二叉樹；依次輸入結(jié)點(diǎn)信結(jié)點(diǎn)使其成為完全二叉樹；依次輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)：若是第一個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)新結(jié)點(diǎn)：若是第一個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)插入到它的雙親結(jié)點(diǎn)上。，否則將新結(jié)點(diǎn)插入到它的雙親結(jié)點(diǎn)上。l如此重復(fù)，直到輸入結(jié)束符號(hào)如此重復(fù)，直到輸入結(jié)束符號(hào)“0”時(shí)停時(shí)停止（假設(shè)結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址停?。止（假設(shè)結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址停５?51 頁6.2 6.2 二叉樹二叉樹l為使新

36、結(jié)點(diǎn)能正確地鏈接到其雙親結(jié)點(diǎn)，可為使新結(jié)點(diǎn)能正確地鏈接到其雙親結(jié)點(diǎn)，可設(shè)置一個(gè)指針數(shù)組作為設(shè)置一個(gè)指針數(shù)組作為“隊(duì)列隊(duì)列”（下標(biāo)從（下標(biāo)從1開開始），保存已輸入的結(jié)點(diǎn)：始），保存已輸入的結(jié)點(diǎn)：l由于結(jié)點(diǎn)是按層自左向右輸入，所以先輸入由于結(jié)點(diǎn)是按層自左向右輸入，所以先輸入結(jié)點(diǎn)的孩子結(jié)點(diǎn)會(huì)先入隊(duì)，故可利用隊(duì)頭指結(jié)點(diǎn)的孩子結(jié)點(diǎn)會(huì)先入隊(duì)，故可利用隊(duì)頭指針針 front 指向當(dāng)前結(jié)點(diǎn)的雙親，利用隊(duì)尾指針指向當(dāng)前結(jié)點(diǎn)的雙親，利用隊(duì)尾指針 rear 指向當(dāng)前結(jié)點(diǎn)。指向當(dāng)前結(jié)點(diǎn)。l若若 rear為偶數(shù)，則當(dāng)前結(jié)點(diǎn)是為偶數(shù)，則當(dāng)前結(jié)點(diǎn)是 front 所指結(jié)所指結(jié)點(diǎn)的左孩子；否則，當(dāng)前結(jié)點(diǎn)是點(diǎn)的左孩子；否則，當(dāng)前

37、結(jié)點(diǎn)是 front 所指結(jié)所指結(jié)點(diǎn)的右孩子，鏈接后，隊(duì)頭元素出隊(duì)。點(diǎn)的右孩子，鏈接后，隊(duì)頭元素出隊(duì)。l若當(dāng)前結(jié)點(diǎn)為虛結(jié)點(diǎn)，則不需鏈接。若當(dāng)前結(jié)點(diǎn)為虛結(jié)點(diǎn)，則不需鏈接。第 52 頁6.2 6.2 二叉樹二叉樹void CreateBinTree( BinTree bt ) /Q1.n是一個(gè)是一個(gè)BinTNode類型的指針數(shù)組類型的指針數(shù)組 int front,rear；char ch； ch=getchar( )；bt=NULL；/置空二叉樹置空二叉樹 front=1；rear=0； /初始化隊(duì)列初始化隊(duì)列 while( ch != # ) /假設(shè)結(jié)點(diǎn)值為單字符，假設(shè)結(jié)點(diǎn)值為單字符，#為截止符為

38、截止符 s=NULL； /先假設(shè)讀入的為虛結(jié)點(diǎn)先假設(shè)讀入的為虛結(jié)點(diǎn)“#” if(ch!=#) s=(BinTNode *)malloc(sizeof(BinTNode)； s-data=ch；s-lchild=s-rchild=NULL； /endif_1 rear+； /隊(duì)尾指針自增隊(duì)尾指針自增 Qrear=s； /將新結(jié)點(diǎn)地址或虛結(jié)點(diǎn)地址將新結(jié)點(diǎn)地址或虛結(jié)點(diǎn)地址(NULL)入隊(duì)入隊(duì) if(rear=1) /若若rear為為1,則說明是根結(jié)點(diǎn)，用則說明是根結(jié)點(diǎn)，用bt指向它指向它 bt=s； else if(s!=NULL & Qfront!=NULL) /當(dāng)前結(jié)點(diǎn)不是虛結(jié)當(dāng)前結(jié)點(diǎn)不

39、是虛結(jié)點(diǎn)點(diǎn) if(rear % 2=0) /rear為偶數(shù)，新結(jié)點(diǎn)應(yīng)作為左孩子為偶數(shù)，新結(jié)點(diǎn)應(yīng)作為左孩子 Qfront-lchild=s； else Qfront-rchild=s；/新結(jié)點(diǎn)應(yīng)作為右孩子新結(jié)點(diǎn)應(yīng)作為右孩子 front +；/front指向下一個(gè)雙親指向下一個(gè)雙親 ch=getchar( )；/讀下一個(gè)結(jié)點(diǎn)值讀下一個(gè)結(jié)點(diǎn)值 /endwhile第 53 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l遍歷的基本概念遍歷的基本概念l 遍歷：按某種搜索策略遍歷：按某種搜索策略( (路徑路徑) )訪問訪問樹或圖中的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被樹或圖中的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被

40、訪問一次。訪問一次。l 訪問：含義很廣，可以是對(duì)結(jié)點(diǎn)的訪問：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)等。數(shù)據(jù)等。l 遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。許多其它的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。l 遍歷對(duì)線性結(jié)構(gòu)很容易，但二叉樹遍歷對(duì)線性結(jié)構(gòu)很容易，但二叉樹每個(gè)結(jié)點(diǎn)都可能有兩棵子樹，因而需要每個(gè)結(jié)點(diǎn)都可能有兩棵子樹，因而需要尋找一種規(guī)律，使二叉樹中的結(jié)點(diǎn)能線尋找一種規(guī)律，使二叉樹中的結(jié)點(diǎn)能線性排列。性排列。第 54 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二

41、叉樹的遍歷二叉樹的遍歷l 二叉樹的遍歷，就是按某種次序二叉樹的遍歷，就是按某種次序訪問二叉樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪訪問二叉樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。問一次且僅訪問一次。l 二叉樹由根、左子樹、右子樹三二叉樹由根、左子樹、右子樹三部分組成。部分組成。l 二叉樹的遍歷可以分解為：訪問二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹。根，遍歷左子樹和遍歷右子樹。第 55 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的遍歷二叉樹的遍歷令：令：L L：遍歷左子樹：遍歷左子樹 D D：訪問根結(jié)點(diǎn)：訪問根結(jié)點(diǎn) R R：遍歷右子樹：遍歷右子樹有六種遍歷方法

42、：有六種遍歷方法： 基本：基本：DLRDLR，LDRLDR，LRDLRD 鏡象：鏡象：DRLDRL，RDLRDL，RLDRLD 約定先左后右，有三種遍歷方法：約定先左后右，有三種遍歷方法：DLRDLR、LDRLDR、LRDLRD，分別根據(jù)訪問根結(jié)點(diǎn)的次序稱為：，分別根據(jù)訪問根結(jié)點(diǎn)的次序稱為：先序遍歷、中序遍歷和后序遍歷。先序遍歷、中序遍歷和后序遍歷。 A A F F G G E E D D C C B B第 56 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的先序遍歷（二叉樹的先序遍歷（DLR）先序遍歷（先序遍歷（DLRDLR）若二叉樹非空若二叉樹非空（1 1）訪問根

43、結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2 2）先序遍歷左子樹；）先序遍歷左子樹；（3 3）先序遍歷右子樹。）先序遍歷右子樹。例：先序遍歷二叉樹例：先序遍歷二叉樹 1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A A 2 2）先序遍歷左子樹：即按）先序遍歷左子樹：即按 DLR DLR 的順序遍歷左子樹的順序遍歷左子樹 3 3）先序遍歷右子樹：即按）先序遍歷右子樹：即按 DLR DLR 的順序遍歷右子樹的順序遍歷右子樹 A A F F G G E E D D C C B B第 57 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的先序遍歷（二叉樹的先序遍歷（DLR）先序遍歷（先序遍歷（DLRDLR）若二叉

44、樹非空若二叉樹非空（1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2 2）先序遍歷左子樹；）先序遍歷左子樹；（3 3）先序遍歷右子樹。）先序遍歷右子樹。 A A F F G G E E D D C C B B先序遍歷序列：先序遍歷序列：A,A, B,B,C,C,D,D, E,E, G,G,F F第 58 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的中序遍歷（二叉樹的中序遍歷（LDR）中序遍歷（中序遍歷（LDRLDR）若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹；）中序遍歷左子樹；（2 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3 3）中序遍歷右子樹。）中序遍歷右子樹。中序遍歷序列：

45、中序遍歷序列：例：中序遍歷二叉樹例：中序遍歷二叉樹 1 1）中序遍歷左子樹：即按）中序遍歷左子樹：即按 LDR LDR 的順序遍歷左子樹的順序遍歷左子樹 2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A A 3 3）中序遍歷右子樹：即按）中序遍歷右子樹：即按 LDR LDR 的順序遍歷右子樹的順序遍歷右子樹A,A,D,B,G,E,D,B,G,E,C,FC,F A A F F G G E E D D C C B B第 59 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的后序遍歷（二叉樹的后序遍歷（LRD）后序遍歷（后序遍歷（LRDLRD）若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹

46、；）后序遍歷左子樹；（2 2）后序遍歷右子樹。）后序遍歷右子樹。（3 3）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；后序遍歷序列：后序遍歷序列：例：后序遍歷二叉樹例：后序遍歷二叉樹 1 1）后序遍歷左子樹：即按）后序遍歷左子樹：即按 LRD LRD 的順序遍歷左子樹的順序遍歷左子樹 2 2）后序遍歷右子樹：即按）后序遍歷右子樹：即按 LRD LRD 的順序遍歷右子樹的順序遍歷右子樹 3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A AA AD,G,E,B,D,G,E,B, F,C,F,C, A A F F G G E E D D C C B B第 60 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例：先序遍

47、歷、中序遍歷、后序遍歷二叉樹。例：先序遍歷、中序遍歷、后序遍歷二叉樹。 e e d d c c b b f f a a + + * * / / - - - -后序遍歷序列：后序遍歷序列：中序遍歷序列：中序遍歷序列：先序遍歷序列：先序遍歷序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f-,+,a,-,+,a,* *,b,-,c,d,/,e,f,b,-,c,d,/,e,f第 61 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l遍歷的遞歸算法遍歷的遞歸算

48、法l 先序遍歷（先序遍歷（DLR）的定義：）的定義：若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹；）先序遍歷右子樹；上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于： 若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束基本項(xiàng)（也叫終止項(xiàng)）基本項(xiàng)（也叫終止項(xiàng)） 若二叉樹非空若二叉樹非空遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹。）先序遍歷右子樹。第 62 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹1、先序遍歷遞歸算法、先

49、序遍歷遞歸算法 void PreOrderTraverse ( BiTree T, Status ( * Visit ) ( ElemType e ) ) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的是訪問結(jié)點(diǎn)的函數(shù)函數(shù) /本算法先序遍歷以本算法先序遍歷以T為根結(jié)點(diǎn)指針的二叉樹為根結(jié)點(diǎn)指針的二叉樹 if ( T ) /若二叉樹不若二叉樹不為空為空 Visit( T-data )； /訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) PreOrderTraverse(T-lchild, Visit); /先序遍歷先序遍歷T的左子樹的左子樹 PreOrderTraverse(T-rchil

50、d, Visit); /先序遍歷先序遍歷T的右子樹的右子樹 /PreOrderTraverse最簡單的最簡單的 Visit 函數(shù)是：函數(shù)是：Status PrintElement( TElemType e ) /輸出元素輸出元素e的值的值output( e ); return OK;DABC E E F F T T第 63 頁 D D ABC F G G T TE E 6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(PA-rc); A A B B D D E E G G C C F FTra(P

51、B) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc); Tra(PD) if (PD!=NULL) V(D); Tra(PD-lc); Tra(PD-rc); Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(PA-rc); Tra(PB) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc); Tra(PB) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc); Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(P

52、A-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PD) if (PD!=NULL) V(D); Tra(PD-lc); Tra(PD-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-lc); Tra(PE-rc); Tra(PE) if (PE!=NULL) V(E); Tra(P

53、E-lc); Tra(PE-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-lc); Tra(PE-rc); Tra(PF) if (PF!=NULL) V(F); Tra(PF-lc); Tra(PF-rc); Tra(PF) if (PF!=NULL) V(F); Tra(PF-lc); Tra(PF-rc); 第 64 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l先序遍歷遞歸算法（教材先序遍歷遞歸算法（教材P129）lStatus PreOrderTraverse ( BiTree T, lStatus ( * Visit ) ( El

54、emType e ) )l / 采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪是訪問結(jié)點(diǎn)的函數(shù)問結(jié)點(diǎn)的函數(shù)l if ( T ) l if ( Visit( T-data ) ) / 如果訪問根結(jié)點(diǎn)如果訪問根結(jié)點(diǎn)成功，則繼續(xù)成功，則繼續(xù)l if ( PreOrderTraverse(T-lchild, Visit) ) /左子樹左子樹l if ( PreOrderTraverse(T-rchild, Visit) ) /右子樹右子樹l return OK;l return ERROR;l l else return ok;l / PreOrderTraverse第 65

55、頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹2、中序遍歷遞歸算法、中序遍歷遞歸算法Status InOrderTraverse( BiTree T, Status ( * Visit ) ( ElemType e ) ) / 采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的是訪問結(jié)點(diǎn)的函數(shù)函數(shù) / 本算法中序遍歷以本算法中序遍歷以T為根結(jié)點(diǎn)指針的二叉樹為根結(jié)點(diǎn)指針的二叉樹 if ( T ) / 若二叉樹若二叉樹不為空不為空 InOrderTraverse( T-lchild, Visit ); / 中序遍歷中序遍歷T的左子樹的左子樹 Visit

56、( T-data )； / 訪問根結(jié)訪問根結(jié)點(diǎn)點(diǎn) InOrderTraverse( T-rchild, Visit ); / 中序遍歷中序遍歷T的右子樹的右子樹 / InOrderTraverse第 66 頁 D D ABC F G G T TE E 6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹Tra(PA) if (PA!=NULL) Tra(PA-lc); V(A) ; Tra(PA-rc); A AB BD DE EG GC CF FTra(PB) if (PB!=NULL) Tra(PB-lc); V(B) ; Tra(PB-rc); Tra(PD) if (PD!=N

57、ULL) Tra(PD-lc); V(D); Tra(PD-rc); 第 67 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹3、后序遍歷遞歸算法、后序遍歷遞歸算法void PostOrderTraverse( BiTree T , Status ( * Visit ) ( ElemType e ) ) / 采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的是訪問結(jié)點(diǎn)的函數(shù)函數(shù) / 本算法后序遍歷以本算法后序遍歷以T為根結(jié)點(diǎn)指針的二叉樹為根結(jié)點(diǎn)指針的二叉樹 if ( T ) / 若二叉若二叉樹不為空樹不為空 PostOrderTraverse( T-

58、lchild, Visit ); / 后序遍后序遍歷左子樹歷左子樹 PostOrderTraverse( T-rchild, Visit ); / 后序遍后序遍歷右子樹歷右子樹 Visit ( T-data )； / 訪問根訪問根結(jié)點(diǎn)結(jié)點(diǎn) / PostOrderTraverse第 68 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例1：編寫求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法。：編寫求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法。 輸入：二叉樹的二叉鏈表輸入：二叉樹的二叉鏈表 結(jié)果：二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)結(jié)果：二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)void leaf ( BiTree T ) / 二叉鏈表存貯二叉樹，計(jì)

59、算二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)二叉鏈表存貯二叉樹，計(jì)算二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù) / 先序遍歷的過程中進(jìn)行統(tǒng)計(jì)，初始全局變量先序遍歷的過程中進(jìn)行統(tǒng)計(jì)，初始全局變量 n=0 if ( T ) if ( T-lchild=null & T-rchild=null ) n += 1; /若若T所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)則計(jì)數(shù)所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)則計(jì)數(shù) else leaf ( T-lchild ); leaf ( T-rchild ); / if / leaf與先序遍歷算與先序遍歷算法比較一下！法比較一下！第 69 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例1：編寫求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法

60、。：編寫求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法。int Countleave( BiTree T ) / 采用二叉鏈表存貯二叉樹，返回葉子結(jié)點(diǎn)的個(gè)數(shù)采用二叉鏈表存貯二叉樹，返回葉子結(jié)點(diǎn)的個(gè)數(shù) if ( T-lchild=NULL & T-rchild=NULL ) return 1; else if ( !T ) return 0; return ;Countleave( T-lchild ) + Countleave( T-rchild ) D D ABC F G G T TE E 第 70 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例2：建立二叉鏈表。：建立二叉鏈表。 結(jié)果：二叉樹的二叉鏈表。結(jié)果：二叉樹的二叉鏈表。基本思想：基本思想： 輸入（在空子樹處添加字符輸入（在空子樹處添加字符 * * 的二叉樹的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)