數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏版第06章ppt課件

1、1數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造第六章第六章 樹和二叉樹樹和二叉樹6/23/20212ABCDEFGHIJKLM樹樹36.1 6.1 樹的類型定義樹的類型定義數(shù)據(jù)對象數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。是具有一樣特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 假設(shè)假設(shè)D為空集，那么稱為空樹；為空集，那么稱為空樹； 否那么否那么:1在在D中存在獨(dú)一的稱為根的數(shù)據(jù)元素中存在獨(dú)一的稱為根的數(shù)據(jù)元素root,2當(dāng)當(dāng)n1時(shí)，其他結(jié)點(diǎn)可分為時(shí)，其他結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的個(gè)互不相交的有限集有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵其中每一棵子集本身又是一棵符合本定義的樹，稱為根符合本定

2、義的樹，稱為根root的子樹。的子樹。根本操作：根本操作：查找：查找： Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); TreeEmpty(T); T r e e D e p t h ( T ) ; TraverseTree(T, Visit( );46.1 6.1 樹的類型定義樹的類型定義插入：插入： InitTree(&T); CreateTree(&T, definition); Assign(T, cur_e, value); InsertChild(&T, &p, i,

3、c);刪除：刪除： ClearTree(&T); DestroyTree(&T); DeleteChild(&T, &p, i); DestroyTree(&T);56.1 6.1 樹的類型定義樹的類型定義和線性構(gòu)造的比較和線性構(gòu)造的比較 線性構(gòu)造線性構(gòu)造 樹構(gòu)造樹構(gòu)造第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素(無前驅(qū)無前驅(qū))； 根結(jié)點(diǎn)根結(jié)點(diǎn)(無前驅(qū)無前驅(qū))；最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素(無后繼無后繼)； 多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn)(無后繼無后繼)；其它數(shù)據(jù)元素其它數(shù)據(jù)元素 樹中其它結(jié)點(diǎn)樹中其它結(jié)點(diǎn)(一個(gè)前驅(qū)、一個(gè)后繼一個(gè)前驅(qū)、一個(gè)后繼) 。 (一個(gè)前驅(qū)、多個(gè)后繼一

4、個(gè)前驅(qū)、多個(gè)后繼)。6ABCDEFGHIJKLM樹形表示樹形表示A (B (E (K, L), F), C(G ), D( H( M), I, J)嵌套括號表示法嵌套括號表示法樹的表示方法：樹的表示方法： I JFKLGMCCDBEA文氏圖文氏圖凹入表凹入表ABFEKLCDHIGMJ7根本術(shù)語根本術(shù)語結(jié)點(diǎn)結(jié)點(diǎn): 數(shù)據(jù)元素?cái)?shù)據(jù)元素 + 假設(shè)干指向子樹的分支。假設(shè)干指向子樹的分支。結(jié)點(diǎn)的度結(jié)點(diǎn)的度: 分支的個(gè)數(shù)。分支的個(gè)數(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)； 途徑和

5、途徑長度。途徑和途徑長度。孩子結(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)x到子結(jié)點(diǎn)到子結(jié)點(diǎn)y的有序?qū)Φ挠行驅(qū)?x，y)。結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: 假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1，第，第i 層的結(jié)點(diǎn)的層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為子樹根結(jié)點(diǎn)的層次為i+1。規(guī)定根的層數(shù)為。規(guī)定根的層數(shù)為0。樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次。樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次。 森林：是森林：是mm0棵互不相交的樹的集合任何一棵棵互不相交的樹的集合任何一棵非空樹是一個(gè)二元組非空樹是一個(gè)二元組Tree = root

6、，F(xiàn)其中：其中：root被稱為根結(jié)點(diǎn)，被稱為根結(jié)點(diǎn)，F(xiàn)被稱為子樹森林。被稱為子樹森林。86.2 6.2 二叉樹的類型定義二叉樹的類型定義二叉樹的定義二叉樹的定義定義：二叉樹是由定義：二叉樹是由n(n=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。不相交的左右子樹組成，并且左右子樹都是二叉樹。與樹的關(guān)系：這也是一個(gè)遞歸定義。與樹的關(guān)系：這也是一個(gè)遞歸定義。區(qū)別：區(qū)別： 二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只需一棵子樹也要進(jìn)展區(qū)分

7、，闡明它是左子樹，即使只需一棵子樹也要進(jìn)展區(qū)分，闡明它是左子樹，還是右子樹。子樹，還是右子樹。9(a)空二叉樹空二叉樹A (b)根和空的根和空的左右子樹左右子樹AB (c)根和左子樹根和左子樹二叉樹的二叉樹的5 5種根本形狀種根本形狀A(yù)(d)根和右子樹根和右子樹BA (e)根和左右子樹根和左右子樹BC10二叉樹的主要根本操作：二叉樹的主要根本操作：查找：查找： Root(T); Value(T, e);Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmp

8、ty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();插入：插入： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);刪除：刪除： ClearBiTree(&T); DestroyBiTree(&T

9、); DeleteChild(T, p, LR); 11性質(zhì)性質(zhì)1： 在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i=1)。 證明：采用歸納法證明此性質(zhì)。證明：采用歸納法證明此性質(zhì)。當(dāng)當(dāng)i=1時(shí)，只需一個(gè)根結(jié)點(diǎn)，時(shí)，只需一個(gè)根結(jié)點(diǎn)，2i-1=20 =1,命題成命題成立。立。如今假定第如今假定第i1層上命題成立，那么第層上命題成立，那么第i1層上層上至多有至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度最大為個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度最大為2，故在第故在第i層上最大結(jié)點(diǎn)數(shù)為第層上最大結(jié)點(diǎn)數(shù)為第i1層上最大結(jié)點(diǎn)數(shù)的二層上最大結(jié)點(diǎn)數(shù)的二倍，倍， 即即22i-22i-1。命題得

