數(shù)據(jù)結(jié)構(gòu)：第06章 樹和二叉樹

1、6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第六章第六章 樹和二叉樹樹和二叉樹2022年年3月月30日星期三日星期三6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 2ABCDEFGHIJKLM樹樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹

2、與哈夫曼編碼 36.1 6.1 樹的類型定義樹的類型定義數(shù)據(jù)對象數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 若若D為空集，則稱為空樹；為空集，則稱為空樹； 否則否則:（1）在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root,（2）當(dāng)當(dāng)n1時，其余結(jié)點(diǎn)可分為時，其余結(jié)點(diǎn)可分為m(m0)個互不相交的個互不相交的有限集有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵符其中每一棵子集本身又是一棵符合本定義的樹，稱為根合本定義的樹，稱為根root的子樹。的子樹?；静僮鳎夯静僮鳎翰檎遥翰檎遥?Root(T); V

3、alue(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( );6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 46.1 6.1 樹的類型定義樹的類型定義插入：插入： InitTree(&T); CreateTree(&T, definition); Assign(T, cur_e, val

4、ue); InsertChild(&T, &p, i, c);刪除：刪除： ClearTree(&T); DestroyTree(&T); DeleteChild(&T, &p, i); DestroyTree(&T);6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 56.1 6.1 樹的類型定義樹的類型定義和線性結(jié)構(gòu)的比較和線性結(jié)構(gòu)的比較 線性結(jié)構(gòu)線性結(jié)構(gòu) 樹結(jié)構(gòu)樹結(jié)構(gòu)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素(無前驅(qū)無前驅(qū))； 根結(jié)點(diǎn)

5、根結(jié)點(diǎn)(無前驅(qū)無前驅(qū))；最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素(無后繼無后繼)； 多個葉子結(jié)點(diǎn)多個葉子結(jié)點(diǎn)(無后繼無后繼)；其它數(shù)據(jù)元素其它數(shù)據(jù)元素 樹中其它結(jié)點(diǎn)樹中其它結(jié)點(diǎn)(一個前驅(qū)、一個后繼一個前驅(qū)、一個后繼) 。 (一個前驅(qū)、多個后繼一個前驅(qū)、多個后繼)。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 6ABCDEFGHIJKLM樹形表示樹形表示A (B (E (K, L), F), C(G ), D( H( M), I, J)嵌套括號表示法嵌套括號表示法樹的表示方法：樹的表示方

6、法： I JFKLGMCCDBEA文氏圖文氏圖凹入表凹入表ABFEKLCDHIGMJ6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 7基本術(shù)語基本術(shù)語結(jié)點(diǎn)結(jié)點(diǎn): 數(shù)據(jù)元素數(shù)據(jù)元素 + 若干指向子樹的分支。若干指向子樹的分支。結(jié)點(diǎn)的度結(jié)點(diǎn)的度: 分支的個數(shù)。分支的個數(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é)

7、點(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)所在的最大層次。 森林：森林：是是m（m0）棵互不相交的樹的集合任何一棵）棵互不相交的樹的集合任何一棵非空樹是一個二元組非空樹是一個二元組Tree = （root，F(xiàn)）其中：其中：root被稱為根結(jié)

8、點(diǎn)，被稱為根結(jié)點(diǎn)，F(xiàn)被稱為子樹森林。被稱為子樹森林。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 86.2 6.2 二叉樹的類型定義二叉樹的類型定義二叉樹的定義二叉樹的定義定義：定義：二叉樹是由二叉樹是由n(n=0)個結(jié)點(diǎn)的有限集合構(gòu)個結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點(diǎn)及兩棵互成，此集合或者為空集，或者由一個根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。不相交的左右子樹組成，并且左右子樹都是二叉樹。與樹的關(guān)系：與樹的關(guān)系：這也是一個遞歸定義。這

9、也是一個遞歸定義。區(qū)別區(qū)別： 二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。子樹，還是右子樹。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 9(a)空二叉樹空二叉樹A (b)根和空的根和空的左右子樹左右子樹AB (c)根和左子樹根和左子樹二叉樹的二叉樹的5 5種基本形態(tài)種基本形態(tài)A(d)根和右子樹根和右子樹BA (e)根和左右子樹根和左右子樹BC6.1

10、 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 10二叉樹的主要基本操作：二叉樹的主要基本操作：查找：查找： Root(T); Value(T, e);Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, V

11、isit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();插入：插入： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);刪除：刪除： ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR); 6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍

