01數(shù)據(jù)結(jié)構(gòu)講義06第六章樹和二叉樹1

1、第六章第六章 樹和二叉樹樹和二叉樹基本內(nèi)容基本內(nèi)容二叉樹的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹的遍歷和線索化算法；樹的定義、存儲(chǔ)結(jié)構(gòu)、樹與二叉樹的轉(zhuǎn)換、樹的遍歷；哈夫曼樹的構(gòu)造；學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)1掌握二叉樹的結(jié)構(gòu)特性，2熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；3遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。掌握各種遍歷策略的遞歸算法，能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；4理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，掌握二叉樹的線索化過(guò)程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。5熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和與二叉樹的轉(zhuǎn)換方法，掌握樹的遍歷方法；6了解哈夫曼樹

2、的特性，掌握構(gòu)造哈夫曼樹和哈夫曼編碼的方法；第六章第六章 樹和二叉樹樹和二叉樹 樹型結(jié)構(gòu)是一類重要的樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹和二叉樹最。其中以樹和二叉樹最為常用，直觀看來(lái)，為常用，直觀看來(lái)，樹是以分支關(guān)系定義的層次結(jié)構(gòu)樹是以分支關(guān)系定義的層次結(jié)構(gòu)，樹結(jié)構(gòu)在客，樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹來(lái)形象表示。樹在汁算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯程序樹來(lái)形象表示。樹在汁算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯程序中，可用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹形中，可

3、用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹形結(jié)構(gòu)也是信息的重要組織形式之一。結(jié)構(gòu)也是信息的重要組織形式之一。 本章重點(diǎn)討論二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，并研究樹和森本章重點(diǎn)討論二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，并研究樹和森林與二叉樹的轉(zhuǎn)換關(guān)系，林與二叉樹的轉(zhuǎn)換關(guān)系，最后介紹幾個(gè)應(yīng)用例子。最后介紹幾個(gè)應(yīng)用例子。第六章第六章 樹和二叉樹樹和二叉樹 6.1 6.1 樹的定義和基本術(shù)語(yǔ)樹的定義和基本術(shù)語(yǔ)1.樹的概念2. 樹的應(yīng)用3.樹的表示4.樹的有關(guān)術(shù)語(yǔ)5樹的基本操作6.16.1 樹的定義和基本術(shù)語(yǔ)樹的定義和基本術(shù)語(yǔ)1樹的概念樹的概念 樹結(jié)構(gòu) （除了一個(gè)稱為根的結(jié)點(diǎn)外）每個(gè)元素都有且僅有一個(gè)直接

4、每個(gè)元素都有且僅有一個(gè)直接前趨，有且僅有零個(gè)或多個(gè)直接后繼。前趨，有且僅有零個(gè)或多個(gè)直接后繼。樹是n個(gè)結(jié)點(diǎn)的有限集合，在任一棵非空樹中：（1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)。有且僅有一個(gè)稱為根的結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)可分為個(gè)互不相交的集合，而且這些集合中的每一其余結(jié)點(diǎn)可分為個(gè)互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念J JI IA AC CB BD DH HG GF FE E例：下面的圖是一棵樹T=A, B, C, D, E, F, G, H, I, J

5、T=A, B, C, D, E, F, G, H, I, J A A是根，是根，其余結(jié)點(diǎn)可以劃分為其余結(jié)點(diǎn)可以劃分為3 3個(gè)個(gè)互不相交的集合互不相交的集合：T1=B, E, F , T2=C, D , T3=D, H, I, JT1=B, E, F , T2=C, D , T3=D, H, I, J 這些集合中的每一集合都本身又是一棵樹這些集合中的每一集合都本身又是一棵樹,它們是它們是A的子樹。的子樹。 例如例如 對(duì)于對(duì)于 T1T1，B B是根，其余結(jié)點(diǎn)可以劃分為是根，其余結(jié)點(diǎn)可以劃分為2 2個(gè)個(gè)互不相交互不相交的集合：的集合：T11=E，T12=F，T11,T12 是是B的子樹。的子樹。J

6、JI IA AC CB BD DH HG GF FE E從邏輯結(jié)構(gòu)看：從邏輯結(jié)構(gòu)看：1）樹中只有根結(jié)點(diǎn)沒(méi)有前趨；樹中只有根結(jié)點(diǎn)沒(méi)有前趨；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)J JI IA AC CB BD DH HG GF FE E2樹的應(yīng)用樹的應(yīng)用1）樹可表示具有分支結(jié)構(gòu)關(guān)系的對(duì)象）樹可表示具有分支結(jié)構(gòu)關(guān)系的對(duì)象例例1家族族譜家族族譜 設(shè)某家庭有

7、設(shè)某家庭有10個(gè)成員個(gè)成員A、B、C、D、E、F、G、H、I、J，他們之間的關(guān)系可下圖所示的樹表示：他們之間的關(guān)系可下圖所示的樹表示：例例2單位行政機(jī)構(gòu)的組織關(guān)系單位行政機(jī)構(gòu)的組織關(guān)系J JI IA AC CB BD DH HG GF FE E2）樹是常用的數(shù)據(jù)組織形式）樹是常用的數(shù)據(jù)組織形式有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來(lái)組織。管理和使用數(shù)據(jù)，將它們用樹的形式來(lái)組織。例例3 計(jì)算機(jī)的文件系統(tǒng)計(jì)算機(jī)的文件系統(tǒng) 不論是不論是DOS文件系統(tǒng)還是文件系統(tǒng)還是window文件系統(tǒng)，所有