10、到證明。命題得到證明。二叉樹的重要特性：二叉樹的重要特性：12性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)k=1).證明：深度為證明：深度為k的二叉樹的最大的結(jié)點(diǎn)時(shí)為二叉的二叉樹的最大的結(jié)點(diǎn)時(shí)為二叉樹中每層上的最大結(jié)點(diǎn)數(shù)之和，由性質(zhì)樹中每層上的最大結(jié)點(diǎn)數(shù)之和，由性質(zhì)1得到每層上的得到每層上的最大結(jié)點(diǎn)數(shù)最大結(jié)點(diǎn)數(shù)2i-1第第i層上的最大結(jié)點(diǎn)數(shù)層上的最大結(jié)點(diǎn)數(shù)二叉樹的重要特性：二叉樹的重要特性：12k1i1i2k13二叉樹的重要特性：二叉樹的重要特性：性質(zhì)性質(zhì)3： 對任何一棵二叉樹，假設(shè)其終端結(jié)點(diǎn)數(shù)為對任何一棵二叉樹，假設(shè)其終端結(jié)點(diǎn)數(shù)為n0，度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)

11、數(shù)為n2，那么，那么n0n21。證明：設(shè)二叉樹中度為證明：設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)，二叉樹中總結(jié)點(diǎn)數(shù)為點(diǎn)數(shù)為N，由于二叉樹中一切結(jié)點(diǎn)均小于或等于，由于二叉樹中一切結(jié)點(diǎn)均小于或等于2，所以，所以有：有：Nn0n1n2 1 再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)都再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有一個(gè)進(jìn)入分支，設(shè)有一個(gè)進(jìn)入分支，設(shè)B為二叉樹中的分支總數(shù)，為二叉樹中的分支總數(shù)， 那么有：那么有：NB1。由于這些分支都是由度為。由于這些分支都是由度為1和和2的結(jié)點(diǎn)射出的，的結(jié)點(diǎn)射出的，所以有：所以有：Bn1+2*n2 NB1n12n21 2)由式由式1和和

12、2得到：得到： n0+n1+n2=n1+2*n2+1 n0n2114滿二叉樹滿二叉樹2453671123456(a)完全二叉樹完全二叉樹123457(b)非完全二叉樹非完全二叉樹12367( c)非完全二叉樹非完全二叉樹15兩種特殊形狀的二叉樹：兩種特殊形狀的二叉樹： 一棵深度為一棵深度為k且由且由2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。假設(shè)深度為假設(shè)深度為k、由、由n個(gè)結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)可以與個(gè)結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)可以與深度為深度為k的順序編號的滿二叉樹從的順序編號的滿二叉樹從1到到n標(biāo)號的結(jié)點(diǎn)相對標(biāo)號的結(jié)點(diǎn)相對應(yīng)，那么稱這樣的二叉樹為完全二叉樹。應(yīng)，那么稱這樣的二

13、叉樹為完全二叉樹。完全二叉樹的特點(diǎn)是：完全二叉樹的特點(diǎn)是：1一切的葉結(jié)點(diǎn)都出如今第一切的葉結(jié)點(diǎn)都出如今第k層或?qū)踊騥1層。層。2對任一結(jié)點(diǎn)，假設(shè)其右子樹的最大層次為對任一結(jié)點(diǎn)，假設(shè)其右子樹的最大層次為h，那么其左子樹的最大層次為那么其左子樹的最大層次為h或或h1。滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹16 性質(zhì)性質(zhì)4：具有：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n1。符號符號x表示不大于表示不大于x的最大整數(shù)。的最大整數(shù)。 證明：假設(shè)此二叉樹的深度為證明：假設(shè)此二叉樹的深度為k，那么根據(jù)性質(zhì)，那么根據(jù)性質(zhì)2及完及完全二叉樹的定義得到：全二叉樹的定義得到：2k-11

14、n=2k-1 或或 2k-1=n2k取對數(shù)得到：取對數(shù)得到：k1log2nk 由于由于k是整數(shù)。所以有：是整數(shù)。所以有：klog2n1。二叉樹的重要特性二叉樹的重要特性17性質(zhì)性質(zhì)5： 假設(shè)對一棵有假設(shè)對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號從第層序編號從第1層到第層到第log2n+1層，每層從左到右層，每層從左到右),那么對任一結(jié)點(diǎn)那么對任一結(jié)點(diǎn)i1=i1，那么其雙親是結(jié)點(diǎn)，那么其雙親是結(jié)點(diǎn)i/2。 2假設(shè)假設(shè)2in，那么結(jié)點(diǎn)，那么結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；為葉子結(jié)點(diǎn)，無左孩子；否那么，其左孩子是結(jié)點(diǎn)否那么，其左孩子是結(jié)點(diǎn)2i。 3假設(shè)假設(shè)2i1n，那么結(jié)點(diǎn)，

15、那么結(jié)點(diǎn)i無右孩子；否那么，其無右孩子；否那么，其右孩子是結(jié)點(diǎn)右孩子是結(jié)點(diǎn)2i1。證明：略！證明：略！完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn): :186.3 6.3 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造1.順序存儲構(gòu)造順序存儲構(gòu)造它是用一組延續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。它是用一組延續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。因此，必需把二叉樹的一切結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛞虼?，必需把二叉樹的一切結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄校Y(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的列，結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系，用編號的方法：邏輯關(guān)系，用編號的方法： #define max-tree-size 1

16、00Typedef telemtype sqbitreemax-tree-size;Sqbitree bt 從樹根起，自上層至下層，每層自左至右的給一切從樹根起，自上層至下層，每層自左至右的給一切結(jié)點(diǎn)編號。結(jié)點(diǎn)編號。19LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12完全二叉樹完全二叉樹ABCDEFGHIJKL20ABCDEFG 表示該處沒有元素表示該處沒有元素存在僅僅為了好了解存在僅僅為了好了解ABCDEFG普通二叉樹普通二叉樹211.1.順序存儲構(gòu)造順序存儲構(gòu)造缺陷：有能夠?qū)Υ鎯臻g呵斥極大的浪費(fèi)，在最缺陷：有能夠?qū)Υ鎯臻g呵斥極大的浪費(fèi)，在最壞的情況下，一個(gè)

