數(shù)據(jù)結(jié)構(gòu)與算法_第6章_樹(shù)和二叉樹(shù)

1、16.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.2 二叉樹(shù)二叉樹(shù)6.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化6.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系6.5 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用6.6 總結(jié)與提高總結(jié)與提高26.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)樹(shù)：是：是n(n0)個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的有限有限集合集合T。 當(dāng)當(dāng)n=0時(shí)稱(chēng)為時(shí)稱(chēng)為空樹(shù)空樹(shù)； 當(dāng)當(dāng)n0時(shí)，該集合滿(mǎn)足如下條件：時(shí)，該集合滿(mǎn)足如下條件： 其中必有一個(gè)稱(chēng)為其中必有一個(gè)稱(chēng)為根根(root)的特定結(jié)點(diǎn)，它沒(méi)有的特定結(jié)點(diǎn)，它沒(méi)有直直接前驅(qū)接

2、前驅(qū)，但有零個(gè)或多個(gè)，但有零個(gè)或多個(gè)直接后繼直接后繼。(2) 其余其余n-1個(gè)結(jié)點(diǎn)可以劃分成個(gè)結(jié)點(diǎn)可以劃分成m(m0)個(gè)個(gè)互不相交的互不相交的有限集有限集T1，T2，T3，Tm，其中，其中Ti又是一棵樹(shù)，又是一棵樹(shù)，稱(chēng)為根稱(chēng)為根root的的子樹(shù)子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 36.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)例如：例如：第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2根根46.1 樹(shù)

3、的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)表示方法：表示方法：第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)型表示樹(shù)型表示bacghdefij56.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)表示方法：表示方法：第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)文氏圖表示文氏圖表示ijdfghabce66.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)表示方法：表示方法：第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)凹入表示凹入表示abdeijfcgh76.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)表示方法：表示方法：第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)嵌套括號(hào)表示嵌套括號(hào)表示a ( b ( d, e ( i, j ), c ( g, h )

4、) )86.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)基本術(shù)語(yǔ)基本術(shù)語(yǔ)結(jié)點(diǎn)：結(jié)點(diǎn)：數(shù)據(jù)元素?cái)?shù)據(jù)元素+若干指向子樹(shù)的分支若干指向子樹(shù)的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度: 分支的個(gè)數(shù)分支的個(gè)數(shù)樹(shù)的度樹(shù)的度: 樹(shù)中所有結(jié)點(diǎn)的度的最大值樹(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)度大于零的結(jié)點(diǎn)(從根到結(jié)點(diǎn)的從根到結(jié)點(diǎn)的)路徑：路徑：由從由從根根到到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。構(gòu)成。ABCDEFGHIJMKL96.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)基本術(shù)語(yǔ)基本術(shù)語(yǔ)孩

5、子結(jié)點(diǎn)：孩子結(jié)點(diǎn)： 一個(gè)結(jié)點(diǎn)的直接后繼一個(gè)結(jié)點(diǎn)的直接后繼雙親結(jié)點(diǎn)雙親結(jié)點(diǎn): 一個(gè)結(jié)點(diǎn)的直接前驅(qū)一個(gè)結(jié)點(diǎn)的直接前驅(qū)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn): 同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱(chēng)同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱(chē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)的層次為1，第，第i層的結(jié)點(diǎn)的層的結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)的層次為子樹(shù)的根結(jié)點(diǎn)的層次為i+1樹(shù)的深度：樹(shù)的深度：樹(shù)中結(jié)點(diǎn)的層次的樹(shù)中結(jié)點(diǎn)的層次的最大值最大值A(chǔ)BCDEFGHIJMKL森林：森林：是是m（m0）棵互不相交的樹(shù)的集合）棵互不相交的樹(shù)的集合106.1 樹(shù)的定義與基本術(shù)語(yǔ)樹(shù)的定義與基本術(shù)語(yǔ)第第 6 章章 樹(shù)

6、和二叉樹(shù)樹(shù)和二叉樹(shù)基本操作基本操作InitTree(Tree);DestoryTree(Tree);CreatTree(Tree);TreeEmpty(Tree);Root(Tree);Parent(Tree,x);FirstChild(Tree,x);NextSibling(Tree,x);InsertChild(Tree,p,Child);DeleteChild(Tree,p,Child);返回返回116.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)定義：定義：滿(mǎn)足以上兩個(gè)條件的樹(shù)型結(jié)構(gòu)為滿(mǎn)足以上兩個(gè)條件的樹(shù)型結(jié)構(gòu)為二叉樹(shù)二叉樹(shù)。每個(gè)結(jié)點(diǎn)的度都不大于每個(gè)結(jié)點(diǎn)的度都不大于2；每個(gè)結(jié)點(diǎn)

7、的孩子結(jié)點(diǎn)次序不能任意顛倒。每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。二叉樹(shù)或?yàn)槎鏄?shù)或?yàn)榭諛?shù)空樹(shù)，或是由一個(gè)，或是由一個(gè)根結(jié)點(diǎn)根結(jié)點(diǎn)加上兩棵分加上兩棵分別稱(chēng)為別稱(chēng)為左子樹(shù)左子樹(shù)和和右子樹(shù)右子樹(shù)的、的、互不交的二叉樹(shù)組成互不交的二叉樹(shù)組成。ABEFKLDHJM根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)126.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)形態(tài)：形態(tài)：空二叉樹(shù)空二叉樹(shù)只有根結(jié)點(diǎn)只有根結(jié)點(diǎn) 的二叉樹(shù)的二叉樹(shù)只有右子樹(shù)只有右子樹(shù) 的二叉樹(shù)的二叉樹(shù)左、右子樹(shù)均左、右子樹(shù)均非空的二叉樹(shù)非空的二叉樹(shù)只有左子樹(shù)只有左子樹(shù) 的二叉樹(shù)的二叉樹(shù)5種種136.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和