8、的文件是用樹的形文件系統(tǒng)，所有的文件是用樹的形式來(lái)組織的。式來(lái)組織的。文件夾1 文件夾n 文件1 文件2文件夾11 文件夾12 文件11 文件12C C3樹的表示樹的表示(P120) 1）嵌套集合圖示表示）嵌套集合圖示表示 2）廣義表表示）廣義表表示 3）凹入表示法（類似書的目錄）凹入表示法（類似書的目錄）4樹的樹的 基本術(shù)語(yǔ)基本術(shù)語(yǔ)樹的結(jié)點(diǎn)：樹的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支；包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支；孩子結(jié)點(diǎn)：孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；雙親結(jié)點(diǎn)：雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，則結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是結(jié)點(diǎn)是B結(jié)點(diǎn)

9、的雙親；結(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)的層定義為1；根的孩子為第二層結(jié)點(diǎn)；根的孩子為第二層結(jié)點(diǎn),依此類推；依此類推；樹的高度樹的高度：樹中：樹中最大最大的結(jié)點(diǎn)層的結(jié)點(diǎn)層結(jié)點(diǎn)的度：結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù)結(jié)點(diǎn)子樹的個(gè)數(shù)樹的度：樹的度： 樹中樹中最大最大的結(jié)點(diǎn)度。的結(jié)點(diǎn)度。葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)也叫終端結(jié)點(diǎn)，是度為，是度為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；分支結(jié)點(diǎn)：分支結(jié)點(diǎn)：度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；森林；森林；互不相交的樹集合；互不相交的樹集合；有序樹有序樹：子樹有序的樹：

10、子樹有序的樹(自左到右自左到右)，如：家族樹；，如：家族樹；無(wú)序樹無(wú)序樹：不考慮子樹的順序；：不考慮子樹的順序；5 樹的基本操作樹的基本操作樹的應(yīng)用很廣，應(yīng)用不同基本操作也不同。下面列舉了樹的一些樹的應(yīng)用很廣，應(yīng)用不同基本操作也不同。下面列舉了樹的一些基本操作：基本操作：（以（以DOS文元件系統(tǒng)為例解釋樹的基本操作）文元件系統(tǒng)為例解釋樹的基本操作） 1 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, definition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDe

11、pth(T); 7） Root(T); 8） Value(T, &cur_e); 樹是一種分支結(jié)構(gòu)的對(duì)象，在樹的概念中，對(duì)每一個(gè)結(jié)點(diǎn)樹是一種分支結(jié)構(gòu)的對(duì)象，在樹的概念中，對(duì)每一個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒(méi)有限制，孩子的個(gè)數(shù)沒(méi)有限制，因此樹的形態(tài)多種多樣，本章我們主要因此樹的形態(tài)多種多樣，本章我們主要討論一種最簡(jiǎn)單的樹討論一種最簡(jiǎn)單的樹二叉樹。二叉樹。9） Assign(T, cur_e, value); 10）Paret(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &am

12、p;p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( );6.26.2 二二 叉叉 樹樹6.2.1 6.2.1 二叉樹的定義二叉樹的定義二叉樹：二叉樹： 或?yàn)榭諛?，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且或?yàn)榭諛?，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。左、右子樹本身也是二叉樹。說(shuō)明說(shuō)明1 1）二叉樹中）二叉樹中每個(gè)結(jié)點(diǎn)最多有兩顆子樹每個(gè)結(jié)點(diǎn)最多有兩顆子樹；二叉樹；二叉樹每個(gè)結(jié)點(diǎn)度小于等于每個(gè)結(jié)點(diǎn)度小于等于2 2; ;2 2）左、右子樹不能顛例）左、右子樹不能顛例有序樹有

13、序樹; ;3 3）二叉樹是）二叉樹是遞歸結(jié)構(gòu)，遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念在二叉樹的定義中又用到了二叉樹的概念; ; A A F F G G E E D D C C B B A A F F G G E E D D C C B B (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 G G E E D D B B C C F F(b)2 二叉樹的基本形態(tài)二叉樹的基本形態(tài)僅有根空左子樹為空右子樹為空左右子樹均為非空3應(yīng)用舉例例1 可以用二叉樹表示表達(dá)式

14、a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -6.2.2 二叉樹性質(zhì)(證明見(jiàn)P124)性質(zhì)1 在二叉樹的第在二叉樹的第i i 層上最多有層上最多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)性質(zhì)2 深度為深度為k k的二叉樹最多有的二叉樹最多有 2 2k k-1 -1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)性質(zhì)3 設(shè)二叉樹葉子結(jié)點(diǎn)數(shù)為設(shè)二叉樹葉子結(jié)點(diǎn)數(shù)為n n0 0，度為，度為2 2的結(jié)點(diǎn)的結(jié)點(diǎn)n n2 2，則，則n n0 0 = = n n2 2 +1+1 A A F F G G E E D D C C B B兩種特殊的二叉樹兩種特殊的二叉樹滿二叉樹滿二叉樹：如果

15、深度為如果深度為k k的二叉樹，有的二叉樹，有2 2k k-1-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹個(gè)結(jié)點(diǎn)則稱為滿二叉樹； A A G G F F E E D D C C B B A A C C B BK=3的滿二叉樹K=2的滿二叉樹完全二叉樹：完全二叉樹：如果一顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大如果一顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹；，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹； A A E E D D C C B B G G A A E E D D C C B B( (a)a)( (c)c)( (b)b)(a)(a)、( (b

16、)b)完全二叉樹( (c) c) 不是完全二叉樹 A A G G F F E E D D C C B B下面是兩個(gè)關(guān)于完全二叉樹的性質(zhì)下面是兩個(gè)關(guān)于完全二叉樹的性質(zhì)性質(zhì)性質(zhì)4 4 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：loglog2 2 n+1n+1性質(zhì)性質(zhì)5 5：對(duì)完全二叉樹的結(jié)點(diǎn)編號(hào)對(duì)完全二叉樹的結(jié)點(diǎn)編號(hào), ,從上到下，每一層從左到右從上到下，每一層從左到右 A A F F E E D D C C B B1 12 23 34 45 56 6在完全二叉樹中編號(hào)為在完全二叉樹中編號(hào)為i i的結(jié)點(diǎn)，的結(jié)點(diǎn)， 1 1）若有左孩子，則左孩編號(hào)為）若有左孩子，則左孩編號(hào)