17、深度為壞的情況下，一個(gè)深度為H且只需且只需H個(gè)結(jié)點(diǎn)的右單支樹個(gè)結(jié)點(diǎn)的右單支樹確需求確需求2h-1個(gè)結(jié)點(diǎn)存儲空間。而且，假設(shè)經(jīng)常需求插個(gè)結(jié)點(diǎn)存儲空間。而且，假設(shè)經(jīng)常需求插入與刪除樹中結(jié)點(diǎn)時(shí)，順序存儲方式不是很好！入與刪除樹中結(jié)點(diǎn)時(shí)，順序存儲方式不是很好！221.1.順序存儲構(gòu)造順序存儲構(gòu)造ABCDindexindex 0 01 1 2 23 34 4 5 5 6 6 7 78 8 9 9 1010 1111 1212 1313 1414 1515A A B B C C D D- - - -23lchildDatarchildABCDEFGH2 2二叉鏈表法二叉鏈表法ABCDEFGH24Typed

18、ef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;2 2二叉鏈表法二叉鏈表法二叉樹的二叉鏈表存儲表示二叉樹的二叉鏈表存儲表示25Status CreateBiTree(BiTree *T) /*創(chuàng)建一棵二叉樹創(chuàng)建一棵二叉樹*/ scanf(&ch); if(ch= =) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Tdata=ch; CreateBiTree(Tlchild);

19、CreateBiTree(Trchildd); return OK; 6.3 6.3 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造鏈?zhǔn)酱鎯?gòu)造的算法：鏈?zhǔn)酱鎯?gòu)造的算法：26三叉鏈表法三叉鏈表法ABCDEFGHDBCEFGHArchildparentdatalchild27Typedef struct TBiTNode TelemType data; struct TBiTNode *lchild,*rchild,*parent; BiTNode,*BiTree;三叉鏈表法三叉鏈表法二叉樹的三叉鏈表存儲表示二叉樹的三叉鏈表存儲表示286.4 6.4 二叉樹的遍歷二叉樹的遍歷一、問題的提出一、問題的提出順著

20、某一條搜索途徑巡訪二叉樹中的結(jié)點(diǎn)，使得每順著某一條搜索途徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次?！霸L問的含義可以很廣，如：輸出結(jié)點(diǎn)的信息訪問的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。等。 對對“二叉樹而言，可以有三條搜索途徑：二叉樹而言，可以有三條搜索途徑：1先上后下的按層次遍歷；先上后下的按層次遍歷；2先左子樹后右子樹的遍歷；先左子樹后右子樹的遍歷；3先右子樹后左子樹的遍歷。先右子樹后左子樹的遍歷。296.4 6.4 二叉樹的遍歷二叉樹的遍歷二、先左后右的遍歷算法二、先左后右的遍歷算法 先根序的遍歷算法：先根序的遍歷算法：假設(shè)二叉樹

21、為空樹，那么空操作；否那么，假設(shè)二叉樹為空樹，那么空操作；否那么，1訪問根結(jié)訪問根結(jié)點(diǎn)；點(diǎn)； 2先序遍歷左子樹；先序遍歷左子樹； 3先序遍歷右子樹。先序遍歷右子樹。中根序的遍歷算法：中根序的遍歷算法：假設(shè)二叉樹為空樹假設(shè)二叉樹為空樹,那么空操作；否那么那么空操作；否那么,1中序遍歷左中序遍歷左子樹；子樹；2訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 3中序遍歷右子樹。中序遍歷右子樹。后根序的遍歷算法：后根序的遍歷算法：假設(shè)二叉樹為空樹假設(shè)二叉樹為空樹,那么空操作那么空操作;否那么否那么,1后序遍歷左子后序遍歷左子樹；樹； 2后序遍歷右子樹；后序遍歷右子樹； 3訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。 306.4 6.4 二叉樹

22、的遍歷二叉樹的遍歷例如例如/-abcd圖圖1 (a-b)/(c+d)/bca-+d圖圖2 a-(b/c+d)/bca-+d圖圖3 a-b/c+d先序：先序：/-ab+cd中序：中序：a-b/c+d后序：后序：ab-cd+/先序：先序：-a+/bcd中序：中序：a-b/c+d后序：后序：abc/d+-先序：先序：+-a/bcd中序：中序：a-b/c+d后序：后序：abc/-d+分別稱為表達(dá)式的前綴表示法、中綴表示法和后綴表示分別稱為表達(dá)式的前綴表示法、中綴表示法和后綴表示法逆波蘭表示法。法逆波蘭表示法。316.4 6.4 二叉樹的遍歷二叉樹的遍歷三、算法的遞歸描畫三、算法的遞歸描畫 void P