12、歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 11性質(zhì)性質(zhì)1： 在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個結(jié)點(diǎn)個結(jié)點(diǎn)(i=1)。 證明：證明：采用歸納法證明此性質(zhì)。采用歸納法證明此性質(zhì)。當(dāng)當(dāng)i=1時，只有一個根結(jié)點(diǎn)，時，只有一個根結(jié)點(diǎn)，2i-1=20 =1,命題成立。命題成立。現(xiàn)在假定第現(xiàn)在假定第i1層上命題成立，則第層上命題成立，則第i1層上至層上至多有多有2i-2個結(jié)點(diǎn)。由于二叉樹每個結(jié)點(diǎn)的度最大為個結(jié)點(diǎn)。由于二叉樹每個結(jié)點(diǎn)的度最大為2，故在第故在第i層上最大結(jié)點(diǎn)數(shù)為第層上最大結(jié)點(diǎn)數(shù)為第i1層上最大結(jié)點(diǎn)數(shù)的二層上最大結(jié)點(diǎn)數(shù)的二倍，倍， 即即22i-2

13、2i-1。命題得到證明。命題得到證明。二叉樹的重要特性：二叉樹的重要特性：6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 12性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k1個結(jié)點(diǎn)（個結(jié)點(diǎn)（k=1).證明：證明：深度為深度為k的二叉樹的最大的結(jié)點(diǎn)時為二叉的二叉樹的最大的結(jié)點(diǎn)時為二叉樹中每層上的最大結(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ù)）二叉樹的重要特性：二

14、叉樹的重要特性：12k1i1i2k6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 13二叉樹的重要特性：二叉樹的重要特性：性質(zhì)性質(zhì)3： 對任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為對任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則則n0n21。證明：證明：設(shè)二叉樹中度為設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)點(diǎn)，二叉樹中總結(jié)點(diǎn)數(shù)為數(shù)為N，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)均小于或等于，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)均小于或等于2，所以有：，所以有：Nn0n1n2 （1

15、） 再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個進(jìn)入分支，設(shè)有一個進(jìn)入分支，設(shè)B為二叉樹中的分支總數(shù)，為二叉樹中的分支總數(shù)， 則有：則有：NB1。由于這些分支都是由度為。由于這些分支都是由度為1和和2的結(jié)點(diǎn)射出的，的結(jié)點(diǎn)射出的，所以有：所以有：Bn1+2*n2 NB1n12n21 （2)由式（由式（1）和（）和（2）得到：）得到： n0+n1+n2=n1+2*n2+1 n0n216.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 14

16、滿二叉樹滿二叉樹2453671123456(a)完全二叉樹完全二叉樹123457(b)非完全二叉樹非完全二叉樹12367( c)非完全二叉樹非完全二叉樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 15兩種特殊形態(tài)的二叉樹：兩種特殊形態(tài)的二叉樹： 一棵深度為一棵深度為k且由且由2k-1個結(jié)點(diǎn)的二叉樹稱為個結(jié)點(diǎn)的二叉樹稱為滿二叉樹滿二叉樹。如果深度為如果深度為k、由、由n個結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)能夠與個結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)能夠與深度為深度為k的順序編號的滿二叉樹從的順序編號的滿二叉

17、樹從1到到n標(biāo)號的結(jié)點(diǎn)相對標(biāo)號的結(jié)點(diǎn)相對應(yīng)，則稱這樣的二叉樹為應(yīng)，則稱這樣的二叉樹為完全二叉樹完全二叉樹。完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn)是：是：（1）所有的葉結(jié)點(diǎn)都出現(xiàn)在第）所有的葉結(jié)點(diǎn)都出現(xiàn)在第k層或?qū)踊騥1層。層。（2）對任一結(jié)點(diǎn)，如果其右子樹的最大層次為）對任一結(jié)點(diǎn)，如果其右子樹的最大層次為h，則其左子樹的最大層次為則其左子樹的最大層次為h或或h1。滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 16 性質(zhì)性質(zhì)4：具有：具有n個結(jié)點(diǎn)

