09級使用數(shù)據(jù)結(jié)構(gòu)第6章

1、第第 六六 章章 樹和二叉樹樹和二叉樹返回主目錄返回主目錄第第 六六 章章 樹和二叉樹樹和二叉樹 學(xué)習(xí)目標學(xué)習(xí)目標領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別樹的結(jié)構(gòu)差別熟記二叉樹的主要特性，并掌握它們的證明熟記二叉樹的主要特性，并掌握它們的證明方法方法熟練掌握二叉樹的各種遍歷算法，并能靈活熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作運用遍歷算法實現(xiàn)二叉樹的其它操作理解二叉樹的線索化過程以及在中序線索化理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法樹上找給定結(jié)點的前驅(qū)和后繼的方法熟練掌握二叉樹和樹的各

2、種存儲結(jié)構(gòu)及其建熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法立的算法學(xué)會編寫實現(xiàn)樹的各種操作的算法學(xué)會編寫實現(xiàn)樹的各種操作的算法了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。曼編碼的方法。本章說明本章說明第第 六六 章章 樹和二叉樹樹和二叉樹本章說明本章說明 重點和難點重點和難點二叉樹和樹的遍歷及其應(yīng)用是本章的學(xué)習(xí)二叉樹和樹的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點，而編寫實現(xiàn)二叉樹和樹的各種操作的遞歸重點，而編寫實現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點所在。算法也恰是本章的難點所在。 知識點知識點樹的類型定義、二叉樹的類型定義、二叉樹的類型定義、二

3、叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實樹的存儲表示、二叉樹的遍歷以及其它操作的實現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼編碼編碼 學(xué)習(xí)指南學(xué)習(xí)指南本章是整個課程的第二個學(xué)習(xí)重點，也是本章是整個課程的第二個學(xué)習(xí)重點，也是整個課程中的一大難點。在本章的學(xué)習(xí)過程中主整個課程中的一大難點。在本章的學(xué)習(xí)過程中主要應(yīng)該學(xué)會如何根據(jù)二叉樹和樹的結(jié)構(gòu)及其操作要應(yīng)該學(xué)會如何根據(jù)二叉樹和樹的結(jié)構(gòu)及其操作的遞歸定義編寫遞歸算法。的遞歸定義編寫遞歸算法。第第 六六 章

4、章 樹和二叉樹樹和二叉樹6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)關(guān)系定義的層次結(jié)構(gòu)1、樹的定義、樹的定義 定義：樹定義：樹(tree)是是n(n0)個結(jié)點的有限集個結(jié)點的有限集T，其中：，其中：有且僅有一個特定的結(jié)點，稱為樹的根有且僅有一個特定的結(jié)點，稱為樹的根(root)當當n1時，其余結(jié)點可分為時，其余結(jié)點可分為m(m0)個互不相交的個互不相交的有限集有限集T1,T2,Tm，其中每一個集合本身又是，其中每一個集合本身又是一棵樹，稱為根的子樹一棵樹，稱為根的子樹(subtree)特點：特點：樹

5、中至少有一個結(jié)點樹中至少有一個結(jié)點根根樹中各子樹是互不相交的集合樹中各子樹是互不相交的集合第第 六六 章章 樹和二叉樹樹和二叉樹6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語A只有根結(jié)點的樹只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹第第 六六 章章 樹和二叉樹樹和二叉樹ADT Tree 數(shù)據(jù)對象數(shù)據(jù)對象 D： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R： 基本操作基本操作 P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);2、樹的抽象數(shù)據(jù)類型的定義、樹的抽象數(shù)據(jù)類型的定義P1186.1 樹的定義和