23、reorder (BiTree T, void( *visit)(TElemType& e) / 先序遍歷二叉樹先序遍歷二叉樹 if (T) visit(T-data; / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)Preorder(T-lchild, visit); / 遍歷左子樹遍歷左子樹Preorder(T-rchild, visit); / 遍歷右子樹遍歷右子樹32void InOrderTraverse (BiTree T, void( *visit)(TElemType &e)/中序遍歷中序遍歷if(T)InOrderTraverse (T-lchild, visit); visit(T-d

24、ata; / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)InOrderTraverse (T-rchild, visit);void PostOrderTraverse (BiTree T, void( *visit)(TElemType &e)/后序遍歷后序遍歷if(T)PostOrderTraverse (T-lchild, visit);PostOrderTraverse (T-rchild, visit); visit(T-data; / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)33四、先序遍歷算法的非遞歸描畫四、先序遍歷算法的非遞歸描畫先序遍歷的非遞歸算法。先序遍歷的非遞歸算法。t指向根，指向根，p為指針，指為指針，指向當(dāng)前

25、結(jié)點(diǎn)。運(yùn)用一個(gè)堆棧向當(dāng)前結(jié)點(diǎn)。運(yùn)用一個(gè)堆棧s，top為棧指針為棧指針 1 if t=NULL 2 then 輸出輸出 這是一棵空樹這是一棵空樹 3 else p=t，top=0 4 DO 5 while p！=NULL 6 輸出輸出 datap; 7 top+;8 if topn9 then 調(diào)用調(diào)用 棧滿棧滿 10 else stop=p，p=lchildp11 if top！=012 p=stop; top-; p=rchildp13while( top=0 & p=null)算法終了算法終了6.4 6.4 二叉樹的遍歷二叉樹的遍歷四、先序遍歷算法的非遞歸描畫四、先序遍歷算法的非遞

26、歸描畫1 if t=NULL2 then 輸出輸出 這是一棵空樹這是一棵空樹 3 else p=t，top=0 4 DO 5 while p！=NULL 6 輸出輸出 datap;7 top+;8 if topn9 then 調(diào)用調(diào)用 棧滿棧滿10 else stop=p，p=lchildp11 if top！=012 p=stop; top-; p=rchildp13while( top=0 & p=null)算法終了算法終了注注:結(jié)點(diǎn)旁結(jié)點(diǎn)旁的數(shù)字是的數(shù)字是該結(jié)點(diǎn)的該結(jié)點(diǎn)的存儲地址存儲地址二叉樹執(zhí)行先序遍歷二叉樹執(zhí)行先序遍歷算法的過程算法的過程棧棧35中序遍歷的非遞歸算法中序遍歷的

27、非遞歸算法中序遍歷的非遞歸算法，運(yùn)用堆棧中序遍歷的非遞歸算法，運(yùn)用堆棧s，top為指針，為指針，t指向根，指向根，p為指針，指向當(dāng)前結(jié)點(diǎn)為指針，指向當(dāng)前結(jié)點(diǎn)1 top=0,p=t2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn )6 then 調(diào)用調(diào)用 棧滿棧滿7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 輸出輸出 data(p) 11 pn )6 then 調(diào)用調(diào)用 棧滿棧滿7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-1

28、0 輸出輸出 data(p) 11 plchild)& (!T-rchild)count+;CountLeaf( T-lchild, count); / 統(tǒng)計(jì)左子樹中葉子結(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)左子樹中葉子結(jié)點(diǎn)個(gè)數(shù)CountLeaf( T-rchild, count);/ 統(tǒng)計(jì)右子樹中葉子結(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)右子樹中葉子結(jié)點(diǎn)個(gè)數(shù)38五、遍歷算法的運(yùn)用舉例五、遍歷算法的運(yùn)用舉例2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)int Depth (BiTree T )if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild );depthRight

29、= Depth( T-rchild );depthval = 1+(depthLeft depthRight? depthLeft:depthRight);return depthval;39五、遍歷算法的運(yùn)用舉例五、遍歷算法的運(yùn)用舉例3、復(fù)制二叉樹、復(fù)制二叉樹(后序遍歷后序遍歷)/ 生成一個(gè)二叉樹的結(jié)點(diǎn)生成一個(gè)二叉樹的結(jié)點(diǎn)BiTNode *GetTreeNode(TElemType item,BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode)exit(1); T- data = item; T-

30、 lchild = lptr； T- rchild = rptr; return T;40五、遍歷算法的運(yùn)用舉例五、遍歷算法的運(yùn)用舉例3、復(fù)制二叉樹、復(fù)制二叉樹(后序遍歷后序遍歷)BiTNode *CopyTree(BiTNode *T) if (!T )return NULL;if (T-lchild ) newlptr = CopyTree(T-lchild);else newlptr = NULL;if (T-rchild ) newrptr = CopyTree(T-rchild);else newrptr = NULL;newnode = GetTreeNode(T-data, ne

31、wlptr, newrptr);return newnode;416.5 6.5 線索二叉樹線索二叉樹一、何謂線索二叉樹？一、何謂線索二叉樹？遍歷二叉樹是按一定的規(guī)那么將二叉樹中結(jié)點(diǎn)陳列遍歷二叉樹是按一定的規(guī)那么將二叉樹中結(jié)點(diǎn)陳列成一個(gè)線性序列；這實(shí)踐上是把一個(gè)非線性構(gòu)造進(jìn)展線成一個(gè)線性序列；這實(shí)踐上是把一個(gè)非線性構(gòu)造進(jìn)展線性化的操作。性化的操作。以二叉鏈表作為存儲構(gòu)造時(shí)，對于某個(gè)結(jié)點(diǎn)只能找以二叉鏈表作為存儲構(gòu)造時(shí)，對于某個(gè)結(jié)點(diǎn)只能找到其左右孩子，而不能直接得到結(jié)點(diǎn)在任一序列中的前到其左右孩子，而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)或后繼。要想得到只能經(jīng)過遍歷的動態(tài)過程才行。驅(qū)或后繼。要想得到只

32、能經(jīng)過遍歷的動態(tài)過程才行。怎樣保管遍歷過程中得到的信息呢？怎樣保管遍歷過程中得到的信息呢？1添加兩個(gè)指針添加兩個(gè)指針2利用構(gòu)造中的空鏈域，并設(shè)立標(biāo)志。即采用如利用構(gòu)造中的空鏈域，并設(shè)立標(biāo)志。即采用如下的方式：下的方式：lchild ltagdatartagrchild426.5 6.5 線索二叉樹線索二叉樹何謂線索二叉樹？何謂線索二叉樹？ 指向該線性序列中的指向該線性序列中的“前驅(qū)和前驅(qū)和“后繼的指針，稱作后繼的指針，稱作“線索。包含線索。包含“線索的存儲構(gòu)造，稱作線索的存儲構(gòu)造，稱作“線索鏈表；線索鏈表；與其相應(yīng)的二叉樹，稱作與其相應(yīng)的二叉樹，稱作“線索二叉樹。線索二叉樹。對線索鏈表中結(jié)點(diǎn)的

33、商定：對線索鏈表中結(jié)點(diǎn)的商定：在二叉鏈表的結(jié)點(diǎn)中添加兩個(gè)標(biāo)志域，并作如下規(guī)定：在二叉鏈表的結(jié)點(diǎn)中添加兩個(gè)標(biāo)志域，并作如下規(guī)定：假設(shè)該結(jié)點(diǎn)的左子樹不空，那么假設(shè)該結(jié)點(diǎn)的左子樹不空，那么lchild域的指針指向其域的指針指向其左子樹，且左標(biāo)志域左子樹，且左標(biāo)志域 ltag的值為的值為0； 否那么，否那么，lchild域的指針指向其域的指針指向其“前驅(qū)，且左標(biāo)志前驅(qū)，且左標(biāo)志ltag的值為的值為1。假設(shè)該結(jié)點(diǎn)的右子樹不空，那么假設(shè)該結(jié)點(diǎn)的右子樹不空，那么rchild域的指針指向域的指針指向其右子樹，且右標(biāo)志域其右子樹，且右標(biāo)志域rtag的值為的值為0；否那么，否那么，rchild域的指針指向其域的指