18、的完全二叉樹的深度為個結(jié)點(diǎn)的完全二叉樹的深度為log2n1。符號符號x表示不大于表示不大于x的最大整數(shù)。的最大整數(shù)。 證明：證明：假設(shè)此二叉樹的深度為假設(shè)此二叉樹的深度為k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2及完全及完全二叉樹的定義得到：二叉樹的定義得到：2k-11n=2k-1 或或 2k-1=n2k取對數(shù)得到：取對數(shù)得到：k1log2nk 因?yàn)橐驗(yàn)閗是整數(shù)。所以有：是整數(shù)。所以有：klog2n1。二叉樹的重要特性二叉樹的重要特性6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 17性質(zhì)性質(zhì)

19、5： 如果對一棵有如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號（從第層序編號（從第1層到第層到第log2n+1層，每層從左到右層，每層從左到右),則則對任一結(jié)點(diǎn)對任一結(jié)點(diǎn)i（1=i1，則其雙親是結(jié)點(diǎn)，則其雙親是結(jié)點(diǎn)i/2。 （2）如果）如果2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子是結(jié)點(diǎn)則，其左孩子是結(jié)點(diǎn)2i。 （3）如果）如果2i1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無右孩子；否則，其右孩無右孩子；否則，其右孩子是結(jié)點(diǎn)子是結(jié)點(diǎn)2i1。證明：略！證明：略！完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn): :6.1 樹的類型定義 6.2 二叉樹的類型定義

20、 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 186.3 6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)它是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。它是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。因此，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個恰當(dāng)?shù)男蛞虼?，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個恰當(dāng)?shù)男蛄校Y(jié)點(diǎn)在這個序列中的相互位置能反映出結(jié)點(diǎn)之間的列，結(jié)點(diǎn)在這個序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系，用編號的方法：邏輯關(guān)系，用編號的方法： #define max-tree-size 100Typedef t

21、elemtype sqbitreemax-tree-size;Sqbitree bt 從樹根起，自上層至下層，每層自左至右的給所有從樹根起，自上層至下層，每層自左至右的給所有結(jié)點(diǎn)編號。結(jié)點(diǎn)編號。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 19LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12完全二叉樹完全二叉樹ABCDEFGHIJKL6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹

22、6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 20ABCDEFG 表示該處沒有元素表示該處沒有元素存在僅僅為了好理解存在僅僅為了好理解ABCDEFG一般二叉樹一般二叉樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 211.1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)缺點(diǎn)：缺點(diǎn)：有可能對存儲空間造成極大的浪費(fèi)，在最有可能對存儲空間造成極大的浪費(fèi)，在最壞的情況下，一個深度為壞的情況下，一個深度為H且只有且只有H個結(jié)點(diǎn)的個結(jié)點(diǎn)的右單支樹右單支樹確需要確需要2h-1個結(jié)點(diǎn)存儲空間。而且，若經(jīng)常需要插

23、入與個結(jié)點(diǎn)存儲空間。而且，若經(jīng)常需要插入與刪除樹中結(jié)點(diǎn)時，順序存儲方式不是很好！刪除樹中結(jié)點(diǎn)時，順序存儲方式不是很好！6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 221.1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(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- - - -6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.

24、4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 23lchildDatarchildABCDEFGH（2 2）二叉鏈表法）二叉鏈表法ABCDEFGH6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 24Typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;2 2）二叉鏈表法）二叉鏈表法二叉樹的二叉鏈表存儲表示二叉樹的二叉鏈表存

25、儲表示6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 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); CreateBiTree(Trchildd); return OK;

26、 6.3 6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)的算法：鏈?zhǔn)酱鎯Y(jié)構(gòu)的算法：6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 26三叉鏈表法三叉鏈表法ABCDEFGHDBCEFGHArchildparentdatalchild6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 27Typedef struct TBiTNode TelemType data;

27、 struct TBiTNode *lchild,*rchild,*parent; BiTNode,*BiTree;三叉鏈表法三叉鏈表法二叉樹的三叉鏈表存儲表示二叉樹的三叉鏈表存儲表示6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 286.4 6.4 二叉樹的遍歷二叉樹的遍歷一、問題的提出一、問題的提出順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次?！霸L問訪問”的含