6、基本術(shù)語樹的定義和基本術(shù)語第第 六六 章章 樹和二叉樹樹和二叉樹樹形表示法：自然界倒長的樹樹形表示法：自然界倒長的樹(Knuth開初用正開初用正長的樹表示長的樹表示)文氏表示法：用嵌套集合表示文氏表示法：用嵌套集合表示(a)嵌套括號表示法：廣義表表示法嵌套括號表示法：廣義表表示法凹入表示法：類似書目凹入表示法：類似書目3、樹的表示方法、樹的表示方法6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語K LEADJIMHGCBF(a)ACDBEKLFGHMIJ(c)(b)(A(B(E(K,L),F),C(G),D(H(M),I,J)第第 六六 章章 樹和二叉樹樹和二叉樹4、 樹的術(shù)語樹的術(shù)語6.1 樹的

7、定義和基本術(shù)語樹的定義和基本術(shù)語結(jié)點結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及若表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支干指向其子樹的分支結(jié)點的度結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)結(jié)點擁有的子樹數(shù)葉子葉子(leaf)度為度為0的結(jié)點的結(jié)點孩子孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點子樹的根稱為該結(jié)點的孩子雙親雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點孩子結(jié)點的上層結(jié)點叫該結(jié)點的的兄弟兄弟(sibling)同一雙親的孩子同一雙親的孩子樹的度樹的度一棵樹中最大的結(jié)點度數(shù)一棵樹中最大的結(jié)點度數(shù)結(jié)點的層次結(jié)點的層次(level)從根結(jié)點算起，根為第一層，從根結(jié)點算起，根

8、為第一層，它的孩子為第二層它的孩子為第二層第第 六六 章章 樹和二叉樹樹和二叉樹堂兄堂兄其父母為兄弟的結(jié)點互稱堂兄其父母為兄弟的結(jié)點互稱堂兄祖先祖先結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點所有結(jié)點子孫子孫以某結(jié)點為根的子樹中的任一結(jié)點都稱為以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫該結(jié)點的子孫有序樹有序樹結(jié)點的子樹從左到右有順序，否則，稱結(jié)點的子樹從左到右有順序，否則，稱為無序樹為無序樹深度深度(depth)樹中結(jié)點的最大層次數(shù)樹中結(jié)點的最大層次數(shù)森林森林(forest)m(m0)棵互不相交的樹的集合棵互不相交的樹的集合6.1 樹的定義和基本術(shù)語樹

9、的定義和基本術(shù)語第第 六六 章章 樹和二叉樹樹和二叉樹6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語ABCDEFGHIJKLM結(jié)點結(jié)點A的度：的度：3結(jié)點結(jié)點B的度：的度：2結(jié)點結(jié)點M的度：的度：0葉子：葉子：K，L，F(xiàn)，G，M，I，J結(jié)點結(jié)點A的孩子：的孩子：B，C，D結(jié)點結(jié)點B的孩子：的孩子：E，F(xiàn)結(jié)點結(jié)點I的雙親：的雙親：D結(jié)點結(jié)點L的雙親：的雙親：E結(jié)點結(jié)點B，C，D為兄弟為兄弟結(jié)點結(jié)點K，L為兄弟為兄弟樹的度：樹的度：3結(jié)點結(jié)點A的層次：的層次：1結(jié)點結(jié)點M的層次：的層次：4樹的深度：樹的深度：4結(jié)點結(jié)點F，G為堂兄弟為堂兄弟結(jié)點結(jié)點A是結(jié)點是結(jié)點F，G的祖先的祖先第第 六六 章章 樹

10、和二叉樹樹和二叉樹6.2 二二 叉叉 樹樹1、二叉樹定義、二叉樹定義定義：二叉樹是定義：二叉樹是n(n0)個結(jié)點的有限集，它或個結(jié)點的有限集，它或為空樹為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點特點每個結(jié)點至多有二棵子樹每個結(jié)點至多有二棵子樹(即不存在度大于即不存在度大于2的的結(jié)點結(jié)點)二叉樹的子樹有左、右之分，且其次序不能任二叉樹的子樹有左、右之分，且其次序不能任意顛倒意顛倒基本形態(tài)基本形態(tài)A只有根結(jié)點只有根結(jié)點的二叉樹的二叉樹 空二叉樹空二叉樹AB右子樹為空右子樹為空AB左子樹為空

11、左子樹為空ABC左、右子樹左、右子樹均非空均非空第第 六六 章章 樹和二叉樹樹和二叉樹證明：用歸納法證明之證明：用歸納法證明之 i=1時，只有一個根結(jié)點，顯然，時，只有一個根結(jié)點，顯然，2i-1=20=1 是對的是對的 假設(shè)對所有假設(shè)對所有j, (1ji)命題成立，即第命題成立，即第j層層上上 至多有至多有2j-1個結(jié)點，可證明個結(jié)點，可證明j=i命題成立命題成立 那么，第那么，第i-1層至多有層至多有2i-2個結(jié)點個結(jié)點 又二叉樹每個結(jié)點的度至多為又二叉樹每個結(jié)點的度至多為2 第第i層上最大結(jié)點數(shù)是第層上最大結(jié)點數(shù)是第i-1層的層的2倍，即倍，即 22i-2=2i-1 故命題得證故命題得證2

12、、二叉樹的性質(zhì)、二叉樹的性質(zhì)6.2 二二 叉叉 樹樹)1(21 iii個個結(jié)結(jié)點點層層上上至至多多有有在在二二叉叉樹樹的的第第性質(zhì)性質(zhì)1：第第 六六 章章 樹和二叉樹樹和二叉樹性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k-1個結(jié)點個結(jié)點(k1)6.2 二二 叉叉 樹樹證明：由性質(zhì)證明：由性質(zhì)1，可得深度為，可得深度為k 的二叉樹最大結(jié)點數(shù)是的二叉樹最大結(jié)點數(shù)是122)(111kkikiii層的最大結(jié)點數(shù)第性質(zhì)性質(zhì)3：對任何一棵二叉樹：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為，如果其終端結(jié)點數(shù)為n0，度為，度為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，則，則n0=n2+1證明：設(shè)證明：設(shè)n1為二

13、叉樹為二叉樹T中度為中度為1的結(jié)點數(shù)的結(jié)點數(shù) 因為：二叉樹中所有結(jié)點的度均小于或等于因為：二叉樹中所有結(jié)點的度均小于或等于2 所以：其結(jié)點總數(shù)所以：其結(jié)點總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一 個分支進入，設(shè)個分支進入，設(shè)B為分支總數(shù)，則為分支總數(shù)，則n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結(jié)點射出，的結(jié)點射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1第第 六六 章章 樹和二叉樹樹和二叉樹特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)特點：每一層上的結(jié)點數(shù)都是最大結(jié)