34、針指向其“后繼，且右標(biāo)志后繼，且右標(biāo)志rtag的值為的值為1。 436.5 6.5 線索二叉樹線索二叉樹0 A 01B 00D 1 1C 11E 1TADBEC中序序列：中序序列：BCAED446.5 6.5 線索二叉樹線索二叉樹線索鏈表的構(gòu)造描畫：線索鏈表的構(gòu)造描畫：typedef enum Link, Thread PointerThr; / Link=0:指針，指針，Thread=1:線索線索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild, *rchild; / 左右指針左右指針PointerThr LTag

35、, RTag; / 左右標(biāo)志左右標(biāo)志 BiThrNode, *BiThrTree;6.5 6.5 線索二叉樹線索二叉樹找結(jié)點(diǎn)的后繼找結(jié)點(diǎn)的后繼線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。過程叫做線索化。下面以中序?yàn)槔纯慈绾卧诰€索二叉樹中找結(jié)點(diǎn)的后繼。下面以中序?yàn)槔纯慈绾卧诰€索二叉樹中找結(jié)點(diǎn)的后繼。1樹中一切葉子結(jié)點(diǎn)和只需左子樹的右指針均為線索，樹中一切葉子結(jié)點(diǎn)和只需左子樹的右指針均為線索，直接指示了結(jié)點(diǎn)的后繼；直接指示了結(jié)點(diǎn)的后繼；2其他非終端結(jié)點(diǎn)的右鏈均為指針，無法得到后繼的信其他非終端結(jié)點(diǎn)的右鏈均為指針，無法得到后

36、繼的信息。然而根據(jù)中序遍歷的規(guī)律可知，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右息。然而根據(jù)中序遍歷的規(guī)律可知，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)，即右子樹中最左下的結(jié)點(diǎn)。子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)，即右子樹中最左下的結(jié)點(diǎn)。3反之，在中序線索樹中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：假設(shè)左反之，在中序線索樹中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：假設(shè)左標(biāo)志是標(biāo)志是1，那么左鏈為線索，指示其前驅(qū)；否那么，遍歷該結(jié)點(diǎn)，那么左鏈為線索，指示其前驅(qū)；否那么，遍歷該結(jié)點(diǎn)的左子樹時(shí)最后訪問的結(jié)點(diǎn)左子樹中最右下的結(jié)點(diǎn)為其前驅(qū)的左子樹時(shí)最后訪問的結(jié)點(diǎn)左子樹中最右下的結(jié)點(diǎn)為其前驅(qū))。ABCEIDHF GGKnullnull6.5 6.5 線索二叉樹線索二叉樹找

37、結(jié)點(diǎn)的后繼找結(jié)點(diǎn)的后繼在后序線索樹中找結(jié)點(diǎn)在后序線索樹中找結(jié)點(diǎn)x的后繼較復(fù)雜，可分三種情況：的后繼較復(fù)雜，可分三種情況：1假設(shè)結(jié)點(diǎn)假設(shè)結(jié)點(diǎn)x是二叉樹的根是二叉樹的根,那么其后繼為空那么其后繼為空;2假設(shè)結(jié)點(diǎn)假設(shè)結(jié)點(diǎn)x是其雙親的右孩子或是左孩子且其雙親沒是其雙親的右孩子或是左孩子且其雙親沒有右子樹有右子樹,那么其后繼即為雙親結(jié)點(diǎn)。那么其后繼即為雙親結(jié)點(diǎn)。3假設(shè)結(jié)點(diǎn)假設(shè)結(jié)點(diǎn)x是其雙親的左孩子，且其雙親有右子樹，是其雙親的左孩子，且其雙親有右子樹，那么其后繼為雙親的右子樹上按后序遍歷出的第一個(gè)結(jié)點(diǎn)。那么其后繼為雙親的右子樹上按后序遍歷出的第一個(gè)結(jié)點(diǎn)。由此可見，在后序線索化樹上找后繼時(shí)需知道結(jié)點(diǎn)的雙親

38、，由此可見，在后序線索化樹上找后繼時(shí)需知道結(jié)點(diǎn)的雙親，因此需求運(yùn)用三叉鏈表。因此需求運(yùn)用三叉鏈表?？梢?，在中序線索二叉樹上遍歷二叉樹，雖然時(shí)間復(fù)雜度可見，在中序線索二叉樹上遍歷二叉樹，雖然時(shí)間復(fù)雜度也是也是O(n)，但常數(shù)因子小，且不需求設(shè)棧，因此假設(shè)在某程序，但常數(shù)因子小，且不需求設(shè)棧，因此假設(shè)在某程序中需求經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后中需求經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼，那么應(yīng)采用線索鏈表作存儲構(gòu)造。繼，那么應(yīng)采用線索鏈表作存儲構(gòu)造。6.5 6.5 線索二叉樹線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法:for ( p = firstNod

39、e(T); p; p = Succ(p) )Visit(p);中序線索化鏈表的遍歷算法中序線索化鏈表的遍歷算法:中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？ABCEIDHF GGKnullnull6.5 6.5 線索二叉樹線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法:Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) / T指向頭結(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)的右鏈rchil

40、d， 指向中序遍歷的最后一個(gè)結(jié)點(diǎn)。中序遍指向中序遍歷的最后一個(gè)結(jié)點(diǎn)。中序遍歷二叉線索鏈表表示的二叉樹，對每個(gè)數(shù)據(jù)元素歷二叉線索鏈表表示的二叉樹，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)調(diào)用函數(shù)Visit。p = T-lchild; / p指向根結(jié)點(diǎn)指向根結(jié)點(diǎn)while (p != T) / 空樹或遍歷終了時(shí)，空樹或遍歷終了時(shí)，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR;/ 訪問其左訪問其左子樹為空的結(jié)點(diǎn)子樹為空的結(jié)點(diǎn) while (p-RTag=Thread & p-rchild!=T) p = p-rchi