28、義可以很廣，如：輸出結(jié)點(diǎn)的信息的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。等。 對對“二叉樹二叉樹”而言，可以有三條搜索路徑：而言，可以有三條搜索路徑：1先上后下的按層次遍歷；先上后下的按層次遍歷；2先左（子樹）后右（子樹）的遍歷；先左（子樹）后右（子樹）的遍歷；3先右（子樹）后左（子樹）的遍歷。先右（子樹）后左（子樹）的遍歷。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 296.4 6.4 二叉樹的遍歷二叉樹的遍歷二、先左后右的遍歷算法二、先左后右的遍歷算法 先（根）序的遍歷算法：

29、先（根）序的遍歷算法：若二叉樹為空樹，則空操作；若二叉樹為空樹，則空操作；否則，（否則，（1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；）先序遍歷左子樹；（3）先序遍歷右子樹。）先序遍歷右子樹。中（根）序的遍歷算法：中（根）序的遍歷算法：若二叉樹為空樹若二叉樹為空樹,則空操作；則空操作；否則否則, （1）中序遍歷左子樹；）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。）中序遍歷右子樹。后（根）序的遍歷算法：后（根）序的遍歷算法：若二叉樹為空樹若二叉樹為空樹,則空操作則空操作;否則否則,（1）后序遍歷左子樹；）后序遍歷左子樹； （2）后序遍歷右子樹；）后序遍歷右子樹

30、； （3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。 6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 306.4 6.4 二叉樹的遍歷二叉樹的遍歷示例示例/-abcd圖圖1 (a-b)/(c+d)gbcafed 圖圖2gbcafed圖圖3先序：先序：/-ab+cd中序：中序：a-b/c+d后序：后序：ab-cd+/先序：先序：faegbcd中序：中序：afbgced后序：后序：abcgdef先序：先序：efagbcd中序：中序：afbgced后序：后序：abcgfde分別稱為表達(dá)式的前綴表示法、

31、中綴表示法和后綴表示分別稱為表達(dá)式的前綴表示法、中綴表示法和后綴表示法（逆波蘭表示法）。法（逆波蘭表示法）。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 316.4 6.4 二叉樹的遍歷二叉樹的遍歷三、算法的遞歸描述三、算法的遞歸描述 void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍歷二叉樹先序遍歷二叉樹 if (T) visit(T-data）; / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)Preorder(T-lchild

32、, visit); / 遍歷左子樹遍歷左子樹Preorder(T-rchild, visit); / 遍歷右子樹遍歷右子樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 32void InOrderTraverse (BiTree T, void( *visit)(TElemType &e)/中序遍歷中序遍歷if(T)InOrderTraverse (T-lchild, visit); visit(T-data）; / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)InOrderTraverse (T

33、-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)6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 33四、先序遍歷算法的非遞歸描述四、先序遍歷算法的

34、非遞歸描述先序遍歷的非遞歸算法。先序遍歷的非遞歸算法。t指向根，指向根，p為指針，指為指針，指向當(dāng)前結(jié)點(diǎn)。使用一個堆棧向當(dāng)前結(jié)點(diǎn)。使用一個堆棧s（），（），top為棧指針為棧指針 1 if t=NULL 2 then 輸出輸出 這是一棵空樹這是一棵空樹 3 else p=t，top=0 4 DO 5 while p！=NULL 6 輸出輸出 data（p）; 7 top+;8 if topn9 then 調(diào)用調(diào)用 棧滿棧滿 10 else stop=p，p=lchild（p）11 if top！=012 p=stop; top-; p=rchild（p）13while( top=0 &

35、 p=null)算法結(jié)束算法結(jié)束6.4 6.4 二叉樹的遍歷二叉樹的遍歷四、先序遍歷算法的非遞歸描述四、先序遍歷算法的非遞歸描述1 if t=NULL2 then 輸出輸出 這是一棵空樹這是一棵空樹 3 else p=t，top=0 4 DO 5 while p！=NULL 6 輸出輸出 data（p）;7 top+;8 if topn9 then 調(diào)用調(diào)用 棧滿棧滿10 else stop=p，p=lchild（p）11 if top！=012 p=stop; top-; p=rchild（p）13while( top=0 & p=null)算法結(jié)束算法結(jié)束注注:結(jié)點(diǎn)旁結(jié)點(diǎn)旁的數(shù)字是

36、的數(shù)字是該結(jié)點(diǎn)的該結(jié)點(diǎn)的存儲地址存儲地址二叉樹執(zhí)行先序遍歷二叉樹執(zhí)行先序遍歷算法的過程算法的過程棧棧6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 35中序遍歷的非遞歸算法中序遍歷的非遞歸算法中序遍歷的非遞歸算法，使用堆棧中序遍歷的非遞歸算法，使用堆棧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)用 棧滿