14、點數(shù)完全二叉樹完全二叉樹定義：深度為定義：深度為k，有，有n個結(jié)點的二叉樹當且僅當其個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為每一個結(jié)點都與深度為k的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結(jié)點一一對應(yīng)時，稱為的結(jié)點一一對應(yīng)時，稱為特點特點葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點，若其右分支下子孫的最大層次為對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為則其左分支下子孫的最大層次必為l 或或l+16.2 二二 叉叉 樹樹幾種特殊形式的二叉樹幾種特殊形式的二叉樹滿二叉樹滿二叉樹定義：定義：12個個結(jié)結(jié)點點的的二二叉叉樹樹

15、稱稱為為且且有有一一棵棵深深度度為為 kk第第 六六 章章 樹和二叉樹樹和二叉樹6.2 二二 叉叉 樹樹1231145891213671014151231145891267101234567123456思考：滿二叉樹與完全二叉樹的關(guān)系？思考：滿二叉樹與完全二叉樹的關(guān)系？第第 六六 章章 樹和二叉樹樹和二叉樹性質(zhì)性質(zhì)4：具有：具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為log2n+1 證明：設(shè)深度為證明：設(shè)深度為k，則由性質(zhì)，則由性質(zhì)2和完全二叉樹定義和完全二叉樹定義 (k-1層層)2k-1-1n2k-1(k層）或?qū)樱┗?k-1 n2k 于是于是k-1 log2nk 又又k是整數(shù)是

16、整數(shù) k=log2n+1性質(zhì)性質(zhì)5：對于一棵完全二叉樹，從上到下從左至右對結(jié)：對于一棵完全二叉樹，從上到下從左至右對結(jié)點進行編號點進行編號,根結(jié)點為根結(jié)點為1,則對任一結(jié)點則對任一結(jié)點i(1=in，則結(jié)點，則結(jié)點i無左子女，否則，其左子女為無左子女，否則，其左子女為2i如果如果2i+1n，則結(jié)點，則結(jié)點i無右子女，否則，其右子女為無右子女，否則，其右子女為2i+16.2 二二 叉叉 樹樹第第 六六 章章 樹和二叉樹樹和二叉樹3、二叉樹的存儲結(jié)構(gòu)、二叉樹的存儲結(jié)構(gòu)順序的存儲結(jié)構(gòu)順序的存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素叉樹中

17、的數(shù)據(jù)元素特點：特點：結(jié)點間關(guān)系蘊含在其存儲位置中結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 116.2 二二 叉叉 樹樹浪費空間浪費空間第第 六六 章章 樹和二叉樹樹和二叉樹二叉樹的順序存儲表示二叉樹的順序存儲表示 #define MAX_TREE_SIZE 100 Typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號單元存儲根結(jié)點號單元存儲根結(jié)點 SqBiTree bt;缺點：按完全二叉樹形式存儲，

18、浪費空間。缺點：按完全二叉樹形式存儲，浪費空間。 例如，在最壞情況下，例如，在最壞情況下，n個結(jié)點的單枝樹，要占用個結(jié)點的單枝樹，要占用2n-1個元素的存儲空間。個元素的存儲空間。6.2 二二 叉叉 樹樹順序存儲結(jié)構(gòu)適用于滿二叉樹和完全二叉樹順序存儲結(jié)構(gòu)適用于滿二叉樹和完全二叉樹的存儲。的存儲。第第 六六 章章 樹和二叉樹樹和二叉樹鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)二叉鏈表二叉鏈表表示表示typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;lchild data rchild A

