內(nèi)容文本講義d

1、第 2 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 樹樹(Tree)是是 n 個結(jié)點(diǎn)的有限集合，在任意一個結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：棵非空樹中： （1）有且僅有一個稱為根）有且僅有一個稱為根(Root)的結(jié)點(diǎn)。的結(jié)點(diǎn)。 （2）其余結(jié)點(diǎn)可分為若干個互不相交的集合）其余結(jié)點(diǎn)可分為若干個互不相交的集合，且這些集合中的每一集合本身又是一棵樹，且這些集合中的每一集合本身又是一棵樹，稱為根的子樹稱為根的子樹(SubTree)。樹是遞歸結(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ù)語例：右面的圖是例：右面的圖是一棵樹一棵樹 T。 T = A T = A，B B，C C，D D，E E，F(xiàn) F，G G，H H，I I，J J A A是根，其余結(jié)點(diǎn)可以劃分為是根，其余結(jié)點(diǎn)可以劃分為3 3個互不相交的集合：個互不相交的集合： 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 的子樹。的子樹。 對于對于T1T1，B B是根，其余結(jié)點(diǎn)可以劃分為兩個互不相是根，其余結(jié)點(diǎn)可以劃分為兩個互

3、不相交的集合：交的集合： T11= E T12= F T11 T11= E T12= F T11，T12T12是是B B的子樹。的子樹。J JI IA AC CB BD DH HG GF FE E第 4 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 2）除根外，其余結(jié)點(diǎn)都有且僅一個前趨；）除根外，其余結(jié)點(diǎn)都有且僅一個前趨； 3）樹的結(jié)點(diǎn)，可以有零個或多個后繼；）樹的結(jié)點(diǎn)，可以有零個或多個后繼； 4）除根之外的其它結(jié)點(diǎn)，都存在唯一一條）除根之外的其它結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑；從根到該結(jié)點(diǎn)的路徑； 5）樹是一種分支結(jié)構(gòu)（除了一個稱為根的）樹是一種分支結(jié)構(gòu)（除了一個稱為根的結(jié)

4、點(diǎn)之外）每個元素都有且僅有一個直接前結(jié)點(diǎn)之外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。趨，有且僅有零個或多個直接后繼。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第 5 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的應(yīng)用樹的應(yīng)用家族樹家族樹血統(tǒng)樹血統(tǒng)樹( 二叉樹二叉樹 )第 6 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的應(yīng)用樹的應(yīng)用l 常用的數(shù)據(jù)組織形式常用的數(shù)據(jù)組織形式計算機(jī)的文計算機(jī)的文件系統(tǒng)。件系統(tǒng)。l 不論是不論是DOSDOS文件系統(tǒng)

5、還是文件系統(tǒng)還是windowwindow文件文件系統(tǒng)，所有的文件都是用樹的形式進(jìn)行組織。系統(tǒng)，所有的文件都是用樹的形式進(jìn)行組織。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾2 1 2 1 文件夾文件夾22 22 文件文件21 21 文件文件2222C C第 7 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的應(yīng)用樹的應(yīng)用lDNS Name Space.DNS Name Space.“.”.comeducnedubittshuapku cs ee ss中國教育和科研網(wǎng)教育和科研網(wǎng)北理校園網(wǎng)北理校園網(wǎng)第 8 頁6.1 6.1 樹的定義與基本術(shù)語樹的

6、定義與基本術(shù)語l樹的表示樹的表示l 1）圖示表示）圖示表示l 2）二元組表示）二元組表示l 3）文氏圖表示）文氏圖表示l 4）廣義表表示）廣義表表示l 5）凹入表示法（類似書的目錄）凹入表示法（類似書的目錄）J JI IA AC CB BD DH HG GF FE E第 9 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語D = A，B，C，D，E，F(xiàn)，G，H，I，J R = , , , , , , , , l樹的表示樹的表示l2）二元組表示）二元組表示J JI IA AC CB BD DH HG GF FE E第 10 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的表示樹