37、棧滿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-10 輸出輸出 data(p) 11 plchild)& (!T-rchild)count+;CountLeaf( T-lchild, count); / 統(tǒng)計左子樹中葉子結(jié)點(diǎn)個數(shù)統(tǒng)計左子樹中葉子結(jié)點(diǎn)個數(shù)CountLeaf( T-rchild, count);/ 統(tǒng)計右子樹中葉子結(jié)點(diǎn)個

38、數(shù)統(tǒng)計右子樹中葉子結(jié)點(diǎn)個數(shù)6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 38五、遍歷算法的應(yīng)用舉例五、遍歷算法的應(yīng)用舉例2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild );depthRight= Depth( T-rchild );depthval = 1+(depthLeft depthRight? depthLe

39、ft:depthRight); return depthval; 6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 39五、遍歷算法的應(yīng)用舉例五、遍歷算法的應(yīng)用舉例3、復(fù)制二叉樹、復(fù)制二叉樹(后序遍歷后序遍歷)/ 生成一個二叉樹的結(jié)點(diǎn)生成一個二叉樹的結(jié)點(diǎn)BiTNode *GetTreeNode(TElemType item,BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode)exit(1

40、); T- data = item; T- lchild = lptr； T- rchild = rptr; return T;6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 40五、遍歷算法的應(yīng)用舉例五、遍歷算法的應(yīng)用舉例3、復(fù)制二叉樹、復(fù)制二叉樹(后序遍歷后序遍歷)BiTNode *CopyTree(BiTNode *T) if (!T )return NULL;if (T-lchild ) newlptr = CopyTree(T-lchild);else newlptr

41、= NULL;if (T-rchild ) newrptr = CopyTree(T-rchild);else newrptr = NULL;newnode = GetTreeNode(T-data, newlptr, newrptr);return newnode;6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 416.5 6.5 線索二叉樹線索二叉樹一、何謂線索二叉樹？一、何謂線索二叉樹？遍歷二叉樹是按一定的規(guī)則將二叉樹中結(jié)點(diǎn)排列成遍歷二叉樹是按一定的規(guī)則將二叉樹中結(jié)點(diǎn)排列成

42、一個線性序列；這實(shí)際上是把一個非線性結(jié)構(gòu)進(jìn)行線性一個線性序列；這實(shí)際上是把一個非線性結(jié)構(gòu)進(jìn)行線性化的操作?；牟僮?。以二叉鏈表作為存儲結(jié)構(gòu)時，對于某個結(jié)點(diǎn)只能找以二叉鏈表作為存儲結(jié)構(gòu)時，對于某個結(jié)點(diǎn)只能找到其左右孩子，而不能直接得到結(jié)點(diǎn)在任一序列中的前到其左右孩子，而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)或后繼。要想得到只能通過遍歷的動態(tài)過程才行。驅(qū)或后繼。要想得到只能通過遍歷的動態(tài)過程才行。怎樣保存遍歷過程中得到的信息呢？怎樣保存遍歷過程中得到的信息呢？（1增加兩個指針增加兩個指針（2利用結(jié)構(gòu)中的空鏈域，并設(shè)立標(biāo)志。即采用如利用結(jié)構(gòu)中的空鏈域，并設(shè)立標(biāo)志。即采用如下的形式：下的形式：lchild