19、BCDEFG在在n個結(jié)點的二叉鏈表中，有個結(jié)點的二叉鏈表中，有n+1個空指針域個空指針域 AB C D E F G6.2 二二 叉叉 樹樹第第 六六 章章 樹和二叉樹樹和二叉樹三叉鏈表三叉鏈表表示表示typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild,*parent;BiTNode ,*Bitree;lchild data parent rchildABCDEFG A B C D E F G6.2 二二 叉叉 樹樹第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 問題

20、的提出問題的提出 先左后右的遍歷算法先左后右的遍歷算法 算法的遞歸描述算法的遞歸描述 遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例1、遍歷二叉樹、遍歷二叉樹 算法的非遞歸描述算法的非遞歸描述第第 六六 章章 樹和二叉樹樹和二叉樹 順著某一條搜索路徑巡訪二叉樹順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。次，而且僅被訪問一次。 問題的提出問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)的含義可以很廣，如：輸出結(jié)點的信息等。點的信息等。6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二

21、叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 “遍歷遍歷”是任何類型均有的操作，是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路對線性結(jié)構(gòu)而言，只有一條搜索路徑徑(因為每個結(jié)點均只有一個后繼因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索則存在如何遍歷即按什么樣的搜索路徑進行遍歷的問題。路徑進行遍歷的問題。第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 對對“二叉樹二叉樹”而言，可以有三條搜索路而言，可以有三條搜索路徑：

22、徑：（1）先上后下的按層次遍歷；）先上后下的按層次遍歷；（2）先左（子樹）后右（子樹）的遍）先左（子樹）后右（子樹）的遍歷；歷；（3）先右（子樹）后左（子樹）的遍）先右（子樹）后左（子樹）的遍歷。歷。第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 先左后右的遍歷算法先左后右的遍歷算法先（根）序的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法后（根）序的遍歷算法根根左左子樹子樹右右子樹子樹根根根根根根根根根根訪問根結(jié)點、遍歷左子樹、遍歷右子樹訪問根結(jié)點、遍歷左子樹、遍歷右子樹第第 六六 章章 樹和二叉樹樹和二叉

23、樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；）訪問根結(jié)點；（2）先序遍歷左子樹；）先序遍歷左子樹；（3）先序遍歷右子樹。）先序遍歷右子樹。先（根）序的遍歷算法：先（根）序的遍歷算法：第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；）中序遍歷左子樹；（2）訪問根結(jié)點；）訪問根結(jié)點；（3）中序遍歷右子樹。）中序遍歷右子樹。中（根）序的遍歷算法：中（根）序的遍歷算法：第第 六六

24、章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；）后序遍歷左子樹；（2）后序遍歷右子樹；）后序遍歷右子樹；（3）訪問根結(jié)點。）訪問根結(jié)點。后（根）序的遍歷算法：后（根）序的遍歷算法：第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A第第 六六 章章

25、樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 算法的遞歸描述（算法的遞歸描述（6.1）第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹void preorder(BiTree *T) if (T) printf(%dt,T-data); preorder(T-lchild); preorder(T-rchild); 主程序主程序Pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D

26、);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 算法的非遞歸描述算法的非遞歸描述 二叉樹表示表達式二叉樹表示表達式 基本思想基本思想 若表達式為數(shù)或簡單變量，則相應(yīng)若表達式為數(shù)或簡單變量，則相應(yīng)二叉樹只有根結(jié)點，其數(shù)據(jù)域存放表達二叉樹只有根結(jié)點，其數(shù)據(jù)域存放表達式信息；否則，表達式均可寫成式信息；否

27、則，表達式均可寫成（運算符）（運算符）形式，形式，其中，其中，“運算符運算符”可用二叉樹的根結(jié)點表可用二叉樹的根結(jié)點表示，示，“第一操作數(shù)第一操作數(shù)”用二叉樹的左子樹表用二叉樹的左子樹表示，示，“第二操作數(shù)第二操作數(shù)”用二叉樹的右子樹表用二叉樹的右子樹表示。操作數(shù)本身可以是表達式。示。操作數(shù)本身可以是表達式。第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹表達式表達式 = ( = (操作數(shù)操作數(shù)1)(1)(運算符運算符)()(操作數(shù)操作數(shù)2)2)運算符運算符操作數(shù)1操作數(shù)2第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和

28、線索二叉樹例如：例如： a+b a+b* *(c-d)-e/f (c-d)-e/f 的二叉樹表示。的二叉樹表示。abcef- -+* */d- -先序（前綴表達式）先序（前綴表達式）中序（中綴表達式）中序（中綴表達式）后序（后綴表達式）后序（后綴表達式）- + a- + a * * b -b -cd/efcd/efa+b*c-d-e/fabcd-*+ef/-第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹abc- -* *- -* *c cab b- -* *abc先序遍歷：先序遍歷：- * a b c第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷

29、二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹abc- -* *- -* *c cab b中序遍歷：中序遍歷： a * b - ca* *bc- -第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹abc- -* *- -* *c cab b后序遍歷：后序遍歷： a b * c -ab* *c c- -第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法6.2ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULL

30、ABCDEFGiP-AP-B訪問：C(4)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(1

31、2)ABCDEFGiP-AP-D訪問：C B E Gp(10)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 建立二叉樹的存儲結(jié)構(gòu)建立二叉樹的存儲結(jié)構(gòu) 遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 求二叉樹的深度求二叉樹的深

32、度 二叉樹表示表達式二叉樹表示表達式第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹，遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個由此，需在遍歷算法中增添一個“計數(shù)計數(shù)”的參數(shù)，并將算法中的參數(shù)，并將算法中“訪問結(jié)點訪問結(jié)點”的操的操作改為作改為: :若是葉子，則計數(shù)器增若是葉子，則計數(shù)器增1 1。算法實現(xiàn)算法實現(xiàn)第第 六六 章章 樹和二叉樹樹和二叉

33、樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹否則，整個二叉樹中的葉子結(jié)點個數(shù)等否則，整個二叉樹中的葉子結(jié)點個數(shù)等于其左子樹中的葉子結(jié)點個數(shù)和其右子于其左子樹中的葉子結(jié)點個數(shù)和其右子樹中的葉子結(jié)點個數(shù)之和。樹中的葉子結(jié)點個數(shù)之和。 另一種算法思想分析方法另一種算法思想分析方法: :若二叉樹為空，則葉子結(jié)點的個數(shù)為零若二叉樹為空，則葉子結(jié)點的個數(shù)為零; ;若二叉樹中只有一個若二叉樹中只有一個( (根根) )結(jié)點，則葉子結(jié)點，則葉子結(jié)點的個數(shù)為結(jié)點的個數(shù)為1;1;(后序遍歷后序遍歷)算法實現(xiàn)算法實現(xiàn)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹

34、求二叉樹的深度求二叉樹的深度算法基本思想算法基本思想: :若二叉樹為空樹，則深度為若二叉樹為空樹，則深度為0;0;否則，二叉樹的深度應(yīng)為其左、右子樹深否則，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加度的最大值加1 1。由此，需先分別求得左、右子樹的深度。由此，需先分別求得左、右子樹的深度。 首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系(后序遍歷后序遍歷)第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹int Depth (BiTree T ) / 返回二叉樹的深度返回二叉樹的深度 if ( !T ) depthval = 0; else dept

35、hLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹也可以從另一角度去分析也可以從另一角度去分析: : 從二叉樹深度的定義還可知，二叉樹的從二叉樹深度的定義還可知，二叉樹的深度即為其葉子結(jié)點所在層次的最大值。深度即為其葉子結(jié)點所在層次的最大值。由此，可通過遍歷求得二叉樹中所有結(jié)點由此，

36、可通過遍歷求得二叉樹中所有結(jié)點的的“層次層次”，從中取其最大值。，從中取其最大值。算法中需引入一個計結(jié)點層次的參數(shù)。算法中需引入一個計結(jié)點層次的參數(shù)。 首先分析二叉樹的深度和結(jié)點的“層次”間的關(guān)系。第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹void Depth(BiTree T , int level, int &dval) if ( T ) if (leveldval) dval = level; Depth( T-lchild, level+1, dval ); Depth( T-rchild, level+1, dval ); / 調(diào)用之前