17、為2 2i i； 2 2）若有右孩子，則有孩子結(jié)點(diǎn)編號(hào)為）若有右孩子，則有孩子結(jié)點(diǎn)編號(hào)為2 2i+1i+1； 3 3）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為i/2i/2；6.2.3 6.2.3 二叉樹的存貯結(jié)構(gòu)二叉樹的存貯結(jié)構(gòu) 1 二叉樹的順序結(jié)構(gòu)完全二叉樹的順序結(jié)構(gòu)用一組連續(xù)的內(nèi)存單元，按編號(hào)順序依次存儲(chǔ)完全二叉樹的元素順序結(jié)構(gòu)圖示1 2 3 4 5 6 7 1 2 3 4 5 6 7 m-1m-1 A B C D E FA B C D E F A A F F E E D D C C B B1 12 23 34 45 56 6一般二叉樹的順序結(jié)構(gòu) 假想，我們補(bǔ)齊二叉樹所缺少的

18、那些結(jié)點(diǎn)，對(duì)二叉樹結(jié)點(diǎn)編號(hào)。 用這種方式對(duì)二叉樹結(jié)點(diǎn)編號(hào)，則在二叉樹中編號(hào)為i的結(jié)點(diǎn)， 1）若有左孩子，則左孩編號(hào)為2i； 2）若有右孩子，則有孩子結(jié)點(diǎn)編號(hào)為2i+1； 3）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為i/2； A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 9 A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 9 A A F F G G E E D D C C B B1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 m-1m-1 A B A B C C D E

19、 D E F F G G一般二叉樹的順序結(jié)構(gòu)圖示將二叉樹原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單元“相應(yīng)相應(yīng)”的位置上2 2 二叉鏈表二叉鏈表 二叉鏈表中每個(gè)結(jié)點(diǎn)至少包含三個(gè)域：二叉鏈表中每個(gè)結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域、左指針域、數(shù)據(jù)域、左指針域、右指針域右指針域 D D A A B B C C E E F F A A F F E E D D C C B B3 3 三叉鏈表三叉鏈表 三叉鏈表中每個(gè)結(jié)點(diǎn)至少包含四個(gè)域：三叉鏈表中每個(gè)結(jié)點(diǎn)至少包含四個(gè)域：數(shù)據(jù)域、雙親指針域、左指數(shù)據(jù)域、雙親指針域、左指針域、右指針域針域、右指針域二叉鏈表圖示4 靜態(tài)鏈表 上面?zhèn)兌骀湵砘蛉骀湵硎侨骀湵硎怯弥羔槍?shí)現(xiàn)，是一種動(dòng)

20、態(tài)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也可用一維數(shù)組來(lái)實(shí)現(xiàn)，用一維數(shù)組表示的二用一維數(shù)組表示的二叉鏈表或三叉鏈表，稱為靜態(tài)鏈表叉鏈表或三叉鏈表，稱為靜態(tài)鏈表 A A F F E E D D C C B B孩子結(jié)點(diǎn)在數(shù)組中的位置0表示無(wú)左或右孩子靜態(tài)二叉鏈表2 A 13 C 05 B 00 E 00 F 00 D 4 0123456Lchild data rchild6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷：遍歷：按按某種搜索路徑訪問(wèn)某種搜索路徑訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。問(wèn)一次。訪問(wèn)：訪問(wèn)：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理

21、含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。結(jié)點(diǎn)數(shù)據(jù)。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。對(duì)于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼，遍歷是很容易的對(duì)于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼，遍歷是很容易的事事 二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如何訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？何訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？6.3.1 6.3.1 遍歷二叉樹遍歷二叉樹 二叉樹由根根、左子樹、左子樹、右子樹右子樹三部分組

22、成 二叉樹的遍歷可以分解為：訪問(wèn)訪問(wèn)根根，遍歷，遍歷左子樹左子樹和和遍歷遍歷右子樹右子樹令：令：L L：遍歷左子樹 D D：訪問(wèn)根結(jié)點(diǎn) R R：遍歷右子樹有六種遍歷方法： D DL LR R，L LD DR R，L LR RD D， D DR RL L，R RD DL L，R RL LD D 約定先左后右約定先左后右,有三種遍歷方法： D DL LR R、L LD DR R、L LR RD D ，分別稱為 先序( (根根) )遍歷、中序( (根根) )遍歷、后序( (根根) )遍歷 A A F F G G E E D D C C B B 先序先序( (根根) )遍歷（遍歷（D DL LR R）

23、 若二叉樹非空若二叉樹非空 （1）訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹）先序遍歷右子樹； 先序遍歷序列：A,A,B,D,E,G,B,D,E,G,C,FC,F A A F F G G E E D D C C B B例：先序遍歷右圖所示的二叉樹 （1）訪問(wèn)根結(jié)點(diǎn)A （2）先序遍歷先序遍歷左子樹：即按D DL LR R的順序遍歷左子樹 （3）先序遍歷先序遍歷右子樹：即按D DL LR R的順序遍歷右子樹中序( (根根) )遍歷（L LD DR R）若二叉樹非空（1）中序遍歷左子樹中序遍歷左子樹（2 2）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)（3 3）中序遍