41、ld; Visit(p-data); / 訪問后繼結(jié)點(diǎn)訪問后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根進(jìn)至其右子樹根 return OK; / InOrderTraverse_ThrT-+/*-abe fc d496.5 6.5 線索二叉樹線索二叉樹三、如何建立線索鏈表？三、如何建立線索鏈表？在中序遍歷過程中修正結(jié)點(diǎn)的左、右指針域，在中序遍歷過程中修正結(jié)點(diǎn)的左、右指針域，以保管當(dāng)前訪問結(jié)點(diǎn)的以保管當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)和前驅(qū)和“后繼信息。后繼信息。遍歷過程中，附設(shè)指針遍歷過程中，附設(shè)指針pre,并一直堅(jiān)持指針并一直堅(jiān)持指針pre指向當(dāng)前訪問的、指針指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前

42、驅(qū)。所指結(jié)點(diǎn)的前驅(qū)。6.5 6.5 線索二叉樹線索二叉樹三、如何建立線索鏈表？三、如何建立線索鏈表？Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 中中序遍歷二叉樹序遍歷二叉樹T，并將其中序線索化，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)。指向頭結(jié)點(diǎn)。if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW);Thrt-LTag = Link; Thrt-RTag =Thread; / 建頭結(jié)點(diǎn)建頭結(jié)點(diǎn)Thrt-rchild = Thrt; / 右指針回指右

43、指針回指if (!T) Thrt-lchild = Thrt; / 假設(shè)二叉樹空，那么左指針回指假設(shè)二叉樹空，那么左指針回指else Thrt-lchild = T; pre = Thrt;InThreading(T); / 中序遍歷進(jìn)展中序線索化中序遍歷進(jìn)展中序線索化pre-rchild = Thrt; pre-RTag = Thread; / 最后一個(gè)結(jié)點(diǎn)線索化最后一個(gè)結(jié)點(diǎn)線索化Thrt-rchild = pre; return OK; / InOrderThreadingvoid InThreading(BiThrTree p) if (p) InThreading(p-lchild);

44、 / 左子樹線索化左子樹線索化if (!p-lchild) p-LTag = Thread; p-lchild = pre; / 建前驅(qū)線索建前驅(qū)線索if (!pre-rchild) pre-RTag = Thread; pre-rchild = p; / 建后繼線索建后繼線索pre = p; / 堅(jiān)持堅(jiān)持pre指向指向p的前驅(qū)的前驅(qū)InThreading(p-rchild); / 右子樹線索化右子樹線索化 / InThreading526.6 6.6 樹和森林樹和森林一、樹的三種存儲構(gòu)造一、樹的三種存儲構(gòu)造1. 雙親表示法雙親表示法:在這種表示中，容易找到父結(jié)點(diǎn)及其一切的祖先；在這種表示中，

45、容易找到父結(jié)點(diǎn)及其一切的祖先；也能找到結(jié)點(diǎn)的子女和兄弟雖然比較費(fèi)事。但它沒有也能找到結(jié)點(diǎn)的子女和兄弟雖然比較費(fèi)事。但它沒有表示出結(jié)點(diǎn)之間的左右次序，所以無法求樹中某個(gè)指定結(jié)表示出結(jié)點(diǎn)之間的左右次序，所以無法求樹中某個(gè)指定結(jié)點(diǎn)的最左子結(jié)點(diǎn)和右兄弟結(jié)點(diǎn)等根本運(yùn)算。點(diǎn)的最左子結(jié)點(diǎn)和右兄弟結(jié)點(diǎn)等根本運(yùn)算。ABCDEFGHIJKLM8M5L5K4J4I4H3G2F2E1D1C1B-1A1234567891011121353一、樹的三種存儲構(gòu)造一、樹的三種存儲構(gòu)造1. 雙親表示法雙親表示法:用一組延續(xù)空間存儲樹的結(jié)點(diǎn)，并附設(shè)一個(gè)指用一組延續(xù)空間存儲樹的結(jié)點(diǎn)，并附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)的位置。構(gòu)造類型如

46、下：示器指示其雙親結(jié)點(diǎn)的位置。構(gòu)造類型如下：#define MAX_TREE_SIZE 100結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn)構(gòu)造:typedef struct PTNode /* 樹中結(jié)點(diǎn)構(gòu)造樹中結(jié)點(diǎn)構(gòu)造 */Elem data; /* 結(jié)點(diǎn)中的元素結(jié)點(diǎn)中的元素 */int parent; / 雙親位置域雙親位置域 PTNode;樹構(gòu)造樹構(gòu)造:typedef struct PTNode nodesMAX_TREE_SIZE;int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree一、樹的三種存儲構(gòu)造一、樹的三種存儲構(gòu)造2. 孩子鏈表表示法孩子鏈表表示法:ABCDEFGHIJKLMMLKJ

47、IHGFEDCBA12345678910111213234 56 13 78910 1112 55一、樹的三種存儲構(gòu)造一、樹的三種存儲構(gòu)造2、孩子鏈表表示法、孩子鏈表表示法:結(jié)點(diǎn)表中的每一元素又包含一個(gè)子表，存放該結(jié)點(diǎn)結(jié)點(diǎn)表中的每一元素又包含一個(gè)子表，存放該結(jié)點(diǎn)的一切子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放，子表用鏈接表示，子的一切子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放，子表用鏈接表示，子表中的元素按從左到右的次序存放。構(gòu)造類型如下：表中的元素按從左到右的次序存放。構(gòu)造類型如下：雙親結(jié)點(diǎn)構(gòu)造雙親結(jié)點(diǎn)構(gòu)造typedef struct Elem data;ChildPtr firstchild; / 孩子鏈的頭指針孩子鏈的頭指針