8、二叉樹(shù)基本操作：基本操作：Initiate(bt);Destory (bt);Creat (bt);Empty(bt);Root(bt);Parent(bt,x);LeftChild(bt,x);RithtChild(bt,x);Traverse(bt);Clear(bt);146.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)重要性質(zhì)：重要性質(zhì)：在二叉樹(shù)的第在二叉樹(shù)的第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。用歸納法證明：用歸納法證明：. 當(dāng)當(dāng)i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)：層時(shí)，只有一個(gè)根結(jié)點(diǎn)：2i-1 = 20 = 1；. 假設(shè)對(duì)所有的假設(shè)對(duì)所有的 j，1 j i，命

9、題成立；，命題成立；. 二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第 i 層的層的 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。156.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)重要性質(zhì)：重要性質(zhì)：深度為深度為 k 的二叉樹(shù)上至多含的二叉樹(shù)上至多含 2k-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)。證明：證明：基于上一條性質(zhì)，深度為基于上一條性質(zhì)，深度為 k 的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為20+21+ +2k-1 = 2k-1166.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)重要性質(zhì)：重要性質(zhì)： 對(duì)任何一棵二叉樹(shù)，若它含有對(duì)任何一棵二叉樹(shù)，若

10、它含有n0 個(gè)葉子結(jié)點(diǎn)、個(gè)葉子結(jié)點(diǎn)、 n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：的結(jié)點(diǎn)，則必存在關(guān)系式： n0 = n2+1。 證明：證明：設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又二叉樹(shù)上分支總數(shù)又二叉樹(shù)上分支總數(shù) b = n1+2n2而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1176.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)特殊的二叉樹(shù)特殊的二叉樹(shù)滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)完全二叉樹(shù)完全二叉樹(shù)深度為深度為k且含有且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。個(gè)結(jié)點(diǎn)的二叉樹(shù)。樹(shù)中所含的樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)個(gè)結(jié)

11、點(diǎn)和滿(mǎn)二叉樹(shù)中編號(hào)為中編號(hào)為 1 至至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)abcdefghij完全二叉樹(shù)完全二叉樹(shù)關(guān)系：關(guān)系：滿(mǎn)二叉樹(shù)必為完全二叉樹(shù)，滿(mǎn)二叉樹(shù)必為完全二叉樹(shù)，而完全二叉樹(shù)不一定是而完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。滿(mǎn)二叉樹(shù)。 186.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)重要性質(zhì)：重要性質(zhì)：具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n +1 。 證明：證明：設(shè)完全二叉樹(shù)的深度為設(shè)完全二叉樹(shù)的深度為 k 則根據(jù)第二條性質(zhì)得則根據(jù)第二條性質(zhì)得 2k-1 -1 n 2k -1則則 2

12、k-1 n 2k即即 k-1 log2n n，則該結(jié)點(diǎn)無(wú)左孩子，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為否則，編號(hào)為 2i 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)左孩子結(jié)點(diǎn)；(3) 若若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)。206.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)結(jié)構(gòu)； 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 二叉樹(shù)的結(jié)構(gòu)是非線(xiàn)性的，每一個(gè)結(jié)二叉樹(shù)的結(jié)構(gòu)是非線(xiàn)性的，每一個(gè)結(jié)點(diǎn)最多可有兩個(gè)后繼。點(diǎn)最多可有兩個(gè)后繼。21A B C D E F G H IJ K L

13、6.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)的數(shù)據(jù)元素是用一組連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)的數(shù)據(jù)元素 。ABCDEFGHIJKL一維數(shù)組一維數(shù)組bt1.n A B D C E F1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF2511437 可見(jiàn)，對(duì)于一般的二叉樹(shù)，按照完全二叉樹(shù)可見(jiàn)，對(duì)于一般的二叉樹(shù)，按照完全二叉樹(shù)的編號(hào)來(lái)存儲(chǔ)，會(huì)造成空間的極大浪費(fèi)。的編號(hào)來(lái)存儲(chǔ)，會(huì)造成空間的極大浪費(fèi)。A B C D單支樹(shù)就是一個(gè)極端情況：?jiǎn)沃?shù)就是一個(gè)極端情況：1 3 7 15 ABCD單支

14、樹(shù)單支樹(shù)1371524root6.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)： 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 二叉鏈表二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):lchildrchilddataABCDEFGABCDEFG typedef struct Node DataType data; struct Node * lchild; struct Node * rchild; BiTNode, *BiTree; 256.2 二叉樹(shù)二叉樹(shù)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)： 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 三叉鏈表三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):lchildrchildd