24、歷右子樹）中序遍歷右子樹 中序遍歷序列： D,B,G,E,D,B,G,E,A,A,C,FC,F A A F F G G E E D D C C B B例：中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹：即按L LD DR R的順序遍歷左子樹 （2）訪問(wèn)根結(jié)點(diǎn)A A （3）中序遍歷右子樹：即按L LD DR R的順序遍歷右子樹后序( (根根) )遍歷（L LR RD D）若二叉樹非空（1）后序遍歷左子樹后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列： D,G,E,B,D,G,E,B,F,C,F,C,A A例：后序遍歷右圖所示的二叉樹 （1）后

25、序遍歷后序遍歷左子樹：即按L LR RD D的順序遍歷左子樹 （2）后序遍歷后序遍歷右子樹：即按L LR RD D的順序遍歷右子樹 （3）訪問(wèn)根結(jié)點(diǎn)A A A A F F G G E E D D C C B B e e d d c c b b f f a a + + * * / / - - - -先序先序( (根根) )遍歷序列：遍歷序列：- -, ,+,a,+,a,* *,b,-,c,d,b,-,c,d,/,e,f/,e,f中序中序( (根根) )遍歷序列：遍歷序列：a,+,b,a,+,b,* *,c,-,d,c,-,d,- -, ,e,/,fe,/,f后序后序( (根根) )遍歷序列：遍歷

26、序列：a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/e,f,/, ,- -人們喜歡中序形式的算術(shù)表達(dá)式人們喜歡中序形式的算術(shù)表達(dá)式, ,對(duì)于計(jì)算機(jī)對(duì)于計(jì)算機(jī), ,使用后序易于求值使用后序易于求值 例：先中序遍歷序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹這實(shí)際上是先序遍歷的遞歸定義先序遍歷的遞歸定義，我們知道遞歸定義包括兩個(gè)部分： 1 1）基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）；（也叫終止項(xiàng)）； 2 2）遞歸項(xiàng)遞歸項(xiàng) 若二叉樹非空若二叉樹非空 （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；先序遍歷遞歸定義遞歸項(xiàng)

27、遍歷的遞歸算法遍歷的遞歸算法 上面介紹了三種遍歷方法，顯然是用遞歸的方式遞歸的方式給出的三種遍歷方法，以先序?yàn)槔合刃虮闅v（先序遍歷（D DL LR R）的定義的定義：該定義隱含著若二叉樹為空，結(jié)束 上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束 基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）（也叫終止項(xiàng)）若二叉樹非空若二叉樹非空 遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹； 下面給出下面給出先序、中序、后序遍歷遞歸算法先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，為了增加

28、算法的可讀性，這里對(duì)書上算法作了簡(jiǎn)化，沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們，這里對(duì)書上算法作了簡(jiǎn)化，沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)假設(shè)調(diào)用函數(shù)visit( )visit( )訪問(wèn)結(jié)點(diǎn)總是成功的訪問(wèn)結(jié)點(diǎn)總是成功的。1先序遍歷遞歸算法先序遍歷遞歸算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法先序/遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()if(T)/若二叉樹為空，結(jié)束返回,若二叉樹不為空， /訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹，遍歷

29、右子樹 Visit(T-data)； PreOrderTraverse(T-lchild,Visit);PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse最簡(jiǎn)單的Visit函數(shù)是： StatusPrintElement(TElemTypee)/輸出元素e的值printf(e);returnOK; D D A A B B C C E E F F T T2 中序遍歷遞歸算法中序遍歷遞歸算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，visit()是

30、訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法中序/遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit() if(T)/若二叉樹為空，結(jié)束返回/若二叉樹不為空，遍歷左子樹，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹InOrderTraverse(T-lchild,Visit);Visit(T-data)；InOrderTraverse(T-rchild,Visit);/InOrderTraverse 你能寫出你能寫出后序遍歷遞歸算法了吧后序遍歷遞歸算法了吧3 后序遍歷遞歸算法后序遍歷遞歸算法 voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉鏈表存貯二叉樹

31、，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法中序/遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()if(T)/若二叉樹為空，結(jié)束返回/若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問(wèn)根結(jié)點(diǎn)PostOrderTraverse(T-lchild,Visit);PostOrderTraverse(T-rchild,Visit);Visit(T-data)；/PostOrderTraverse 對(duì)二叉樹進(jìn)行遍歷除了按先序、中序和后序，還可用從上到下、對(duì)二叉樹進(jìn)行遍歷除了按先序、中序和后序，還可用從上到下、從左到右按層次進(jìn)行，遍歷的時(shí)間復(fù)雜度為從左到右按層次進(jìn)行，遍歷的時(shí)間復(fù)雜度為O(N) 除了

32、有遞歸算法除了有遞歸算法,也可利用棧實(shí)現(xiàn)非遞歸算法也可利用棧實(shí)現(xiàn)非遞歸算法,如算法如算法6.2,算法算法6.3從從遞歸的角度遞歸的角度看先序、中序和后序遍歷是一樣的（去除看先序、中序和后序遍歷是一樣的（去除visit( ) 函數(shù)函數(shù)) 遍歷是二叉樹的基本操作：二叉樹許多操作可在遍歷過(guò)程遍歷是二叉樹的基本操作：二叉樹許多操作可在遍歷過(guò)程中完成，如二叉樹線索化，就是在對(duì)二叉樹進(jìn)行中序遍歷時(shí)加中完成，如二叉樹線索化，就是在對(duì)二叉樹進(jìn)行中序遍歷時(shí)加上線索的上線索的。本節(jié)再舉幾個(gè)例子二叉樹遍歷應(yīng)用實(shí)例。本節(jié)再舉幾個(gè)例子二叉樹遍歷應(yīng)用實(shí)例。遍歷的應(yīng)用遍歷的應(yīng)用例例1 編寫編寫 求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法