48、CTBox;樹構(gòu)造樹構(gòu)造:typedef struct CTBox nodesMAX_TREE_SIZE;int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;孩子結(jié)點(diǎn)構(gòu)造孩子結(jié)點(diǎn)構(gòu)造:typedef struct CTNode int child;struct CTNode *next; *ChildPtr;56一、樹的三種存儲構(gòu)造一、樹的三種存儲構(gòu)造帶雙親的孩子鏈表表示法帶雙親的孩子鏈表表示法:ABCDEFGHIJKLM222 56 13 78910 1112 8M5L5K4J4I4H3G2F2E1D1C1B-1A1234567891011121357一、樹的三種存

49、儲構(gòu)造一、樹的三種存儲構(gòu)造3、樹的二叉鏈表、樹的二叉鏈表(孩子孩子-兄弟存儲表示法兄弟存儲表示法typedef struct CSNodeElem data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;ABCDEFGHIJKLMABCDEKFGHMIJL58二、樹、樹林與二叉樹的轉(zhuǎn)換二、樹、樹林與二叉樹的轉(zhuǎn)換1、樹、樹林轉(zhuǎn)換為二叉樹、樹、樹林轉(zhuǎn)換為二叉樹由于樹和二叉樹都可以用二叉鏈表作存儲構(gòu)造，由于樹和二叉樹都可以用二叉鏈表作存儲構(gòu)造，那么以二叉鏈表作媒介可以導(dǎo)出樹與二叉樹之間的那么以二叉鏈表作媒介可以導(dǎo)出樹與二叉樹之間的一

50、個(gè)對應(yīng)關(guān)系。一個(gè)對應(yīng)關(guān)系。從二叉鏈表表示的定義可知，任何一棵和樹對從二叉鏈表表示的定義可知，任何一棵和樹對應(yīng)的二叉樹，其右子樹必空。這樣，假設(shè)把森林中應(yīng)的二叉樹，其右子樹必空。這樣，假設(shè)把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的兄弟，那么可第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的兄弟，那么可以導(dǎo)出森林和二叉樹之間的對應(yīng)關(guān)系。以導(dǎo)出森林和二叉樹之間的對應(yīng)關(guān)系。59二、樹、樹林與二叉樹的轉(zhuǎn)換二、樹、樹林與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹轉(zhuǎn)換規(guī)那么：轉(zhuǎn)換規(guī)那么：步驟：步驟：1.將同父親的兄弟結(jié)點(diǎn)銜接；將同父親的兄弟結(jié)點(diǎn)銜接；2.對每一個(gè)非葉結(jié)點(diǎn)只保管第一個(gè)孩子鏈，刪對每一個(gè)非葉結(jié)點(diǎn)只保管第一個(gè)孩子鏈，

51、刪除其他孩子的鏈；除其他孩子的鏈；3.將樹向左旋轉(zhuǎn)將樹向左旋轉(zhuǎn)450。60樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹事例事例ABEDCHJIGFABEDCHJIGF61樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹事例事例ABEDCHJIGFABEDCHJIGF622 2、森林轉(zhuǎn)換成二叉樹、森林轉(zhuǎn)換成二叉樹轉(zhuǎn)換規(guī)那么：轉(zhuǎn)換規(guī)那么：假設(shè)假設(shè)FT1, T2, , Tm是森林，那么可按如下是森林，那么可按如下規(guī)那么轉(zhuǎn)換成一棵二叉樹規(guī)那么轉(zhuǎn)換成一棵二叉樹Broot, LB, RB。1假設(shè)假設(shè)F為空，那么為空，那么B為空樹；為空樹；2假設(shè)假設(shè)F非空，那么非空，那么B的根的根root為森林中第一為森林中第一棵樹的根棵樹的根Root(T1

52、)，B的左子樹的左子樹LB是從是從T1中根結(jié)點(diǎn)的中根結(jié)點(diǎn)的子樹森林子樹森林F1T11, T12, T1m1轉(zhuǎn)換而成的二叉樹；轉(zhuǎn)換而成的二叉樹；其右子樹其右子樹RB是從森林是從森林FT2, T3, , Tm轉(zhuǎn)換而成轉(zhuǎn)換而成的二叉樹。的二叉樹。63 AB E GC D F HI AB E GC DF HIA B E GC D FHI2 2、森林轉(zhuǎn)換成二叉樹、森林轉(zhuǎn)換成二叉樹643 3、二叉樹轉(zhuǎn)換為樹、二叉樹轉(zhuǎn)換為樹轉(zhuǎn)換規(guī)那么：轉(zhuǎn)換規(guī)那么：1.對有左子樹的一切結(jié)點(diǎn)與其左孩子的右鏈上的對有左子樹的一切結(jié)點(diǎn)與其左孩子的右鏈上的一切結(jié)點(diǎn)進(jìn)展銜接；一切結(jié)點(diǎn)進(jìn)展銜接；2.刪除以前一切的舊右鏈。刪除以前一切的舊

53、右鏈。ABEDCHJIGFABEDCHJIGF654 4、二叉樹轉(zhuǎn)換成森林、二叉樹轉(zhuǎn)換成森林轉(zhuǎn)換規(guī)那么：轉(zhuǎn)換規(guī)那么：假設(shè)假設(shè)Broot, LB, RB 是一棵二叉樹，那么可按是一棵二叉樹，那么可按如下規(guī)那么轉(zhuǎn)換成森林如下規(guī)那么轉(zhuǎn)換成森林FT1, T2, , Tm1假設(shè)假設(shè)B為空，那么為空，那么F為空樹；為空樹；2假設(shè)假設(shè)B非空，那么為森林中第一棵樹的根非空，那么為森林中第一棵樹的根RootT1即為即為 B的根的根root， T1中根結(jié)點(diǎn)的子樹森林中根結(jié)點(diǎn)的子樹森林F1T11, T12, T1m1 是有是有B的左子樹的左子樹LB轉(zhuǎn)換而來轉(zhuǎn)換而來的森林；的森林；F中除中除T1之外的其他樹組成的森林

54、之外的其他樹組成的森林FT2, T3, , Tm是由是由B的右子樹轉(zhuǎn)換而成的。的右子樹轉(zhuǎn)換而成的。66二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林例如例如A B C FD GE HIA B CFD G E HI67 假設(shè)樹假設(shè)樹T為空為空, 前往；否那么前往；否那么 訪問訪問T的根結(jié)點(diǎn)；的根結(jié)點(diǎn)； 依次先根次序遍歷各子樹依次先根次序遍歷各子樹T1、T2Tm；右圖遍歷結(jié)果為：右圖遍歷結(jié)果為：A B D E H I J C F G三、三、 樹和森林的遍歷樹和森林的遍歷(1) 先根次序遍歷的規(guī)那么：先根次序遍歷的規(guī)那么：ABEDCHJIGF68 假設(shè)樹假設(shè)樹T為空，前往；否那么為空，前往；否那么 依次后根次序遍

55、歷各子樹依次后根次序遍歷各子樹T1、T2Tm； 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。右圖遍歷結(jié)果為：右圖遍歷結(jié)果為：D H I J E B F G C A樹的遍歷樹的遍歷(2) 后根次序遍歷的規(guī)那么：后根次序遍歷的規(guī)那么：ABEDCHJIGF69 假設(shè)樹假設(shè)樹T為空，前往；否那么為空，前往；否那么 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 假設(shè)第假設(shè)第1,i(i1層結(jié)點(diǎn)已被層結(jié)點(diǎn)已被訪問，那么從左到右依次訪問訪問，那么從左到右依次訪問i+1層層結(jié)點(diǎn)；結(jié)點(diǎn)；右圖遍歷結(jié)果為：右圖遍歷結(jié)果為：A B C D E F G H I J樹的遍歷樹的遍歷(3) 廣度優(yōu)先遍歷廣度優(yōu)先遍歷(層次序遍歷層次序遍歷) ：ABEDCHJIGF7

56、0 假設(shè)森林假設(shè)森林F為空為空, 前往；否那么前往；否那么 訪問訪問F的第一棵樹的根結(jié)點(diǎn)；的第一棵樹的根結(jié)點(diǎn)； 先根次序遍歷第一棵樹的子樹森林；先根次序遍歷第一棵樹的子樹森林； 先根次序遍歷其它樹組成的森林。先根次序遍歷其它樹組成的森林。遍歷結(jié)果：遍歷結(jié)果：A B C D E F G H I J森林的遍歷森林的遍歷(1) 先根次序遍歷的規(guī)那么：先根次序遍歷的規(guī)那么： AB E GC D F HIJ 71 假設(shè)森林假設(shè)森林F為空，前往；否那么為空，前往；否那么 中根次序遍歷第一棵樹的子樹森林；中根次序遍歷第一棵樹的子樹森林； 訪問訪問F的第一棵樹的根結(jié)點(diǎn)。的第一棵樹的根結(jié)點(diǎn)。 中根次序遍歷其它樹

57、組成的森林；中根次序遍歷其它樹組成的森林； 遍歷結(jié)果：遍歷結(jié)果：B C D A F E H J I G森林的遍歷森林的遍歷(2) 中根次序遍歷的規(guī)那么：中根次序遍歷的規(guī)那么： AB E GC D F HIJ 72 假設(shè)森林假設(shè)森林F為空，前往；否那么為空，前往；否那么 依次遍歷各棵樹的根結(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é)果：遍歷結(jié)果：A E G B C D F H I J森林的遍歷森林的遍歷(3) 廣度優(yōu)先遍歷廣度優(yōu)先遍歷(層次序遍歷層次序遍歷) ： AB E

58、GC D F HIJ 736.7 6.7 哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼一、最優(yōu)樹的定義一、最優(yōu)樹的定義結(jié)點(diǎn)的途徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的途徑上分支結(jié)點(diǎn)的途徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的途徑上分支的數(shù)目。的數(shù)目。樹的途徑長度：樹中每個(gè)結(jié)點(diǎn)的途徑長度之和。樹的途徑長度：樹中每個(gè)結(jié)點(diǎn)的途徑長度之和。樹的帶權(quán)途徑長度：樹中一切葉子結(jié)點(diǎn)的帶權(quán)途徑樹的帶權(quán)途徑長度：樹中一切葉子結(jié)點(diǎn)的帶權(quán)途徑長度之和長度之和WPL(T) = wklk (對一切葉子結(jié)點(diǎn)對一切葉子結(jié)點(diǎn))。在一切含在一切含n個(gè)葉子結(jié)點(diǎn)、并帶一樣權(quán)值的個(gè)葉子結(jié)點(diǎn)、并帶一樣權(quán)值的m叉樹中，叉樹中，必存在一棵其帶權(quán)途徑長度取最小值的樹，稱為必

59、存在一棵其帶權(quán)途徑長度取最小值的樹，稱為“最優(yōu)最優(yōu)樹樹74分分?jǐn)?shù)數(shù) 059 6069 7079 8089 90100 比比例例數(shù)數(shù) 005 015 040 030 010 a60a70a80a90badpassgeneralgoodexcellentYYYYNNNN例如下面的程序：例如下面的程序：if(a 60)p = “bad;else if(a 70)p = “pass; else if(a 80)p = “general; else if(a 90) p = “good; elsep = “excellent;75a80a70a90a60generalbadpassgoodexcelle

60、ntYYYYNNN70=a8080=a9060=a70a60generalgoodpassbadexcellentYYYYNNNN76二、如何構(gòu)造最優(yōu)樹二、如何構(gòu)造最優(yōu)樹哈夫曼最早研討出一個(gè)帶有普通規(guī)律的算法哈夫曼最早研討出一個(gè)帶有普通規(guī)律的算法:以二叉樹為例以二叉樹為例:(1) 根據(jù)給定的根據(jù)給定的n個(gè)權(quán)值個(gè)權(quán)值w1, w2, , wn，構(gòu)造，構(gòu)造n棵二棵二叉樹的集合叉樹的集合F = T1, T2, , Tn，其中每棵二叉樹中均只，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；的根結(jié)點(diǎn)，其左、右子樹為空樹；(2) 在在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;(3) 從從F中刪去這兩棵樹，同時(shí)參與剛生成的新樹中刪去這兩棵樹，同