15、ataABCDEFGparentrootABCDEFG 返回返回266.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)遍歷二叉樹(shù)：遍歷二叉樹(shù)：順著某一條搜索路徑順著某一條搜索路徑巡訪(fǎng)巡訪(fǎng)二叉樹(shù)中的結(jié)點(diǎn)，使二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)得每個(gè)結(jié)點(diǎn)均被訪(fǎng)問(wèn)一次均被訪(fǎng)問(wèn)一次，而且，而且僅被訪(fǎng)問(wèn)一次僅被訪(fǎng)問(wèn)一次。“遍歷遍歷”是任何類(lèi)型均有的操作，對(duì)線(xiàn)性結(jié)構(gòu)而是任何類(lèi)型均有的操作，對(duì)線(xiàn)性結(jié)構(gòu)而言，只有一條搜索路徑言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼個(gè)后繼)，故不需要另加討論。，故不需要另加討論。二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有二叉樹(shù)是非線(xiàn)性結(jié)

16、構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼兩個(gè)后繼，則存在如何遍歷即則存在如何遍歷即按什么樣的搜索路徑遍歷按什么樣的搜索路徑遍歷的問(wèn)題的問(wèn)題。276.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) “二叉樹(shù)二叉樹(shù)”由三個(gè)基本單元組成：根結(jié)點(diǎn)、左由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。若能依次遍歷這三部分，就遍歷了子樹(shù)和右子樹(shù)。若能依次遍歷這三部分，就遍歷了整個(gè)二叉樹(shù)。整個(gè)二叉樹(shù)。設(shè)用設(shè)用L、D、R分別表示遍歷左子樹(shù)、訪(fǎng)問(wèn)根分別表示遍歷左子樹(shù)、訪(fǎng)問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)結(jié)點(diǎn)、遍歷右子樹(shù)，對(duì)，對(duì)“二叉樹(shù)二叉樹(shù)”而言，可以有而言，可以有6種搜索路徑：種搜索路徑：DLRDRLLDRRDL

17、LRDRLD先左后右先左后右先右后左先右后左286.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)先（根）序的遍歷算法：先（根）序的遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪(fǎng)問(wèn)）訪(fǎng)問(wèn)根根結(jié)點(diǎn)；結(jié)點(diǎn)；（2）先序先序遍歷遍歷左左子樹(shù)；子樹(shù)；（3）先序先序遍歷遍歷右右子樹(shù)。子樹(shù)。ABCDEFGA B D G C E F先序遍歷結(jié)果：先序遍歷結(jié)果：ABDGCEF296.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)中（根）序的遍歷算法：中（根）序的遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉

18、樹(shù)為空樹(shù)，則空操作；否則，（1）中序中序遍歷遍歷左左子樹(shù)；子樹(shù)； （2）訪(fǎng)問(wèn)）訪(fǎng)問(wèn)根根結(jié)點(diǎn)；結(jié)點(diǎn)；（3）中序中序遍歷遍歷右右子樹(shù)。子樹(shù)。ABCDEFGABD GCEF中序遍歷結(jié)果：中序遍歷結(jié)果：ABDGCEF306.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)后（根）序的遍歷算法：后（根）序的遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序后序遍歷遍歷左左子樹(shù)；子樹(shù)； （2）后序后序遍歷遍歷右右子樹(shù)；子樹(shù)； （3）訪(fǎng)問(wèn)）訪(fǎng)問(wèn)根根結(jié)點(diǎn)。結(jié)點(diǎn)。ABCDEFGABDGCE F后序遍歷結(jié)果：后序遍歷結(jié)果：ABDGCEF先序遍歷：先

19、序遍歷： A、B、D、F、G、C、E、H 。ABCDFGEH例如例如:中序遍歷：中序遍歷： B、F、D、G、A、C、E、H 。后序遍歷：后序遍歷： F、G、D、B、H、E、C、A 。 abcdefghij又如又如:先序遍歷先序遍歷: a b d h i e j c f g中序遍歷中序遍歷: h d i b j e a f c g后序遍歷后序遍歷: h i d j e b f g c a336.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)舉例：舉例：-+/a*ef-bcd先序：先序：-+a*b-cd/ef中序：中序：a+b*c-d- e / f后序：后序：ab

20、c d -*+ef/-前綴式（波蘭式）前綴式（波蘭式）中綴式中綴式后綴式（逆波蘭式）后綴式（逆波蘭式）3434ABCDEFGHK先序序列先序序列:ABCDEFGHK中序序列中序序列: BDCAHGKFE后序序列后序序列: DCBHKGFEA6.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)由遍歷序列確定二叉樹(shù)由遍歷序列確定二叉樹(shù)356.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)由遍歷序列確定二叉樹(shù)由遍歷序列確定二叉樹(shù)由先序和中序序列恢復(fù)二叉樹(shù)由先序和中序序列恢復(fù)二叉樹(shù)二叉樹(shù)的先序序列二叉樹(shù)的先序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)

21、根根二叉樹(shù)的中序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根366.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)由遍歷序列確定二叉樹(shù)由遍歷序列確定二叉樹(shù)由先序和中序序列恢復(fù)二叉樹(shù)由先序和中序序列恢復(fù)二叉樹(shù)舉例舉例先序序列：先序序列：A B C D E F G中序序列：中序序列：C B D A E G FAA左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)ABBBCCCDDDEEEFFFGGG376.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)具體的遍歷算法具體的遍歷算法（以（以二叉鏈表二叉鏈表為存儲(chǔ)結(jié)構(gòu)）為存儲(chǔ)結(jié)構(gòu)）：先序遍歷算法先序遍歷算法