33、求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法輸入：輸入：二叉樹的二叉鏈表二叉樹的二叉鏈表結(jié)果：結(jié)果：二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)基本思想：基本思想：遍歷操作遍歷操作訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。所以可訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。所以可在二叉樹遍歷的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)。在二叉樹遍歷的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)。 D D A A B B C C E E F F T Tvoid leaf(BiTree T) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結(jié)點(diǎn)為全局變量，用于累加二叉樹的葉子結(jié)點(diǎn)/的個(gè)數(shù)。的個(gè)數(shù)。本算法在先

34、序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)本算法在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)/第一第一 次被調(diào)用時(shí)，次被調(diào)用時(shí)，n=0if(T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 /若二叉樹不為空，若二叉樹不為空，在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù) if(T-lchild=null&T-rchild=null) n=n+1; leaf(T-lchild); leaf(T-rchild); /if/leafvoid leaf(BiTree T) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹

35、的葉子結(jié)點(diǎn)為全局變量，用于累加二叉樹的葉子結(jié)點(diǎn),的個(gè)數(shù)。的個(gè)數(shù)。/本算法在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)第一本算法在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)第一 次被調(diào)用時(shí)，次被調(diào)用時(shí)，n=0 if(T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 /若二叉樹不為空，若二叉樹不為空，在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)在先序遍歷二叉樹的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù) if (T-lchild=null&T-rchild=null) n=n+1; leaf(T-lchild); leaf(T-rchild); /if/leaf viod PreOrderTraver

36、se(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法先序是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法先序 /遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，返回若二叉樹為空，返回 / 若二叉樹不為空，訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹若二叉樹不為空，訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrd

37、erTraverse(T-rchild, Visit); /PreOrderTraverse比較先序遍歷算法和計(jì)算葉子結(jié)點(diǎn)算法，有什么相同和不同？結(jié)構(gòu)類似函數(shù)名不同訪問(wèn)結(jié)點(diǎn)時(shí)調(diào)用visit( )訪問(wèn)結(jié)點(diǎn)時(shí)統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)例2為二叉樹建立二叉鏈表輸入：二叉樹的先序序列結(jié)果：二叉樹的二叉鏈表遍歷操作訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。是否可在利用遍歷，建立遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接？基本思想：輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)字符）按先序編歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接 D D A A B B C C E E F

38、F T T 先序序列：A B D F C E（在空子樹處添加*的二叉樹的）先序序列：A B D * F * * * C E * * * A A F F E E D D C C B B* A A F F E E D D C C B BStatus CreateBiTree(BiTree &T) /輸入（輸入（在空子樹處添加在空子樹處添加* *的二叉樹的）先序序列（設(shè)每個(gè)元素是的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)字一個(gè)字/ 符）符）按先序編歷的順序按先序編歷的順序，建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針，建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針/賦給賦給T scanf (&ch);

39、 if (ch= = * ) T=NULL; / 若若ch= = * 則則T=NULL返回返回 else / 若若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立建立（根）結(jié)點(diǎn)根）結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹鏈表，并將左子樹根結(jié)點(diǎn)指針構(gòu)造左子樹鏈表，并將左子樹根結(jié)點(diǎn)指針 /賦賦 給給（根）結(jié)點(diǎn)根）結(jié)點(diǎn) 的左孩子域的左孩子域 CreateBiTree(T-rchild); /構(gòu)造右子樹鏈表，并將右子樹根結(jié)點(diǎn)指針構(gòu)造右子樹鏈表，并將右子樹根

40、結(jié)點(diǎn)指針 /賦給賦給（根）結(jié)點(diǎn)根）結(jié)點(diǎn) 的右孩子域的右孩子域 return OK;/CreateBiTree 算法算法6.4小小 結(jié)結(jié)1 二叉樹：或?yàn)榭諛?，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹；2 二叉樹即可以用順序結(jié)構(gòu)存儲(chǔ)，也可用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；3 遍歷：按某種搜索路徑訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。 二叉樹的遍歷可以分解為：訪二叉樹的遍歷可以分解為：訪問(wèn)根，遍歷問(wèn)根，遍歷左子樹和左子樹和遍歷遍歷右子樹，本課程介紹了三種右子樹，本課程介紹了三種遍歷算法：遍歷算法：先序遍歷、中序遍歷、后序遍歷；先序遍歷、中序遍歷、后序遍歷；6.3.2 線索二叉樹線索二