7、的表示l3）文氏圖表示）文氏圖表示ABCDEFGHIJMKLABCDEFGHIJMKL第 11 頁6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 假設(shè)樹的根為假設(shè)樹的根為rootroot，子樹為，子樹為T1,T2,TnT1,T2,Tn，與該樹對應(yīng)的廣義表為與該樹對應(yīng)的廣義表為L L，則：，則：L=(L=(原子原子( (子表子表1,1,子表子表2, , 2, , 子表子表n)n)，其中原子對應(yīng)，其中原子對應(yīng)rootroot，子，子表表 i(1i=n) i(1i1時，其余結(jié)點(diǎn)可分為時，其余結(jié)點(diǎn)可分為 m(m0) 個個互不相交的有限集互不相交的有限集T1, T2, , Tm，其中每一，其中每一

8、棵子集本身又是一棵符合本定義的樹，稱為棵子集本身又是一棵符合本定義的樹，稱為根根root的子樹。的子樹。第 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) CreateTree ( &T, definition );

9、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 樹的定義與基本術(shù)語樹的定義與基本術(shù)語l樹的基本操作樹的基本操

10、作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) Parent ( T, cur

11、_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)的右兄弟。l13) InsertChi

12、ld ( &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 棵子樹。棵子樹。l15) TraverseTree ( T, Visit( ) );15) TraverseTree ( T, V

13、isit( ) );l 按某種次序?qū)Π茨撤N次序?qū)?T T 樹的每個結(jié)點(diǎn)調(diào)用函樹的每個結(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)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點(diǎn)多個葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 一個后繼一個后繼) )其它數(shù)據(jù)元素其

14、它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) )第 21 頁6.2 6.2 二叉樹二叉樹l定義定義l一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。左子樹和右子樹的、互不相交的二叉樹組成。l形式定義形式定義l數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R R 滿足：滿足：l 若若 D D，則，則R R，稱為是空二叉樹。，稱為是空二叉樹。l 若若 D D，則，則R R H H ，H H是如下二元關(guān)系：是如下二元關(guān)系：l(1) (1) 在在D D中存在惟一的

15、稱為根的數(shù)據(jù)元素中存在惟一的稱為根的數(shù)據(jù)元素rootroot，它在，它在關(guān)系關(guān)系H H下無前驅(qū)；下無前驅(qū)；l(2) (2) 若若 D-root D-root，則存在，則存在 D-root D-root Dl,Dr Dl,Dr，且且DlDr=DlDr=。第 22 頁6.2 6.2 二叉樹二叉樹l定義定義l一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。左子樹和右子樹的、互不相交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子

16、樹第 23 頁6.2 6.2 二叉樹二叉樹NLRLRNNNl二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)空樹空樹只有根只有根結(jié)點(diǎn)結(jié)點(diǎn)只有左子樹只有左子樹只有右子樹只有右子樹左右子樹均非空左右子樹均非空第 24 頁6.2 6.2 二叉樹二叉樹 (a) (a)、(b)(b)是不同的二叉樹是不同的二叉樹(a)(a)的左子樹有四個結(jié)點(diǎn)，的左子樹有四個結(jié)點(diǎn)，(b)(b)的左子樹有兩個結(jié)點(diǎn)的左子樹有兩個結(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第 25 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)1：l在二叉樹的第在

17、二叉樹的第 i 層上至多有層上至多有2i-1 個結(jié)點(diǎn)個結(jié)點(diǎn)(i1)。i=1 i=1 ：最多：最多1 1個結(jié)點(diǎn)個結(jié)點(diǎn)i=2 i=2 ：最多：最多2 2個結(jié)點(diǎn)個結(jié)點(diǎn)i=3 i=3 ：最多：最多4 4個結(jié)點(diǎn)個結(jié)點(diǎn)GAFEDCB第 26 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)1：l在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個結(jié)點(diǎn)個結(jié)點(diǎn)(i1)。用歸納法證明：用歸納法證明： 歸納基：歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時，只有一個根結(jié)點(diǎn)，層時，只有一個根結(jié)點(diǎn)， 2 i-1 = 2 0 = 1；假設(shè)對所有的假設(shè)對所有的 j, 1j i，命題成立；，命題成立