43、 ltagdatartagrchild6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 426.5 6.5 線索二叉樹線索二叉樹何謂線索二叉樹？何謂線索二叉樹？ 指向該線性序列中的指向該線性序列中的“前驅(qū)前驅(qū)”和和“后繼后繼”的的指針指針，稱，稱作作“線索線索”。包含。包含“線索線索”的存儲結(jié)構(gòu)，稱作的存儲結(jié)構(gòu)，稱作“線索鏈線索鏈表表”；與其相應(yīng)的二叉樹，稱作；與其相應(yīng)的二叉樹，稱作“線索二叉樹線索二叉樹”。對線索鏈表中結(jié)點(diǎn)的約定：對線索鏈表中結(jié)點(diǎn)的約定：在二叉鏈表的結(jié)點(diǎn)中增加兩個

44、標(biāo)志域，并作如下規(guī)定：在二叉鏈表的結(jié)點(diǎn)中增加兩個標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則若該結(jié)點(diǎn)的左子樹不空，則lchild域的指針指向其域的指針指向其左子左子樹樹，且左標(biāo)志域，且左標(biāo)志域 ltag的值為的值為0； 否則，否則，lchild域的指針指向其域的指針指向其“前驅(qū)前驅(qū)”，且左標(biāo)志，且左標(biāo)志ltag的值的值為為1。若該結(jié)點(diǎn)的右子樹不空，則若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右域的指針指向其右子樹，且右標(biāo)志域子樹，且右標(biāo)志域rtag的值為的值為0；否則，否則，rchild域的指針指向其域的指針指向其“后繼后繼”，且右標(biāo)志，且右標(biāo)志rtag的值為的值為1。 6.1 樹的

45、類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 436.5 6.5 線索二叉樹線索二叉樹0 A 01B 00D 1 1C 11E 1TADBEC中序序列：中序序列：BCAED6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 446.5 6.5 線索二叉樹線索二叉樹線索鏈表的結(jié)構(gòu)描述：線索鏈表的結(jié)構(gòu)描述：typedef enum Link, Thread PointerThr; /

46、 Link=0:指針，指針，Thread=1:線索線索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild, *rchild; / 左右指針左右指針PointerThr LTag, RTag; / 左右標(biāo)志左右標(biāo)志 BiThrNode, *BiThrTree;6.5 6.5 線索二叉樹線索二叉樹找結(jié)點(diǎn)的后繼找結(jié)點(diǎn)的后繼線索化線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做過程叫做線索化線索化。下面以下面以中序中序?yàn)槔纯慈绾卧诰€索二叉樹中為例看看如何在線索二叉樹中找結(jié)

47、點(diǎn)的后繼找結(jié)點(diǎn)的后繼。（1樹中所有葉子結(jié)點(diǎn)和只有左子樹的右指針均為線索，樹中所有葉子結(jié)點(diǎn)和只有左子樹的右指針均為線索，直接指示了結(jié)點(diǎn)的后繼；直接指示了結(jié)點(diǎn)的后繼；（2其他非終端結(jié)點(diǎn)的右鏈均為指針，無法得到后繼的信其他非終端結(jié)點(diǎn)的右鏈均為指針，無法得到后繼的信息。然而根據(jù)中序遍歷的規(guī)律可知，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右息。然而根據(jù)中序遍歷的規(guī)律可知，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右子樹時訪問的第一個結(jié)點(diǎn)，即右子樹中最左下的結(jié)點(diǎn)。子樹時訪問的第一個結(jié)點(diǎn)，即右子樹中最左下的結(jié)點(diǎn)。（3反之，在中序線索樹中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若左標(biāo)反之，在中序線索樹中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若左標(biāo)志是志是1，則左鏈為線索，指示其前驅(qū)；否則

48、，遍歷該結(jié)點(diǎn)的左子，則左鏈為線索，指示其前驅(qū)；否則，遍歷該結(jié)點(diǎn)的左子樹時最后訪問的結(jié)點(diǎn)（左子樹中最右下的結(jié)點(diǎn)為其前驅(qū)樹時最后訪問的結(jié)點(diǎn)（左子樹中最右下的結(jié)點(diǎn)為其前驅(qū))。ABCEIDHF GGKnullnull6.5 6.5 線索二叉樹線索二叉樹找結(jié)點(diǎn)的后繼找結(jié)點(diǎn)的后繼在在后序線索樹后序線索樹中找結(jié)點(diǎn)中找結(jié)點(diǎn)x的后繼較復(fù)雜，可分三種情況：的后繼較復(fù)雜，可分三種情況：（1若結(jié)點(diǎn)若結(jié)點(diǎn)x是二叉樹的根是二叉樹的根,則其后繼為空則其后繼為空;（2若結(jié)點(diǎn)若結(jié)點(diǎn)x是其雙親的右孩子或是左孩子且其雙親沒有是其雙親的右孩子或是左孩子且其雙親沒有右子樹右子樹,則其后繼即為雙親結(jié)點(diǎn)。則其后繼即為雙親結(jié)點(diǎn)。（3若結(jié)點(diǎn)若