41、叉樹遍歷遍歷是二叉樹最基本最常用的操作。實(shí)質(zhì)是對(duì)一個(gè)是二叉樹最基本最常用的操作。實(shí)質(zhì)是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行非線性結(jié)構(gòu)進(jìn)行線性化操作線性化操作(得到先序、中序和后序序列）得到先序、中序和后序序列） 1）對(duì)二叉樹所有結(jié)點(diǎn)做某種處理可在遍歷過(guò)程中實(shí)現(xiàn)；）對(duì)二叉樹所有結(jié)點(diǎn)做某種處理可在遍歷過(guò)程中實(shí)現(xiàn)； 2）檢索（查找）二叉樹某個(gè)結(jié)點(diǎn)，可通過(guò)遍歷實(shí)現(xiàn)；）檢索（查找）二叉樹某個(gè)結(jié)點(diǎn)，可通過(guò)遍歷實(shí)現(xiàn)； 與與線性表相比，對(duì)二叉樹的遍歷存在如下問(wèn)題：線性表相比，對(duì)二叉樹的遍歷存在如下問(wèn)題： 1）遍歷算法要復(fù)雜的多，費(fèi)時(shí)的多；）遍歷算法要復(fù)雜的多，費(fèi)時(shí)的多； 2）為檢索或查找二叉樹中某結(jié)點(diǎn)在某種遍歷下的后繼，必須

42、從根）為檢索或查找二叉樹中某結(jié)點(diǎn)在某種遍歷下的后繼，必須從根開始遍歷，直到找到該結(jié)點(diǎn)及后繼；開始遍歷，直到找到該結(jié)點(diǎn)及后繼； 如果如果能將能將二叉樹線性化二叉樹線性化，就可以，就可以減化遍歷算法，減化遍歷算法，提高遍歷速度。提高遍歷速度。如何將二叉樹線性化？如何將二叉樹線性化？ 以中序遍歷為例，以中序遍歷為例，我們看到通過(guò)遍歷可以得到二叉樹結(jié)點(diǎn)的中序序我們看到通過(guò)遍歷可以得到二叉樹結(jié)點(diǎn)的中序序列。列。若能將中序序列中每個(gè)結(jié)點(diǎn)前趨、后繼信息保存起來(lái)若能將中序序列中每個(gè)結(jié)點(diǎn)前趨、后繼信息保存起來(lái)，以后再遍歷，以后再遍歷二叉樹時(shí)就可以根據(jù)所保存的結(jié)點(diǎn)前趨、后繼信息對(duì)二叉樹進(jìn)行遍歷二叉樹時(shí)就可以根據(jù)所

43、保存的結(jié)點(diǎn)前趨、后繼信息對(duì)二叉樹進(jìn)行遍歷。中序遍歷序列：中序遍歷序列：D,B,H,E,A,F,C,GD,B,H,E,A,F,C,G在在中序序列中，中序序列中，D D的的后繼后繼是是B B，H H的的前趨前趨是是B B，后繼后繼是是E E加上結(jié)點(diǎn)前趨后繼信息（線索）的二叉樹稱為線索二叉樹加上結(jié)點(diǎn)前趨后繼信息（線索）的二叉樹稱為線索二叉樹 A A G G H H E E D D C C B B F F線索二叉樹孩子指針前趨指針后繼指針NILNIL線索鏈表線索鏈表 線索二叉樹的可能存貯方法：線索二叉樹的可能存貯方法： 1） 為每個(gè)結(jié)點(diǎn)增加二個(gè)指針域。為每個(gè)結(jié)點(diǎn)增加二個(gè)指針域。 缺點(diǎn)：缺點(diǎn)：要用較多的

44、內(nèi)存空間，降低存儲(chǔ)密度，不可取要用較多的內(nèi)存空間，降低存儲(chǔ)密度，不可取 2）觀察發(fā)現(xiàn)：）觀察發(fā)現(xiàn)：在有在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空鏈域，個(gè)空鏈域，故故可利用這些的空鏈域存放結(jié)點(diǎn)的前趨和后繼信息，以這種結(jié)點(diǎn)的構(gòu)成可利用這些的空鏈域存放結(jié)點(diǎn)的前趨和后繼信息，以這種結(jié)點(diǎn)的構(gòu)成二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表線索鏈表T T D D A A B B C C F F H H E E G G 線索鏈表的類型說(shuō)明線索鏈表的類型說(shuō)明typedefenumlink,threadPointerTag;/link=0:指針,thread=1:

45、線索typedefstructBiThrNodeTElemTypedata;StructBiThrNode*lchild,*rchild;/左右孩子孩子指針域PointerTagLtag,Rtag;/左右標(biāo)志，標(biāo)志域?yàn)闃?biāo)志域?yàn)?時(shí)，表示左右時(shí)，表示左右指針域存儲(chǔ)的是結(jié)點(diǎn)的左或右孩子，標(biāo)志域?yàn)橹羔樣虼鎯?chǔ)的是結(jié)點(diǎn)的左或右孩子，標(biāo)志域?yàn)?時(shí)，表示左右指針域時(shí)，表示左右指針域存儲(chǔ)的是結(jié)點(diǎn)的前趨或后繼存儲(chǔ)的是結(jié)點(diǎn)的前趨或后繼BiThrNode，*BiThrTreeLchild lTag data RTag rchildF F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00

46、 0B B0 00 0H H1 11 1C C0 00 0線索鏈表圖示線索二叉樹 A A G G H H E E D D C C B B F F孩子指針前趨指針后繼指針中序遍歷序列：中序遍歷序列：D,B,H,E,A,F,C,GD,B,H,E,A,F,C,GNILNIL為簡(jiǎn)化線索鏈表的遍歷算法，仿照線性鏈表，為簡(jiǎn)化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一頭結(jié)點(diǎn)為線索鏈表加上一頭結(jié)點(diǎn)約定約定： 頭結(jié)點(diǎn)的頭結(jié)點(diǎn)的lchild域：存放線索鏈表的根結(jié)點(diǎn)指針；域：存放線索鏈表的根結(jié)點(diǎn)指針； 頭結(jié)點(diǎn)的頭結(jié)點(diǎn)的rchild域域: 中序序列最后一個(gè)結(jié)點(diǎn)的指針；中序序列最后一個(gè)結(jié)點(diǎn)的指針； 中序序列第一