18、；二叉樹上每個結(jié)點(diǎn)至多有兩棵子樹，二叉樹上每個結(jié)點(diǎn)至多有兩棵子樹，則第則第 i 層的結(jié)點(diǎn)數(shù)層的結(jié)點(diǎn)數(shù)=2i-22=2i-1。第 27 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)2：l深度為深度為k的二叉樹上至多含的二叉樹上至多含2k-1個結(jié)點(diǎn)個結(jié)點(diǎn)(k1)。證明：證明： 基于上一條性質(zhì)，深度為基于上一條性質(zhì)，深度為 k 的二叉樹上的二叉樹上的結(jié)點(diǎn)數(shù)至多為：的結(jié)點(diǎn)數(shù)至多為：20+21+ +2k-1 = 2k-1 第 28 頁6.2 6.2 二叉樹二叉樹l性質(zhì)性質(zhì)3：l 對任何一棵二叉樹，若它含有對任何一棵二叉樹，若它含有n0 個葉個葉子結(jié)點(diǎn)、子結(jié)點(diǎn)、n2 個度為個度為 2 的結(jié)點(diǎn)，則必存在關(guān)系的結(jié)

19、點(diǎn)，則必存在關(guān)系式：式：n0 = n2+1證明：證明：設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù)：二叉樹上結(jié)點(diǎn)總數(shù)：n = n0 + n1 + n2又又 二叉樹上分支總數(shù)：二叉樹上分支總數(shù)：b = n1 + 2n2而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1第 29 頁6.2 6.2 二叉樹二叉樹l兩類特殊的二叉樹兩類特殊的二叉樹滿二叉樹：指的是深滿二叉樹：指的是深度為度為 k 且含有且含有 2k-1 個個結(jié)點(diǎn)的二叉樹。結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所完全二叉樹：樹中所含的含的 n 個結(jié)點(diǎn)和滿二個結(jié)點(diǎn)和滿二叉樹中編號為叉樹中編號為 1 至至 n 的結(jié)點(diǎn)一一對應(yīng)。的

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

21、右孩子結(jié)的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。點(diǎn)。第 32 頁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)不在同一層i -1i -2第 33 頁6.2 6.2 二叉樹二叉樹l二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)l1. 二叉樹的順序結(jié)構(gòu)二叉樹的順序結(jié)構(gòu)l對于完全二叉樹，采用一組連續(xù)的內(nèi)存單對于完全二叉樹，采用一組連續(xù)的內(nèi)存單元，按編號順序依次存儲完全二叉樹的結(jié)點(diǎn)。元，按編號順序依次存儲完全二叉樹的結(jié)點(diǎn)。 1 2 3 4 5 6 7 m-1 1

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

23、”的位置上。的位置上。 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第 36 頁6.2 6.2 二叉樹二叉樹 對于一些對于一些“退化二叉樹退化二叉樹”，順序存儲，順序存儲結(jié)構(gòu)存在突出缺點(diǎn)：比較浪費(fèi)空間。結(jié)構(gòu)存在突出缺點(diǎn)：比較浪費(fèi)空間。DACBACBDA BCDBT8ABCDBT15第 37 頁6.2 6.2 二叉樹二叉樹2. 二叉鏈表二叉鏈表 二

24、叉鏈表中每個結(jié)點(diǎn)包含三個域：數(shù)據(jù)域、二叉鏈表中每個結(jié)點(diǎn)包含三個域：數(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)存儲數(shù)據(jù)元素存儲數(shù)據(jù)元素指向右孩子指向右孩子指向左孩子指向左孩子第 38 頁6