49、結(jié)點(diǎn)x是其雙親的左孩子，且其雙親有右子樹，則是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親的右子樹上按后序遍歷出的第一個結(jié)點(diǎn)。其后繼為雙親的右子樹上按后序遍歷出的第一個結(jié)點(diǎn)。由此可見，在后序線索化樹上找后繼時需知道結(jié)點(diǎn)的雙親，由此可見，在后序線索化樹上找后繼時需知道結(jié)點(diǎn)的雙親，因此需要使用三叉鏈表。因此需要使用三叉鏈表?？梢?，在中序線索二叉樹上遍歷二叉樹，雖然時間復(fù)雜度可見，在中序線索二叉樹上遍歷二叉樹，雖然時間復(fù)雜度也是也是O(n)，但常數(shù)因子小，且不需要設(shè)棧，因此若在某程序中，但常數(shù)因子小，且不需要設(shè)棧，因此若在某程序中需要經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼，需要經(jīng)常遍

50、歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼，則應(yīng)采用線索鏈表作存儲結(jié)構(gòu)。則應(yīng)采用線索鏈表作存儲結(jié)構(gòu)。ABCEIDHF GGKnull6.5 6.5 線索二叉樹線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法:for ( p = firstNode(T); p; p = Succ(p) )Visit(p);中序線索化鏈表的遍歷算法中序線索化鏈表的遍歷算法:中序遍歷的第一個結(jié)點(diǎn)中序遍歷的第一個結(jié)點(diǎn) ？在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？ABCEIDHF GGKnullnull6.5 6.5 線索二叉樹線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法:Statu