47、結(jié)點(diǎn)中序序列第一結(jié)點(diǎn)lchild域指向頭結(jié)點(diǎn)域指向頭結(jié)點(diǎn); 中序序列最后一個(gè)結(jié)點(diǎn)的中序序列最后一個(gè)結(jié)點(diǎn)的rchild域指向頭結(jié)點(diǎn)域指向頭結(jié)點(diǎn);F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00 01 1頭結(jié)點(diǎn)從上圖中序線索二叉樹，可看出從上圖中序線索二叉樹，可看出 中序序列的中序序列的第一結(jié)點(diǎn)第一結(jié)點(diǎn)，是二叉樹的最左下結(jié)點(diǎn)是二叉樹的最左下結(jié)點(diǎn)； 若若p所指葉子結(jié)點(diǎn)所指葉子結(jié)點(diǎn)(對(duì)對(duì)D而言而言)的的右孩子域?yàn)榫€索右孩子域?yàn)榫€索，則，則p的的右鏈直接指示了結(jié)點(diǎn)的右鏈直接指示了結(jié)點(diǎn)的后繼后繼(B結(jié)點(diǎn)結(jié)點(diǎn))

48、 ； 若若p所指結(jié)點(diǎn)的所指結(jié)點(diǎn)的右孩子域?yàn)楹⒆又羔樣液⒆佑驗(yàn)楹⒆又羔?對(duì)對(duì)B而言而言)，則，則p的的后繼結(jié)點(diǎn)為其右子樹的最左后繼結(jié)點(diǎn)為其右子樹的最左下結(jié)點(diǎn)下結(jié)點(diǎn)(其左標(biāo)志為其左標(biāo)志為1,H結(jié)點(diǎn)結(jié)點(diǎn))； 在中序線索樹中找結(jié)點(diǎn)前趨的規(guī)律在中序線索樹中找結(jié)點(diǎn)前趨的規(guī)律: 若其左標(biāo)識(shí)為若其左標(biāo)識(shí)為1(F),則左鏈為線索則左鏈為線索,指示其前趨指示其前趨(A),否則否則(A)遍歷左子樹時(shí)最后訪問(wèn)的一個(gè)結(jié)點(diǎn)為其前趨遍歷左子樹時(shí)最后訪問(wèn)的一個(gè)結(jié)點(diǎn)為其前趨(左子樹中最右下的結(jié)點(diǎn)左子樹中最右下的結(jié)點(diǎn)(E)F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0

49、H H1 11 1C C0 00 00 01 1頭結(jié)點(diǎn)中序遍歷序列：D,B,H,E,A,F,C,GD,B,H,E,A,F,C,G線索二叉樹的遍歷線索二叉樹的遍歷 在二叉樹上加上結(jié)點(diǎn)前趨、后繼線索后，可利用線索對(duì)二叉樹進(jìn)行遍在二叉樹上加上結(jié)點(diǎn)前趨、后繼線索后，可利用線索對(duì)二叉樹進(jìn)行遍歷。歷。下面是線索鏈表的中序遍歷算法。下面是線索鏈表的中序遍歷算法。基本步驟基本步驟： 1） p=T-lchild; p指向線索鏈表的根結(jié)點(diǎn)；指向線索鏈表的根結(jié)點(diǎn)； 2）若線索鏈表非空，循環(huán)：若線索鏈表非空，循環(huán)： （a）循環(huán)，順著循環(huán)，順著p左孩子指針找到最左下結(jié)點(diǎn)；訪問(wèn)之；左孩子指針找到最左下結(jié)點(diǎn)；訪問(wèn)之； （b

50、）若若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，所指結(jié)點(diǎn)的右孩子域?yàn)榫€索， p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)循環(huán)：循環(huán)： p=p-rchild； 并訪問(wèn)并訪問(wèn)p所指結(jié)點(diǎn)；（在此循環(huán)中，順著后繼線索所指結(jié)點(diǎn)；（在此循環(huán)中，順著后繼線索訪問(wèn)二叉樹中的結(jié)點(diǎn)）訪問(wèn)二叉樹中的結(jié)點(diǎn)） （c） 一旦線索一旦線索“中斷中斷”，p所指結(jié)點(diǎn)的右孩子域?yàn)橛液⒆又羔?，所指結(jié)點(diǎn)的右孩子域?yàn)橛液⒆又羔槪琾=p-rchild，使使 p指向右孩子結(jié)點(diǎn)；指向右孩子結(jié)點(diǎn)； 3）返回返回OK；結(jié)束結(jié)束線索鏈表的遍歷算法線索鏈表的遍歷算法Void InOrderTraverse_Thr(BiThrTree T, Status (

51、* Visit) (TE1emType e) / T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchildlchild指向根結(jié)點(diǎn)，指向根結(jié)點(diǎn)， / 中序遍歷中序遍歷二叉線索樹二叉線索樹T T算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitVisit。 P=T-lchild; /p指向根結(jié)點(diǎn)指向根結(jié)點(diǎn) While(p!=T) /空樹或遍歷結(jié)束時(shí)，空樹或遍歷結(jié)束時(shí)，p=Tp=T While(p-Ltag= =Link) p= p-lchild; /找到最左下結(jié)點(diǎn)；訪問(wèn)之找到最左下結(jié)點(diǎn)；訪問(wèn)之 Visit(p-data) while (p-Rtag= =Thread &

52、; p-rchild!=T) / 若若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索所指結(jié)點(diǎn)的右孩子域?yàn)榫€索 /且不是最后一個(gè)結(jié)點(diǎn)且不是最后一個(gè)結(jié)點(diǎn) p=p-rchild; Visit(p-data); /訪問(wèn)后繼結(jié)點(diǎn)訪問(wèn)后繼結(jié)點(diǎn) p=p-rchild; return OK;/InOrderTraverse_Thr為了增加算法的可讀性，這里對(duì)書上算法作了簡(jiǎn)化為了增加算法的可讀性，這里對(duì)書上算法作了簡(jiǎn)化沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)調(diào)用函數(shù)visit( )visit( )訪問(wèn)結(jié)點(diǎn)總是成功的訪問(wèn)結(jié)點(diǎn)總是成功的。算法算法6.56.56.4 6.4 樹和森林樹和森林