25、.2 6.2 二叉樹二叉樹二叉樹的二叉鏈表表示二叉樹的二叉鏈表表示AFEDCB二叉鏈表圖示二叉鏈表圖示DABC E E F F T T第 39 頁6.2 6.2 二叉樹二叉樹3. 三叉鏈表三叉鏈表 三叉鏈表中每個結(jié)點(diǎn)包含四個域：數(shù)據(jù)域、三叉鏈表中每個結(jié)點(diǎn)包含四個域：數(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

26、 BiTNode * * lchild, lchild, * * rchild; rchild; struct BiTNode struct BiTNode * * parent; parent; BiTNode, BiTNode,* *BiTree;BiTree;第 40 頁6.2 6.2 二叉樹二叉樹二叉樹的三叉鏈表表示二叉樹的三叉鏈表表示rootADEBCF CEFDAB第 41 頁6.2 6.2 二叉樹二叉樹4. 靜態(tài)二叉鏈表靜態(tài)二叉鏈表 采用數(shù)組區(qū)間存貯的鏈表。采用數(shù)組區(qū)間存貯的鏈表。孩子結(jié)點(diǎn)在數(shù)組中孩子結(jié)點(diǎn)在數(shù)組中的位置。用的位置。用-1-1表示表示無左孩子或右孩子無左孩子或右孩子

27、0 01 12 23 34 45 56 6Lchild data rchildLchild data rchildroot = 0AFEDCB2 2 A 1 A 13 33 C -3 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 4第 42 頁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 /

28、樹結(jié)構(gòu)樹結(jié)構(gòu) BNode nodes MAX_TREE_SIZE ; int num_node; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BTree;第 43 頁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第 44 頁6.2 6.2 二叉樹二叉樹5. 雙親鏈表雙親鏈表 typedef struct BPTNo

29、de / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType 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;第 45 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l遍歷的基本概念遍歷的基本概念l 遍歷：按某種搜索路徑訪問二叉樹遍歷：按某種搜索路徑訪問二叉樹中

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

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

32、歷左子樹 D D：訪問根結(jié)點(diǎn)：訪問根結(jié)點(diǎn) R R：遍歷右子樹：遍歷右子樹有六種遍歷方法：有六種遍歷方法： 基本：基本：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第 48 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的先序遍歷（二叉樹的先

33、序遍歷（DLR）先序遍歷（先序遍歷（DLRDLR）若二叉樹非空若二叉樹非空（1 1）訪問根結(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第 49 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二

34、叉樹l二叉樹的先序遍歷（二叉樹的先序遍歷（DLR）先序遍歷（先序遍歷（DLRDLR）若二叉樹非空若二叉樹非空（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第 50 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的中序遍歷（二叉樹的中序遍歷（LDR）中序遍歷（中序遍歷（LDRLDR）若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹；）中序遍歷左子樹；（2

35、 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3 3）中序遍歷右子樹。）中序遍歷右子樹。中序遍歷序列：中序遍歷序列：例：中序遍歷二叉樹例：中序遍歷二叉樹 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第 51 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l二叉樹的后序遍歷（二叉樹的后序遍歷（

36、LRD）后序遍歷（后序遍歷（LRDLRD）若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹；）后序遍歷左子樹；（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

37、 B B第 52 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例：先序遍歷、中序遍歷、后序遍歷二叉樹。例：先序遍歷、中序遍歷、后序遍歷二叉樹。 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第 53

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

39、4 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹1、先序遍歷遞歸算法、先序遍歷遞歸算法 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)

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

41、 Tra(PA-rc); A A B B D D E E G G C C F FTra(PB) 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);

42、Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(PA-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);

43、Tra(PE-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-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); 第 56 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l先序遍歷遞歸算法（教材先序遍歷遞歸算法（教材P129）lvoid PreOrderTr

44、averse ( BiTree T, lStatus ( * Visit ) ( ElemType 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

45、 l else return ok;l / PreOrderTraverse第 57 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹2、中序遍歷遞歸算法、中序遍歷遞歸算法void 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-lc

46、hild, Visit ); / 中序遍歷中序遍歷T的左子樹的左子樹 Visit ( T-data )； / 訪問根結(jié)訪問根結(jié)點(diǎn)點(diǎn) InOrderTraverse( T-rchild, Visit ); / 中序遍歷中序遍歷T的右子樹的右子樹 / InOrderTraverse第 58 頁 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-

47、lc); V(B) ; Tra(PB-rc); Tra(PD) if (PD!=NULL) Tra(PD-lc); V(D); Tra(PD-rc); 第 59 頁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