22、void PreOrder(BiTree root) if (root!=NULL) Visit(root -data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ PreOrder(root -LChild); /*先序遍歷左子樹(shù)先序遍歷左子樹(shù)*/ PreOrder(root -RChild); /*先序遍歷右子樹(shù)先序遍歷右子樹(shù)*/ 386.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)具體的遍歷算法具體的遍歷算法（以（以二叉鏈表二叉鏈表為存儲(chǔ)結(jié)構(gòu)）為存儲(chǔ)結(jié)構(gòu)）：中序遍歷算法中序遍歷算法void InOrder(BiTree root) if (root!=NULL)

23、InOrder(root -LChild); /*中序遍歷左子樹(shù)中序遍歷左子樹(shù)*/ Visit(root -data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ InOrder(root -RChild); /*中序遍歷右子樹(shù)中序遍歷右子樹(shù)*/ 396.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)具體的遍歷算法具體的遍歷算法（以（以二叉鏈表二叉鏈表為存儲(chǔ)結(jié)構(gòu)）為存儲(chǔ)結(jié)構(gòu)）：后序遍歷算法后序遍歷算法void PostOrder(BiTree root) if (root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹(shù)后序遍歷左子樹(shù)*/

24、 PostOrder(root -RChild); /*后序遍歷右子樹(shù)后序遍歷右子樹(shù)*/ Visit(root -data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ 406.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)遍歷算法應(yīng)用：遍歷算法應(yīng)用：遍歷算法將走遍二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹(shù)遍歷算法將走遍二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹(shù)中結(jié)點(diǎn)并無(wú)次序要求，因此可用任一種算法來(lái)完成。中結(jié)點(diǎn)并無(wú)次序要求，因此可用任一種算法來(lái)完成。 void PreOrder(BiTree root) if (root!=NULL) printf (root -data); /* 輸

25、出根結(jié)點(diǎn)輸出根結(jié)點(diǎn) */ PreOrder(root -LChild); /* 先序遍歷左子樹(shù)先序遍歷左子樹(shù) */ PreOrder(root -RChild); /* 先序遍歷右子樹(shù)先序遍歷右子樹(shù) */ 輸出二叉樹(shù)中的結(jié)點(diǎn)輸出二叉樹(shù)中的結(jié)點(diǎn)416.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)遍歷算法應(yīng)用：遍歷算法應(yīng)用：條件：條件：判斷結(jié)點(diǎn)既判斷結(jié)點(diǎn)既沒(méi)有左孩子沒(méi)有左孩子，又，又沒(méi)有右孩子沒(méi)有右孩子時(shí)，則時(shí)，則輸出該結(jié)點(diǎn)輸出該結(jié)點(diǎn)。 void PreOrderLeaf(BiTree root) if (root!=NULL) if (root -LChild

26、=NULL & root -RChild=NULL) printf (root -data); /* 輸出葉結(jié)點(diǎn)輸出葉結(jié)點(diǎn) */ PreOrderLeaf(root -LChild); /* 先序遍歷左子樹(shù)先序遍歷左子樹(shù) */ PreOrderLeaf(root -RChild); /* 先序遍歷右子樹(shù)先序遍歷右子樹(shù) */ 輸出二叉樹(shù)中的葉子結(jié)點(diǎn)輸出二叉樹(shù)中的葉子結(jié)點(diǎn)426.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)遍歷算法應(yīng)用：遍歷算法應(yīng)用：/* LeafCount保存葉子結(jié)點(diǎn)數(shù)目的全局變量保存葉子結(jié)點(diǎn)數(shù)目的全局變量,調(diào)用之前初始化值為調(diào)用之前初

27、始化值為0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild=NULL & root -RChild=NULL) LeafCount+; 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目方法方法1：436.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)遍歷算法應(yīng)用：遍歷算法應(yīng)用：/* 采用遞歸算法，如果是空樹(shù)，返回采用遞歸算法，如果是空樹(shù)，返回0； 如果只有一個(gè)結(jié)點(diǎn)，返回如果只有一個(gè)結(jié)點(diǎn)，返回1； 否則為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和

28、否則為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和 */int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if(root-LChild=NULL)&(root-RChild=NULL) LeafCount =1; else LeafCount =leaf(root-LChild)+leaf(root-RChild); return LeafCount; 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目方法方法2：446.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)建立二叉鏈表方式存儲(chǔ)的二叉樹(shù)建立二

29、叉鏈表方式存儲(chǔ)的二叉樹(shù)給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說(shuō)的遍歷序列是一種在這里所說(shuō)的遍歷序列是一種“擴(kuò)展的遍歷序列擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹(shù)。通常用特定的元素表示空子樹(shù)。例如例如.擴(kuò)展先序序列：擴(kuò)展先序序列：ABDFGCEHABDFGCEH遍歷算法應(yīng)用：遍歷算法應(yīng)用： void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch=) *bt=NULL; else *b

30、t=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild); 456.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)建立二叉鏈表方式存儲(chǔ)的二叉樹(shù)建立二叉鏈表方式存儲(chǔ)的二叉樹(shù)給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說(shuō)的遍歷序列是一種在這里所說(shuō)的遍歷序列