53、6.4.1 6.4.1 樹的存貯結(jié)構(gòu)樹的存貯結(jié)構(gòu)在樹中，每個(gè)結(jié)點(diǎn)即可能有孩子也可能有雙親，所以既可以通過(guò)保存在樹中，每個(gè)結(jié)點(diǎn)即可能有孩子也可能有雙親，所以既可以通過(guò)保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系，也可用雙親表示每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系，也可用雙親表示法通過(guò)通過(guò)保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。法通過(guò)通過(guò)保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。1 雙親表示法 雙親表示法：通過(guò)保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。 用一組連續(xù)的內(nèi)存單元存儲(chǔ)數(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含兩個(gè)域：一個(gè)數(shù)據(jù)域，一個(gè)“指針域”，用于指示其

54、雙親結(jié)點(diǎn)在數(shù)組中的位置雙親表示類型定義雙親表示類型定義#define MAX_TREEE_SIZE 100typedef struct PTNode TelemType data; int parent; /雙親位置域雙親位置域PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; Int n; /結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)Ptree;I IA AC CB BD DH HG GF FE E雙親表示圖示 A -1 A -1 B 0 B 0 C 0 C 0 D 0 D 0 E 1 E 1 F 1 F 1 G 2 G 2 H 3 H 3 I 3 I 30 01 12 23

55、 34 45 56 67 78 8. .data parent 9 9T.nodesT.n結(jié)點(diǎn)數(shù)雙親結(jié)點(diǎn)在數(shù)組中的位置-1表示無(wú)雙親2 2、孩子表示法、孩子表示法 孩子表示法：孩子表示法：通過(guò)保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之通過(guò)保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。間的結(jié)構(gòu)關(guān)系。 與雙親表示法相反，孩子表示法適合實(shí)現(xiàn)涉及孩子的操作。還可以與雙親表示法相反，孩子表示法適合實(shí)現(xiàn)涉及孩子的操作。還可以將雙親表示與孩子表示法結(jié)合：帶雙親的孩子鏈表。將雙親表示與孩子表示法結(jié)合：帶雙親的孩子鏈表。 方法方法1 ：多重鏈表多重鏈表（類似二叉鏈表（類似二叉鏈表, ,使每個(gè)結(jié)點(diǎn)有

56、多個(gè)指針域使每個(gè)結(jié)點(diǎn)有多個(gè)指針域, ,如如: :有有四個(gè)子樹四個(gè)子樹, ,結(jié)點(diǎn)可定義為有四個(gè)指針域）由于子樹的個(gè)數(shù)不定故有兩種方結(jié)點(diǎn)可定義為有四個(gè)指針域）由于子樹的個(gè)數(shù)不定故有兩種方式：式：定長(zhǎng)結(jié)點(diǎn)定長(zhǎng)結(jié)點(diǎn)( (具有固定的指針域如四或五具有固定的指針域如四或五, ,常以最大子樹個(gè)數(shù)來(lái)確定常以最大子樹個(gè)數(shù)來(lái)確定) ) 不定長(zhǎng)結(jié)點(diǎn)不定長(zhǎng)結(jié)點(diǎn)( (不固定不固定, ,指針域按子樹個(gè)數(shù)設(shè)定指針域按子樹個(gè)數(shù)設(shè)定) ) 定長(zhǎng)結(jié)點(diǎn)定長(zhǎng)結(jié)點(diǎn) 優(yōu)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)一致，便于實(shí)現(xiàn)樹的操作。缺點(diǎn)是浪費(fèi)一些內(nèi)存。優(yōu)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)一致，便于實(shí)現(xiàn)樹的操作。缺點(diǎn)是浪費(fèi)一些內(nèi)存。 不定長(zhǎng)結(jié)點(diǎn)不定長(zhǎng)結(jié)點(diǎn) 優(yōu)點(diǎn)：節(jié)省內(nèi)存優(yōu)點(diǎn)：節(jié)省內(nèi)存 缺點(diǎn)：

57、不定長(zhǎng)會(huì)使一些操作實(shí)現(xiàn)復(fù)雜一些缺點(diǎn)：不定長(zhǎng)會(huì)使一些操作實(shí)現(xiàn)復(fù)雜一些 方法方法2：孩子鏈表 孩子鏈表：對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)樹的孩子鏈表類型定義樹的孩子鏈表類型定義typedef struct CTNode /孩子結(jié)點(diǎn)孩子結(jié)點(diǎn) int child; struct CTNode * next;* ChildPtr;typedef struct TElemType data; ChildPtr firstchild; /孩子鏈表頭指針孩子鏈表頭指針CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; Int n, r; /結(jié)點(diǎn)數(shù)和根的位置；結(jié)點(diǎn)數(shù)和根的位置；CTree; A B C D E F G H I 0 1 2 3 4 5 6 7 8 I IA AC CB BD DH HG GF FE E結(jié)點(diǎn)數(shù)和根的位置 1 3 2 4 5 8 6 790T.nodesT.nT.rdatafirstchild樹的孩子鏈表圖示結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈表 3 3