37、調(diào)用之前 level 的初值為的初值為 1。 / dval 的初值為的初值為 0.第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 建立二叉樹的存儲結(jié)構(gòu)建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法結(jié)構(gòu)的建立算法第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 以字符串的形式以字符串的形式 “根根 左子樹左子樹 右子樹右子樹”定義一棵二叉樹（算法定義一棵二叉樹（算法6.4）例如例如: :A(B( ,C( , ),D( , )以字符串“A ”表示ABCD以空白字符

38、“ ”表示空樹空樹只含一個根結(jié)點只含一個根結(jié)點的二叉樹的二叉樹A以下列字符串表示第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹void CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T = NULL; else T =(BiTNode*) malloc(sizeof(BiTNode); T-data = ch; / 生成根結(jié)點生成根結(jié)點 CreateBiTree(T-lchild); / 構(gòu)造左子樹構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹構(gòu)造右子樹 / CreateBiT

39、ree第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹A B C D A BCD上頁算法執(zhí)行過程舉例如下上頁算法執(zhí)行過程舉例如下: :ATBCD scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode*) malloc(sizeof( BiTNode); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); 第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 二叉樹的遍歷有許多重要性質(zhì)，現(xiàn)以例子二叉樹的

40、遍歷有許多重要性質(zhì)，現(xiàn)以例子加以說明。加以說明。例如：僅知二叉樹的先序序列例如：僅知二叉樹的先序序列“abcdefg” 不能唯不能唯一確定一棵二叉樹，如果同時已知二叉樹的中一確定一棵二叉樹，如果同時已知二叉樹的中序序列序序列“cbdaegf”，則會如何？，則會如何？二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根第第 六六 章章 樹和二叉樹樹和二叉樹a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹

41、樹和二叉樹此例推論可知，二叉樹遍歷的重要性質(zhì)：此例推論可知，二叉樹遍歷的重要性質(zhì)： 若已知二叉樹的先序序列和中序序列，若已知二叉樹的先序序列和中序序列，可唯一確定一棵二叉樹；可唯一確定一棵二叉樹； 若已知二叉樹的后序序列和中序序列，若已知二叉樹的后序序列和中序序列，也可唯一確定一棵二叉樹。也可唯一確定一棵二叉樹。6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹2 2、線索二叉樹、線索二叉樹 線索二叉樹定義線索二叉樹定義 線索二叉樹的遍歷線索二叉樹的遍歷 中序遍歷二叉線索樹的算法中序遍歷二叉線索樹的算法

42、第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 二叉樹的遍歷本質(zhì)上是將一個復(fù)雜的非線性二叉樹的遍歷本質(zhì)上是將一個復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個結(jié)點都有了唯一前結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個結(jié)點都有了唯一前驅(qū)和后繼（第一個結(jié)點無前驅(qū)，最后一個結(jié)點無驅(qū)和后繼（第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼）。對于二叉樹的一個結(jié)點，查找其左、右后繼）。對于二叉樹的一個結(jié)點，查找其左、右孩子是方便的，其前驅(qū)后繼只有在遍歷中得到。孩子是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法：為了容易找到前驅(qū)和后繼，有兩種方法： 在結(jié)點結(jié)構(gòu)中增加向前和

43、向后的指針在結(jié)點結(jié)構(gòu)中增加向前和向后的指針fwdfwd和和bkdbkd，這種方法增加了存儲開銷這種方法增加了存儲開銷 利用二叉樹的空鏈指針。利用二叉樹的空鏈指針。 線索二叉樹定義線索二叉樹定義第第 六六 章章 樹和二叉樹樹和二叉樹v n n個結(jié)點的二叉鏈表有個結(jié)點的二叉鏈表有n+1n+1個空鏈域個空鏈域v證明：證明：v 因除了根結(jié)點外，每個結(jié)點都有一因除了根結(jié)點外，每個結(jié)點都有一指針射入。指針射入。v n n個結(jié)點便有個結(jié)點便有n-1n-1個指針，即有個指針，即有n-1n-1個非空鏈域。個非空鏈域。v 因有因有2n2n個鏈域個鏈域v 空鏈域個數(shù)為：空鏈域個數(shù)為：2n-(n-1)=n+12n-(

44、n-1)=n+16.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹 為了節(jié)省存貯空間，我們可以利用這為了節(jié)省存貯空間，我們可以利用這些空鏈域來存放結(jié)點的前趨和后繼的信息。些空鏈域來存放結(jié)點的前趨和后繼的信息。為避免混淆，需在結(jié)點中增加兩個標志域：為避免混淆，需在結(jié)點中增加兩個標志域： lchildltagdatartagrchild( (特征位特征位) ) 0 lchild 0 lchild域指示結(jié)點的左孩子域指示結(jié)點的左孩子ltag= 1 lchildltag= 1 lchild域指示結(jié)點的前趨域指示結(jié)點的前趨 rtag= 0 rchildrtag=

45、0 rchild域指示結(jié)點的右孩子域指示結(jié)點的右孩子 1 rchild 1 rchild域指示結(jié)點的后繼域指示結(jié)點的后繼6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹 線索鏈表：以上述結(jié)點結(jié)構(gòu)構(gòu)成的二叉線索鏈表：以上述結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表鏈表 其中指向結(jié)點前趨和后繼的指針，其中指向結(jié)點前趨和后繼的指針，叫做線索叫做線索 線索二叉樹：加上線索的二叉樹線索二叉樹：加上線索的二叉樹 對二叉樹以某種次序遍歷使其變?yōu)閷Χ鏄湟阅撤N次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。線索二叉樹的過程叫做線索化。例如：中序線索二叉樹例如：中序線索二叉樹作業(yè)：畫先序，后序

46、線索樹！作業(yè)：畫先序，后序線索樹！6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹abcef- -+* */d- -NILNIL中序線索二叉樹中序線索二叉樹第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹0 01 10 0 - - 0 00 0 + + 0 00 0 / / 0 01 1 a a 1 10 0 * * 0 01 1 e e 1 11 1 b b 1 10 0 - - 0 01 1 c c 1 11 1 d d 1 11 1 f f 1 1thr

47、tbt中序線索鏈表中序線索鏈表頭結(jié)點：頭結(jié)點：lt=0, lc指向根結(jié)點指向根結(jié)點rt=1, rc指向遍歷序列中最后一個結(jié)點指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的遍歷序列中第一個結(jié)點的lc域和最后域和最后一個結(jié)點的一個結(jié)點的rc域都指向頭結(jié)點域都指向頭結(jié)點第第 六六 章章 樹和二叉樹樹和二叉樹 只要先找到序列中的第一個結(jié)點，依次找只要先找到序列中的第一個結(jié)點，依次找結(jié)點的后繼直到其后繼為空為止。結(jié)點的后繼直到其后繼為空為止。6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 線索二叉樹的遍歷線索二叉樹的遍歷 在中序線索樹中找結(jié)點的后繼：在中序線索樹中找結(jié)點的后繼： (1) (1)若

48、結(jié)點的若結(jié)點的rtagrtag為為1 1（葉子），則其后繼為（葉子），則其后繼為線索線索rchildrchild所指結(jié)點所指結(jié)點（2 2）（否則）若結(jié)點的）（否則）若結(jié)點的rtagrtag為為0 0（非葉子），（非葉子），則其后繼為則其后繼為“從其右孩子沿著左鏈找到從其右孩子沿著左鏈找到ltagltag為為1 1的那個結(jié)點的那個結(jié)點” (” (即右子樹最左下的結(jié)點）即右子樹最左下的結(jié)點）第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 在中序線索樹中找結(jié)點的前驅(qū)：在中序線索樹中找結(jié)點的前驅(qū)： (1) (1)若結(jié)點的若結(jié)點的ltagltag為為1 1（葉

49、子），則其前驅(qū)為（葉子），則其前驅(qū)為線索線索lchildlchild所指結(jié)點所指結(jié)點（2 2）（否則）若結(jié)點的）（否則）若結(jié)點的ltagltag為為0 0（非葉子），（非葉子），則其前驅(qū)為則其前驅(qū)為“從其左孩子沿著右鏈找到從其左孩子沿著右鏈找到rtagrtag為為1 1的那個結(jié)點的那個結(jié)點”(”(即左子樹最右下的結(jié)點）即左子樹最右下的結(jié)點） 在后序線索二叉樹中查找結(jié)點的前驅(qū)和后繼在后序線索二叉樹中查找結(jié)點的前驅(qū)和后繼 要知道其雙親的信息，要使用棧，所以說要知道其雙親的信息，要使用棧，所以說后序線索二叉樹是不完善的。后序線索二叉樹是不完善的。第第 六六 章章 樹和二叉樹樹和二叉樹6.3 遍歷二叉

50、樹和線索二叉樹遍歷二叉樹和線索二叉樹 二叉樹的二叉線索存儲表示二叉樹的二叉線索存儲表示Typedef enum Link,Thread pointerTag;Typedef enum Link,Thread pointerTag; /Link=0: /Link=0:指針，指針，Thread=1Thread=1：線索：線索Typedef struct BiThrNode Typedef struct BiThrNode TElemType data; TElemType data; struct BiThrNode struct BiThrNode * *lchild, lchild, * *r

51、child;rchild; PointerTag Ltag, PointerTag Ltag, Rtag;Rtag;BiThrNode, BiThrNode, * *BiThrTree;BiThrTree;第第 六六 章章 樹和二叉樹樹和二叉樹二叉樹的線索化：是在遍歷的過程中，將二叉樹的線索化：是在遍歷的過程中，將二叉鏈表中的空指針改為線索二叉鏈表中的空指針改為線索中序遍歷的線索化算法中序遍歷的線索化算法 在二叉樹的線索鏈表上加一個頭結(jié)點，在二叉樹的線索鏈表上加一個頭結(jié)點，令其令其lchildlchild指向二叉樹的根結(jié)點，指向二叉樹的根結(jié)點，rchildrchild指向中序遍歷時訪問的最后一

52、個結(jié)點指向中序遍歷時訪問的最后一個結(jié)點 令二叉樹中序序列中的第一個結(jié)點的令二叉樹中序序列中的第一個結(jié)點的lchildlchild和最后一個結(jié)點的和最后一個結(jié)點的rchildrchild均指向頭均指向頭結(jié)點（象雙向鏈表，可雙向遍歷）結(jié)點（象雙向鏈表，可雙向遍歷） 設(shè)指針設(shè)指針p p指向當前訪問結(jié)點，指向當前訪問結(jié)點，prepre指向指向其前驅(qū)結(jié)點其前驅(qū)結(jié)點 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 中序遍歷二叉線索樹的算法中序遍歷二叉線索樹的算法第第 六六 章章 樹和二叉樹樹和二叉樹 中序遍歷二叉線索樹中序遍歷二叉線索樹T T的非遞歸算法的非遞歸算法思想：找左子樹的最左葉子結(jié)點，訪問

53、思想：找左子樹的最左葉子結(jié)點，訪問 訪問后繼結(jié)點訪問后繼結(jié)點 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 學(xué)習(xí)線索化時，有三點必須注意：學(xué)習(xí)線索化時，有三點必須注意： 何種序的線索化，是先序、中序還是后序何種序的線索化，是先序、中序還是后序 要前驅(qū)線索化、后繼線索化還是全線索化要前驅(qū)線索化、后繼線索化還是全線索化 （前（前驅(qū)后繼都要）驅(qū)后繼都要） 只有空指針處才能加線索只有空指針處才能加線索; ;第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林1 1、樹的三種存儲結(jié)構(gòu)、樹的三種存儲結(jié)構(gòu) 雙親表示法雙親表示法 孩子鏈表表示法孩子鏈表表示法 樹的二叉鏈表樹的二叉鏈表( (孩

54、子孩子- -兄弟）兄弟） 存儲表示法存儲表示法第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林ABCDEFGr=0n=60 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent 雙親表示法雙親表示法雙親雙親位置位置缺點：只反映了雙親位置缺點：只反映了雙親位置第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林 typedef struct PTNode ElemType data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C語

55、言的類型描述語言的類型描述:第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點的位置和結(jié)點個數(shù)根結(jié)點的位置和結(jié)點個數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林r=0n=6 data firstchildABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 464 5 1 2 3 孩子鏈表表示法孩子鏈表表示法-1 0 0 0 2 2 4parent第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹

56、和森林樹和森林typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點結(jié)構(gòu)孩子結(jié)點結(jié)構(gòu): child nextchildC語言的類型描述語言的類型描述:第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林 typedef struct ElemType data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點結(jié)構(gòu)雙親結(jié)點結(jié)構(gòu) data firstchild第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林typedef struct CTBox nodes

57、MAX_TREE_SIZE; int n, r; / 結(jié)點數(shù)和根結(jié)點的位置結(jié)點數(shù)和根結(jié)點的位置 CTree;樹結(jié)構(gòu)樹結(jié)構(gòu):第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林ABCDEFGroot AB C E D F G AB C E D F G 樹的二叉鏈表樹的二叉鏈表 ( (孩子孩子- -兄弟）存儲表示法兄弟）存儲表示法root第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C語

58、言的類型描述語言的類型描述:結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): firstchild data nextsibling第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林2 2、森林與二叉樹的轉(zhuǎn)換、森林與二叉樹的轉(zhuǎn)換 森林和二叉樹的對應(yīng)關(guān)系森林和二叉樹的對應(yīng)關(guān)系 森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹 二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林 森林和二叉樹的對應(yīng)關(guān)系森林和二叉樹的對應(yīng)關(guān)系設(shè)森林設(shè)森林 F = ( T1, T2, , Tn ); T1 = ( root，t11, t12, , t1m );二叉樹二叉樹 B =( LBT, Node(roo

59、t), RBT );第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林T1T11,T12,T1mT2,TnLBTRBTroot第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林BCADEBACDE二叉鏈表二叉鏈表作為中間作為中間媒介媒介第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林BCADBACDFEGHIJACDBGHIJEFFEHIJG樹與二樹與二叉樹對叉樹對應(yīng)應(yīng)樹根相樹根相連連森林與森林與二叉樹二叉樹對應(yīng)對應(yīng)第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若 F = ，即m

60、=0，則 B = ; 由 ROOT( T1 ) 對應(yīng)得到Node(root);否則，即m0由 (T2, T3, Tn ) 對應(yīng)得到 RBT。RBT是由是由 (T2, T3, Tn ) 轉(zhuǎn)換的二叉樹轉(zhuǎn)換的二叉樹若 F = T1 ,T2, T3, Tn ,則按如下規(guī)則轉(zhuǎn)換二叉樹B=(root, LBT, RBT) ：第第 六六 章章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:由LBT 對應(yīng)得到 ( t11, t12, ，t1m);若 B = , 則 F = ;否則，由 Node(root) 對應(yīng)得到 ROOT( T1 );由RBT 對