31、是一種“擴(kuò)展的遍歷序列擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹(shù)。通常用特定的元素表示空子樹(shù)。例如例如.擴(kuò)展先序序列：擴(kuò)展先序序列：ABDFGCEHABDFGCEH遍歷算法應(yīng)用：遍歷算法應(yīng)用： BiTree CreateBiTree( ) char ch; BiTree bt; ch=getchar(); if(ch=) return(NULL); bt=(BiTree)malloc(sizeof(BiTNode); bt-data=ch; bt-LChild=CreateBiTree( ); bt-RChild=CreateBiTree( ); return bt; 466.3 二叉樹(shù)的遍

32、歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 求二叉樹(shù)的高度求二叉樹(shù)的高度設(shè)函數(shù)表示二叉樹(shù)設(shè)函數(shù)表示二叉樹(shù)bt的高度，則遞歸定義如下的高度，則遞歸定義如下: 若若bt為空，則高度為為空，則高度為0 若若bt非空，其高度應(yīng)為其左右子樹(shù)高度的最大值加非空，其高度應(yīng)為其左右子樹(shù)高度的最大值加1遍歷算法應(yīng)用：遍歷算法應(yīng)用：左左子子樹(shù)樹(shù)右右子子樹(shù)樹(shù)bthlhrHigh=max(hl,hr)+1 int PostTreeDepth(BiTree bt) int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); hr=PostTr

33、eeDepth(bt-RChild); max=hlhr?hl:hr; return(max+1); else return(0); 476.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)按樹(shù)狀打印的二叉樹(shù)按樹(shù)狀打印的二叉樹(shù)假設(shè)以二叉鏈表存儲(chǔ)的二叉樹(shù)中，每個(gè)結(jié)點(diǎn)所含數(shù)假設(shè)以二叉鏈表存儲(chǔ)的二叉樹(shù)中，每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，要求實(shí)現(xiàn)如下圖的打印結(jié)果。據(jù)元素均為單字母，要求實(shí)現(xiàn)如下圖的打印結(jié)果。遍歷算法應(yīng)用：遍歷算法應(yīng)用：ABCDEF輸出輸出CFAEDB void PrintTree(TreeNode bt,int nLayer) if(bt = =NULL

34、) return; PrintTree(bt -Rchild,nLayer+1); for(int i=0;idata); PrintTree(bt - Lchild,nLayer+1); 486.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)中序遍歷二叉樹(shù)的非遞歸算法中序遍歷二叉樹(shù)的非遞歸算法基于棧的遞歸消除：基于棧的遞歸消除：從根開(kāi)始，當(dāng)前結(jié)點(diǎn)存在或棧不為空，重復(fù)如下操作：從根開(kāi)始，當(dāng)前結(jié)點(diǎn)存在或棧不為空，重復(fù)如下操作： 1、當(dāng)前結(jié)點(diǎn)進(jìn)棧，走左子樹(shù)，直至左子樹(shù)為空；、當(dāng)前結(jié)點(diǎn)進(jìn)棧，走左子樹(shù)，直至左子樹(shù)為空； 2、退棧并訪(fǎng)問(wèn)；、退棧并訪(fǎng)問(wèn)； 3、走右子樹(shù)；、

35、走右子樹(shù)；49void InOrder（BiTree root） InitStack (&S); p=root; while(p!=NULL | !IsEmpty(S) if (p!=NULL) /* 根指針進(jìn)棧，遍歷左子樹(shù)根指針進(jìn)棧，遍歷左子樹(shù) */ Push(&S,p); p=p-LChild; else /*根指針退棧，訪(fǎng)問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)根指針退棧，訪(fǎng)問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)*/ Pop(&S,&p); Visit(p-data); p=p-RChild; 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：空間復(fù)雜度：O(k)第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉

36、樹(shù)中序遍歷二叉樹(shù)的非遞歸算法中序遍歷二叉樹(shù)的非遞歸算法 調(diào)用棧操作調(diào)用棧操作( SM表示棧，TOP表示棧頂指針)Void inorder(BiTree root) do while(p!=NULL) if (topM) return(overflow); top=top+1; stop=p; p=p-Lchild; /*進(jìn)入左子樹(shù)進(jìn)入左子樹(shù)*/ if(top!=0) p=stop; top=top-1; Visit(p-data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ p=p-Rchild; /*進(jìn)入右子樹(shù)進(jìn)入右子樹(shù)*/ while(p!=NULL|top!=0) 第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉

37、樹(shù)中序遍歷二叉樹(shù)的非遞歸算法中序遍歷二叉樹(shù)的非遞歸算法 直接實(shí)現(xiàn)棧操作直接實(shí)現(xiàn)棧操作算法思想：算法思想：從根開(kāi)始，當(dāng)前結(jié)點(diǎn)存在或棧不為空，重復(fù)如下操作：從根開(kāi)始，當(dāng)前結(jié)點(diǎn)存在或棧不為空，重復(fù)如下操作： 1、當(dāng)前結(jié)點(diǎn)進(jìn)棧，走左子樹(shù)，直至左子樹(shù)為空；、當(dāng)前結(jié)點(diǎn)進(jìn)棧，走左子樹(shù)，直至左子樹(shù)為空； 2、如果棧頂結(jié)點(diǎn)右子樹(shù)為空或右子樹(shù)已訪(fǎng)問(wèn)過(guò)，則退、如果棧頂結(jié)點(diǎn)右子樹(shù)為空或右子樹(shù)已訪(fǎng)問(wèn)過(guò)，則退 棧并訪(fǎng)問(wèn)剛退棧的棧頂結(jié)點(diǎn)；棧并訪(fǎng)問(wèn)剛退棧的棧頂結(jié)點(diǎn)； 3、否則，走右子樹(shù)；、否則，走右子樹(shù)；判定右子樹(shù)是否已訪(fǎng)問(wèn)過(guò)有多種方法，在此采用：判定右子樹(shù)是否已訪(fǎng)問(wèn)過(guò)有多種方法，在此采用：q記錄記錄剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)，并判定棧

38、頂結(jié)點(diǎn)右孩子是否為剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)，并判定棧頂結(jié)點(diǎn)右孩子是否為q。 后序遍歷非遞歸較上述算法的主要區(qū)別在于：后序遍歷非遞歸較上述算法的主要區(qū)別在于：要要判定是否應(yīng)判定是否應(yīng)訪(fǎng)問(wèn)訪(fǎng)問(wèn)當(dāng)前棧頂結(jié)點(diǎn)當(dāng)前棧頂結(jié)點(diǎn)p。1. p無(wú)右孩子；無(wú)右孩子；2. p的右孩子已訪(fǎng)問(wèn)過(guò)，此的右孩子已訪(fǎng)問(wèn)過(guò)，此時(shí)應(yīng)訪(fǎng)問(wèn)棧頂結(jié)點(diǎn)時(shí)應(yīng)訪(fǎng)問(wèn)棧頂結(jié)點(diǎn)p，除這兩種情況外，均應(yīng)進(jìn)入右子樹(shù)訪(fǎng)問(wèn)。，除這兩種情況外，均應(yīng)進(jìn)入右子樹(shù)訪(fǎng)問(wèn)。 第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)后序遍歷二叉樹(shù)的非遞歸算法后序遍歷二叉樹(shù)的非遞歸算法void PostOrder（BiTree root） BiTNode * p,*q； BiTree Sstack-s