51、s 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)的右鏈rchild， 指向指向中序遍歷的最后一個結(jié)點(diǎn)。中序遍歷二叉線索鏈表表示的中序遍歷的最后一個結(jié)點(diǎn)。中序遍歷二叉線索鏈表表示的二叉樹，對每個數(shù)據(jù)元素調(diào)用函數(shù)二叉樹，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。p = T-lchild; / p指向根結(jié)點(diǎn)指向根結(jié)點(diǎn)while (p != T) / 空樹或遍歷結(jié)束時，空樹或遍歷結(jié)束時，p=T while (p-LTag=L

52、ink) p = p-lchild; if (!Visit(p-data) return ERROR;/ 訪問其左訪問其左子樹為空的結(jié)點(diǎn)子樹為空的結(jié)點(diǎn) while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結(jié)點(diǎn)訪問后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根進(jìn)至其右子樹根 return OK; / InOrderTraverse_ThrT-+/*-abe fc d6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6

53、樹和森林 6.7 哈夫曼樹與哈夫曼編碼 496.5 6.5 線索二叉樹線索二叉樹三、如何建立線索鏈表？三、如何建立線索鏈表？在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)前驅(qū)”和和“后繼后繼”信息。信息。遍歷過程中，附設(shè)指針遍歷過程中，附設(shè)指針pre,并始終保持指針并始終保持指針pre指向當(dāng)前訪問的、指針指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。所指結(jié)點(diǎn)的前驅(qū)。6.5 6.5 線索二叉樹線索二叉樹三、如何建立線索鏈表？三、如何建立線索鏈表？Status InOrderThreading(BiThrTree &T

54、hrt, 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; / 右指針回指右指針回指if (!T) Thrt-lchild = Thrt; / 若二叉樹空，則左指針回指若二叉樹空，則左指針回指else Thrt-lchild = T; pre = Thrt

55、;InThreading(T); / 中序遍歷進(jìn)行中序線索化中序遍歷進(jìn)行中序線索化pre-rchild = Thrt; pre-RTag = Thread; / 最后一個結(jié)點(diǎn)線索化最后一個結(jié)點(diǎn)線索化Thrt-rchild = pre; return OK; / InOrderThreadingvoid InThreading(BiThrTree p) if (p) InThreading(p-lchild); / 左子樹線索化左子樹線索化if (!p-lchild) p-LTag = Thread; p-lchild = pre; / 建前驅(qū)線索建前驅(qū)線索if (!pre-rchild) pr

56、e-RTag = Thread; pre-rchild = p; / 建后繼線索建后繼線索pre = p; / 保持保持pre指向指向p的前驅(qū)的前驅(qū)InThreading(p-rchild); / 右子樹線索化右子樹線索化 / InThreading6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 526.6 6.6 樹和森林樹和森林一、樹的三種存儲結(jié)構(gòu)一、樹的三種存儲結(jié)構(gòu)1. 雙親表示法雙親表示法:在這種表示中，容易找到父結(jié)點(diǎn)及其所有的祖先；在這種表示中，容易找到父結(jié)點(diǎn)及其所有的

57、祖先；也能找到結(jié)點(diǎn)的子女和兄弟（雖然比較麻煩）。但它沒有也能找到結(jié)點(diǎn)的子女和兄弟（雖然比較麻煩）。但它沒有表示出結(jié)點(diǎn)之間的左右次序，所以表示出結(jié)點(diǎn)之間的左右次序，所以無法求樹中某個指定結(jié)無法求樹中某個指定結(jié)點(diǎn)的最左子結(jié)點(diǎn)和右兄弟結(jié)點(diǎn)等基本運(yùn)算點(diǎn)的最左子結(jié)點(diǎn)和右兄弟結(jié)點(diǎn)等基本運(yùn)算。ABCDEFGHIJKLM8M5L5K4J4I4H3G2F2E1D1C1B-1A123456789101112136.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 53一、一、樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)

58、構(gòu)1. 雙親表示法雙親表示法:用一組連續(xù)空間存儲樹的結(jié)點(diǎn)，并附設(shè)一個指用一組連續(xù)空間存儲樹的結(jié)點(diǎn)，并附設(shè)一個指示器指示其雙親結(jié)點(diǎn)的位置。結(jié)構(gòu)類型如下：示器指示其雙親結(jié)點(diǎn)的位置。結(jié)構(gòu)類型如下：#define MAX_TREE_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):typedef struct PTNode /* 樹中結(jié)點(diǎn)結(jié)構(gòu)樹中結(jié)點(diǎn)結(jié)構(gòu) */Elem data; /* 結(jié)點(diǎn)中的元素結(jié)點(diǎn)中的元素 */int parent; / 雙親位置域雙親位置域 PTNode;樹結(jié)構(gòu)樹結(jié)構(gòu):typedef struct PTNode nodesMAX_TREE_SIZE;int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個

59、數(shù)根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個數(shù) PTree一、樹的三種存儲結(jié)構(gòu)一、樹的三種存儲結(jié)構(gòu)2. 孩子鏈表表示法孩子鏈表表示法:ABCDEFGHIJKLMMLKJIHGFEDCBA12345678910111213234 56 13 78910 1112 6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 55一、樹的三種存儲結(jié)構(gòu)一、樹的三種存儲結(jié)構(gòu)2、孩子鏈表表示法、孩子鏈表表示法:結(jié)點(diǎn)表中的每一元素又包含一個子表，存放該結(jié)點(diǎn)結(jié)點(diǎn)表中的每一元素又包含一個子表，存放該結(jié)點(diǎn)的所有子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放

60、，子表用鏈接表示，子的所有子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放，子表用鏈接表示，子表中的元素按從左到右的次序存放。結(jié)構(gòu)類型如下：表中的元素按從左到右的次序存放。結(jié)構(gòu)類型如下：雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu)typedef struct Elem data;ChildPtr firstchild; / 孩子鏈的頭指針孩子鏈的頭指針 CTBox;樹結(jié)構(gòu)樹結(jié)構(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)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu):typedef struct CTNode int child;struct CTNode *next; *ChildPtr;6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結(jié)構(gòu) 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.