48、 ) / 若二叉若二叉樹不為空樹不為空 PostOrderTraverse( T-lchild, Visit ); / 后序遍后序遍歷左子樹歷左子樹 PostOrderTraverse( T-rchild, Visit ); / 后序遍后序遍歷右子樹歷右子樹 Visit ( T-data )； / 訪問根訪問根結(jié)點(diǎn)結(jié)點(diǎn) / PostOrderTraverse第 60 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例1：編寫求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法。：編寫求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法。 輸入：二叉樹的二叉鏈表輸入：二叉樹的二叉鏈表 結(jié)果：二叉樹的葉子結(jié)點(diǎn)個數(shù)結(jié)果：二叉樹的葉

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

50、歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例1：編寫求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法。：編寫求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法。int Countleave( BiTree T ) / 采用二叉鏈表存貯二叉樹，返回葉子結(jié)點(diǎn)的個數(shù)采用二叉鏈表存貯二叉樹，返回葉子結(jié)點(diǎn)的個數(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 第 62 頁6.3 6.3 遍

51、歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例2：建立二叉鏈表。：建立二叉鏈表。 結(jié)果：二叉樹的二叉鏈表。結(jié)果：二叉樹的二叉鏈表?；舅枷耄夯舅枷耄?輸入（在空子樹處添加字符輸入（在空子樹處添加字符 * * 的二叉樹的二叉樹的）先序序列（設(shè)每個元素是一個字符）。的）先序序列（設(shè)每個元素是一個字符）。 按先序遍歷的順序，建立二叉鏈表的所按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接。有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接。第 63 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例2：建立二叉鏈表。：建立二叉鏈表。* C C A A F F E E D D B B*A B D

52、 A B D * * F F * * * * * * C E C E * * * * * * A A F F E E D D C C B B先序序列：先序序列：A B D F C EA B D F C E對原來的二叉樹進(jìn)行擴(kuò)充，在空子樹處添加對原來的二叉樹進(jìn)行擴(kuò)充，在空子樹處添加 * * 。第 64 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹Status CreateBiTree ( BiTree &T ) / 按先序遍歷的順序建立二叉鏈表按先序遍歷的順序建立二叉鏈表 scanf ( &ch ); if ( ch = * ) T=NULL; / 若若ch=

53、* 則表示空子樹則表示空子樹 else if ( ! (T=( BiTNode * ) malloc( sizeof( BiTNode ) ) exit( OVERFLOW ); T-date = ch; / 建立（根）結(jié)點(diǎn)建立（根）結(jié)點(diǎn) CreateBiTree( T-lchild ); / 遞歸構(gòu)造左子樹鏈表遞歸構(gòu)造左子樹鏈表 CreateBiTree( T-rchild ); / 遞歸構(gòu)造右子樹鏈表遞歸構(gòu)造右子樹鏈表 return OK; /CreateBiTree第 65 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例2：建立二叉鏈表。：建立二叉鏈表。A B * C

54、 * * D * * * * * * * * *A BCDATBCD第 66 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例3：復(fù)制二叉鏈表。：復(fù)制二叉鏈表。輸入：二叉鏈表輸入：二叉鏈表結(jié)果：復(fù)制的新二叉鏈表結(jié)果：復(fù)制的新二叉鏈表 D D ABC F G G T TE E 第 67 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹例例3：復(fù)制二叉鏈表。：復(fù)制二叉鏈表。void CopyBiTree( BiTree T, BiTree &newT ) / 采用后序遍歷的框架，新二叉鏈表根為采用后序遍歷的框架，新二叉鏈表根為 newT if ( !T )

55、newT=NULL; else CopyBiTree( T-lchild, plchild ); / 復(fù)制左子樹復(fù)制左子樹 CopyBiTree( T-rchild, prchild ); / 復(fù)制右子樹復(fù)制右子樹 newT = (BiTree) malloc( sizeof(BiTNode) ); newT-data = T-data; / 復(fù)制結(jié)點(diǎn)復(fù)制結(jié)點(diǎn) newT-lchild = plchild; / 鏈接新結(jié)點(diǎn)的左子樹鏈接新結(jié)點(diǎn)的左子樹 newT-rchild = prchild; / 鏈接新結(jié)點(diǎn)的右子樹鏈接新結(jié)點(diǎn)的右子樹 第 68 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹

56、與線索二叉樹l遍歷算法的應(yīng)用遍歷算法的應(yīng)用l1.查詢二叉樹中某個結(jié)點(diǎn)查詢二叉樹中某個結(jié)點(diǎn)l2.求二叉樹的深度（后序遍歷）求二叉樹的深度（后序遍歷）l3.判斷二叉樹相等判斷二叉樹相等l4.建立二叉樹的存儲結(jié)構(gòu)（給出全部建立二叉樹的存儲結(jié)構(gòu)（給出全部左右子樹）左右子樹）l5.由二叉樹的先序序列和中序序列建由二叉樹的先序序列和中序序列建立二叉樹立二叉樹第 69 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l遍歷的非遞歸算法遍歷的非遞歸算法 棧是實(shí)現(xiàn)遞歸的最常用的結(jié)構(gòu)。棧是實(shí)現(xiàn)遞歸的最常用的結(jié)構(gòu)。 利用一個棧來記下尚待遍歷的結(jié)點(diǎn)或子利用一個棧來記下尚待遍歷的結(jié)點(diǎn)或子樹，以備以后訪問。

57、樹，以備以后訪問。第 70 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l中序遍歷的非遞歸算法中序遍歷的非遞歸算法？中序遍歷的第一個結(jié)點(diǎn)中序遍歷的第一個結(jié)點(diǎn)？當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)D B G E A F CD B G E A F C 若當(dāng)前結(jié)點(diǎn)有右子樹，后繼結(jié)點(diǎn)為右子樹的若當(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 D ABC F G G T TE E 第 71 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l中序遍歷的非遞歸算法中序遍歷的非遞歸算法？中序遍

58、歷的第一個結(jié)點(diǎn)中序遍歷的第一個結(jié)點(diǎn)？當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) 若當(dāng)前結(jié)點(diǎn)有右子樹，后繼結(jié)點(diǎn)為右子樹的若當(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)。二叉樹的最左下結(jié)點(diǎn)。二叉樹的最左下結(jié)點(diǎn)。AD B G E A F C B DE GC F D D ABC F G G T TE E 第 72 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹Status InTrav( BiTree T, void(* Visit)(TelemType e) ) InitStack(S); p = T; while ( p | !

59、 StackEmpty(S) ) / 樹非空樹非空 或或 棧非空棧非空 if ( p ) / 若樹非空若樹非空 Push(S, p); p = p-lchild; / p有左子樹則有左子樹則p結(jié)點(diǎn)入棧，直到找到最左下結(jié)點(diǎn)結(jié)點(diǎn)入棧，直到找到最左下結(jié)點(diǎn) else /（最左下結(jié)點(diǎn)）退棧，訪問之（最左下結(jié)點(diǎn)）退棧，訪問之 Pop (S, p); Visit( p-data ); p = p-rchild; / p指向右子樹指向右子樹 / while DesrroyStack(S); return OK; / InTrav P131 算法算法6.3第 73 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二

60、叉樹與線索二叉樹l線索二叉樹線索二叉樹l 遍歷二叉樹的結(jié)果可求得結(jié)點(diǎn)的一遍歷二叉樹的結(jié)果可求得結(jié)點(diǎn)的一個線性序列。個線性序列。 中序序列：中序序列：D B G E A F C例如： 后序序列：后序序列：D G E B F C A 先序序列：先序序列：A B D E G C F GAFEDCB 指向線性序列中的指向線性序列中的“前趨前趨”和和 “后繼后繼” 的的指針，稱作指針，稱作“線索線索”。第 74 頁6.3 6.3 遍歷二叉樹與線索二叉樹遍歷二叉樹與線索二叉樹l線索二叉樹線索二叉樹l如何在二叉鏈表中保存線索？如何在二叉鏈表中保存線索？l 借用結(jié)點(diǎn)的空鏈域保借用結(jié)點(diǎn)的空鏈域保存線索存線索 中序序列：中序序列：D B G E A F CD B G E A F CGAFEDCB包含包含 “線索線索” 的存儲結(jié)構(gòu)，稱作的存儲結(jié)構(gòu)，稱作 “線索鏈表線索鏈表”。 D D