39、ize； int top=0; q=NULL; p=root; while(p!=NULL | top!=0) while(p!=NULL) top=+; if(top=stack-size) return(overflow); stop=p; p=p-LChild; if(top0) p=stop; if(p-RChild=NULL) |(p-RChild=q) visit(p-data); q=p; top-; p=NULL; else p=p-RChild; free(s); 后序遍歷二叉樹(shù)的非遞歸算法后序遍歷二叉樹(shù)的非遞歸算法第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)536.3 二叉樹(shù)的遍歷

40、與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)基本概念基本概念線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù) 以二叉鏈表作為二叉樹(shù)存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到以二叉鏈表作為二叉樹(shù)存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，不能直接得到結(jié)點(diǎn)在遍結(jié)點(diǎn)的左、右孩子信息，不能直接得到結(jié)點(diǎn)在遍歷序列中的歷序列中的前驅(qū)前驅(qū)和和后繼后繼信息。若要得到這些信息，信息。若要得到這些信息，可充分利用二叉鏈表中的可充分利用二叉鏈表中的空鏈域空鏈域，將遍歷過(guò)程中，將遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來(lái)。結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來(lái)。 在有在有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)鏈域，個(gè)鏈域，但只有但只有n-1個(gè)有用的

41、非空鏈域，其余個(gè)有用的非空鏈域，其余n+1個(gè)鏈域個(gè)鏈域是空的。是空的。LChildLtagDataRtagRChild546.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù)Ltag=0 LChild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子1 LChild域指示結(jié)點(diǎn)的遍歷前驅(qū)域指示結(jié)點(diǎn)的遍歷前驅(qū)Rtag=0 RChild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 RChild域指示結(jié)點(diǎn)的遍歷后繼域指示結(jié)點(diǎn)的遍歷后繼556.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)在這種存儲(chǔ)結(jié)構(gòu)中，指向在這種存

42、儲(chǔ)結(jié)構(gòu)中，指向前驅(qū)前驅(qū)和和后繼后繼結(jié)點(diǎn)的指針叫做結(jié)點(diǎn)的指針叫做線(xiàn)索線(xiàn)索。線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù)以這種結(jié)構(gòu)組成的二叉鏈表作為二以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做線(xiàn)索鏈表線(xiàn)索鏈表。對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷并對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷并且加上線(xiàn)索的過(guò)程叫做且加上線(xiàn)索的過(guò)程叫做線(xiàn)索化線(xiàn)索化。線(xiàn)索化了的二叉樹(shù)稱(chēng)為線(xiàn)索化了的二叉樹(shù)稱(chēng)為線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù)。566.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)線(xiàn)索化實(shí)質(zhì)上是將二叉鏈表中的空指針域線(xiàn)索化實(shí)質(zhì)上是將二叉鏈表中的空指針域填上相應(yīng)結(jié)點(diǎn)的遍歷前驅(qū)或后繼結(jié)點(diǎn)的地填上相應(yīng)結(jié)點(diǎn)的遍歷前驅(qū)

43、或后繼結(jié)點(diǎn)的地址，而前驅(qū)和后繼的地址只能在動(dòng)態(tài)的遍址，而前驅(qū)和后繼的地址只能在動(dòng)態(tài)的遍歷過(guò)程中才能得到。因此歷過(guò)程中才能得到。因此線(xiàn)索化的過(guò)程是線(xiàn)索化的過(guò)程是在遍歷過(guò)程中修改空指針域的過(guò)程。在遍歷過(guò)程中修改空指針域的過(guò)程。 對(duì)二對(duì)二叉樹(shù)按照不同的遍歷次序進(jìn)行線(xiàn)索化，可叉樹(shù)按照不同的遍歷次序進(jìn)行線(xiàn)索化，可以得到不同的線(xiàn)索二叉樹(shù)以得到不同的線(xiàn)索二叉樹(shù) （先序線(xiàn)索二叉先序線(xiàn)索二叉樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)）。）。二叉樹(shù)的線(xiàn)索化二叉樹(shù)的線(xiàn)索化576.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)舉例：舉例：ABCDGEFH先序

44、序列：先序序列：ABDGCEHFABCDGEFHNULLABCDGEFH中序序列：中序序列：DGBAEHCFNULLNULLABCDGEFH后序序列：后序序列：GDBHEFCANULL586.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域，在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪(fǎng)問(wèn)結(jié)點(diǎn)的以保存當(dāng)前訪(fǎng)問(wèn)結(jié)點(diǎn)的“前驅(qū)前驅(qū)”和和“后繼后繼”信信息。遍歷過(guò)程中，附設(shè)指針息。遍歷過(guò)程中，附設(shè)指針pre, 并始終保持指并始終保持指針針pre指向當(dāng)前訪(fǎng)問(wèn)的、指針指向當(dāng)前訪(fǎng)問(wèn)的、指針p所指結(jié)點(diǎn)的前驅(qū)所指結(jié)點(diǎn)的前驅(qū)。建立線(xiàn)索鏈表

45、建立線(xiàn)索鏈表596.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)中序線(xiàn)索化算法中序線(xiàn)索化算法void Inthread(BiTree root) if (root!=NULL) Inthread(root-LChild); /* 線(xiàn)索化左子樹(shù)線(xiàn)索化左子樹(shù) */ if (root-LChild=NULL) root-Ltag=1; root-LChild=pre; if (pre!=NULL& pre-RChild=NULL) pre- RChild=root; pre-Rtag=1; pre=root； Inthread(root-RChild);

46、/*線(xiàn)索化右子樹(shù)線(xiàn)索化右子樹(shù)*/ 606.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)在線(xiàn)索二叉樹(shù)中找前驅(qū)、后繼結(jié)點(diǎn)在線(xiàn)索二叉樹(shù)中找前驅(qū)、后繼結(jié)點(diǎn)（以中序?yàn)槔ㄒ灾行驗(yàn)槔┰谥行蚓€(xiàn)索樹(shù)中找結(jié)點(diǎn)前驅(qū)：在中序線(xiàn)索樹(shù)中找結(jié)點(diǎn)前驅(qū)： 左子樹(shù)的左子樹(shù)的“最右下端最右下端”結(jié)點(diǎn)結(jié)點(diǎn)BiTNode *InPre(BiTNode *p) if(p-Ltag=1) pre=p-LChild; else for(q=p-LChild;q-Rtag=0;q=q-RChild); pre=q; return(pre);616.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6

47、章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)在線(xiàn)索二叉樹(shù)中找前驅(qū)、后繼結(jié)點(diǎn)在線(xiàn)索二叉樹(shù)中找前驅(qū)、后繼結(jié)點(diǎn)（以中序?yàn)槔ㄒ灾行驗(yàn)槔┰谥行蚓€(xiàn)索樹(shù)中找結(jié)點(diǎn)后繼：在中序線(xiàn)索樹(shù)中找結(jié)點(diǎn)后繼： 右子樹(shù)的右子樹(shù)的“最左下端最左下端”結(jié)點(diǎn)結(jié)點(diǎn)BiTNode *InNext(BiTNode *p) if(p-Rtag=1) Next=p-RChild; else for(q=p-RChild;q-Ltag=0;q=q-LChild); Next=q; return(Next);626.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)線(xiàn)索二叉樹(shù)的運(yùn)算：線(xiàn)索二叉樹(shù)的運(yùn)算：插入插入（做某結(jié)點(diǎn)的右孩子

48、）（做某結(jié)點(diǎn)的右孩子）FprABCDEABCDEprF r-RChild=p-RChild;p-RChild=r;r-LChilid=p;可交換順序可交換順序636.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)線(xiàn)索二叉樹(shù)的運(yùn)算：線(xiàn)索二叉樹(shù)的運(yùn)算：插入插入（做某結(jié)點(diǎn)的右孩子）（做某結(jié)點(diǎn)的右孩子）FprABCDEGHrABCDEFpGHs=p-RChild;while(s-Ltag=0) s=s-LChild;s-LChild=r;r-LChild=p; r-RChild=p-RChild;p-RChild=r;646.3 二叉樹(shù)的遍歷與線(xiàn)索化二叉樹(shù)的遍歷與線(xiàn)索

49、化第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)線(xiàn)索二叉樹(shù)的運(yùn)算：線(xiàn)索二叉樹(shù)的運(yùn)算：插入插入（做某結(jié)點(diǎn)的右孩子）（做某結(jié)點(diǎn)的右孩子）算法算法void InsNode(BiTNode *p,BiTNode *r) if(p-Rtag=1) r-RChild=p-RChild; r-Rtag=1; p-RChilid=r; r-LChild=p; r-Ltag=1; else s=p-RChild; while(s-Ltag=0) s=s-LChild; s-LChild=r; r-LChild=p; r-Ltag=1; r-RChild=p-RChild; r-Rtag=0; p-RChild=r; 返回

50、返回656.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 雙親表示法雙親表示法dataparentABCDGEFparentdata結(jié)點(diǎn)序號(hào)結(jié)點(diǎn)序號(hào)0123456A-1B0C0D1E1F1G2666.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 雙親表示法雙親表示法存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)#define MAX 100typedef struct TNode DataType data; int parent; TNode;typedef struct TNo

51、de treeMAX; int nodenum;ParentTree;676.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 孩子表示法孩子表示法ABCDGEF0123456ABCDEFG12 345 6 686.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 孩子表示法孩子表示法存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)typedef struct ChildNode int Child; struct ChildNode *next;ChildNode;typedef stru

52、ct DataType data; ChildNode *FirstChild;DataNode;typedef struct DataNode nodesMAX; int root; int num;ChildTree;696.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 孩子兄弟表示法孩子兄弟表示法data下一個(gè)兄弟結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)ABCDGEFABDCEFG706.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的三種存儲(chǔ)結(jié)構(gòu)樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 孩子兄

53、弟表示法孩子兄弟表示法data下一個(gè)兄弟結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)typedef struct CSNode DataType data; struct CSNode *FirstChild; struct CSNode *NextSibling;CSNode,*CSTree;716.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)轉(zhuǎn)化規(guī)則：轉(zhuǎn)化規(guī)則：.樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)；樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)；.對(duì)樹(shù)中每一個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子

54、結(jié)對(duì)樹(shù)中每一個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn)，刪去其與其他孩子結(jié)點(diǎn)之間的連線(xiàn)；點(diǎn)之間的連線(xiàn)，刪去其與其他孩子結(jié)點(diǎn)之間的連線(xiàn)；.以樹(shù)的根結(jié)點(diǎn)位軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定以樹(shù)的根結(jié)點(diǎn)位軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。的角度，使之結(jié)構(gòu)層次分明。726.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)例如：例如：ABCDGEFH.樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)；樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)；.對(duì)樹(shù)中每一個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)對(duì)樹(shù)中每一個(gè)結(jié)點(diǎn)，只保留其與第一

55、個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn)，刪去其與其他孩子結(jié)點(diǎn)之間的連線(xiàn)；點(diǎn)之間的連線(xiàn)，刪去其與其他孩子結(jié)點(diǎn)之間的連線(xiàn)；.以樹(shù)的根結(jié)點(diǎn)位軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定以樹(shù)的根結(jié)點(diǎn)位軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。的角度，使之結(jié)構(gòu)層次分明。GABCDEFH736.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化森林森林二叉樹(shù)二叉樹(shù).將森林中的每棵樹(shù)轉(zhuǎn)化成相應(yīng)的二叉樹(shù)；將森林中的每棵樹(shù)轉(zhuǎn)化成相應(yīng)的二叉樹(shù)；.第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根

56、結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連接在一起后，所得到的二叉樹(shù)就是由森林當(dāng)所有二叉樹(shù)連接在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。轉(zhuǎn)換得到的二叉樹(shù)。 轉(zhuǎn)化規(guī)則：轉(zhuǎn)化規(guī)則：74GHIJ6.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化森林森林二叉樹(shù)二叉樹(shù)例如：例如：ABCDEF.將森林中的每棵樹(shù)轉(zhuǎn)化成相應(yīng)的二叉樹(shù)；將森林中的每棵樹(shù)轉(zhuǎn)化成相應(yīng)的二叉樹(shù)；EFGHIJABCD.第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的第一棵

57、二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連接在一起根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連接在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。 ABCDEFGHIJ756.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化二叉樹(shù)二叉樹(shù)樹(shù)或森林樹(shù)或森林.若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)的雙親

58、結(jié)點(diǎn)用線(xiàn)連起來(lái)；都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線(xiàn)連起來(lái)；.刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)；刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)；轉(zhuǎn)化規(guī)則：轉(zhuǎn)化規(guī)則：.整理由前兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。整理由前兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。76GHIJ6.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)化二叉樹(shù)二叉樹(shù)樹(shù)或森林樹(shù)或森林例如：例如：ABCDEF.若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)

59、的雙親結(jié)點(diǎn)用線(xiàn)連起來(lái)；都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線(xiàn)連起來(lái)；.刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)；刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)；ABCDEFGHIJ.整理由前兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。整理由前兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。776.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)與森林的遍歷樹(shù)與森林的遍歷樹(shù)的遍歷樹(shù)的遍歷.先根先根(次序次序)遍歷遍歷:.后根后根(次序次序)遍歷遍歷:可有三條搜索路徑可有三條搜索路徑:.按層次遍歷按層次遍歷:若樹(shù)不空，則先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先訪(fǎng)問(wèn)根結(jié)點(diǎn)

60、，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。若樹(shù)不空，則自上而下自左至右訪(fǎng)問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。若樹(shù)不空，則自上而下自左至右訪(fǎng)問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。786.4 樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)、森林與二叉樹(shù)的關(guān)系第第 6 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)與森林的遍歷樹(shù)與森林的遍歷樹(shù)的遍歷樹(shù)的遍歷.先根先根(次序次序)遍歷遍歷:.后根后根(次序次序)遍歷遍歷:例如例如:.按層次遍歷按層次遍歷:若樹(shù)不空，則先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。若樹(shù)不