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

2、與哈夫曼編碼 36.1 6.1 樹的類型定義樹的類型定義數據對象數據對象D：D是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。數據關系數據關系R： 若若D為空集，則稱為空樹；為空集，則稱為空樹； 否則否則:（1）在在D中存在唯一的稱為根的數據元素中存在唯一的稱為根的數據元素root,（2）當當n1時，其余結點可分為時，其余結點可分為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 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 56.1 6.1 樹的類型定義樹的類型定義和線性結構的比較和線性結構的比較 線性結構線性結構 樹結構樹結構第一個數據元素第一個數據元素(無前驅無前驅)； 根結點

5、根結點(無前驅無前驅)；最后一個數據元素最后一個數據元素(無后繼無后繼)； 多個葉子結點多個葉子結點(無后繼無后繼)；其它數據元素其它數據元素 樹中其它結點樹中其它結點(一個前驅、一個后繼一個前驅、一個后繼) 。 (一個前驅、多個后繼一個前驅、多個后繼)。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 7基本術語基本術語結點結點: 數據元素數據元素 + 若干指向子樹的分支。若干指向子樹的分支。結點的度結點的度: 分支的個數。分支的個數。樹的度樹的度: 樹中所有結點的度的最大值。樹中所有結點的度的最大值。葉子結點葉子結點: 度為零的結點。度為零的結點。分支結點分支結點: 度大于零的結點；度大于零的結點； 路徑路徑和和路徑長度路徑長度。孩子孩子結點、結

7、點、雙親雙親結點、結點、兄弟兄弟結點、堂兄弟、結點、堂兄弟、祖先祖先結點、結點、子孫子孫結點。結點。邊邊：雙親節點：雙親節點x到子結點到子結點y的有序對的有序對(x，y)。結點的層次結點的層次: 假設根結點的層次為假設根結點的層次為1，第，第i 層的結點的層的結點的子樹根結點的層次為子樹根結點的層次為i+1。規定根的層數為規定根的層數為0。樹的深度：樹的深度：樹中葉子結點所在的最大層次。樹中葉子結點所在的最大層次。 森林：森林：是是m（m0）棵互不相交的樹的集合任何一棵）棵互不相交的樹的集合任何一棵非空樹是一個二元組非空樹是一個二元組Tree = （root，F）其中：其中：root被稱為根結

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

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

10、 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍

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

13、2i-1。命題得到證明。命題得到證明。二叉樹的重要特性：二叉樹的重要特性：6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 12性質性質2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k1個結點（個結點（k=1).證明：證明：深度為深度為k的二叉樹的最大的結點時為二叉的二叉樹的最大的結點時為二叉樹中每層上的最大結點數之和，由性質樹中每層上的最大結點數之和，由性質1得到每層上的得到每層上的最大結點數最大結點數2i-1（第（第i層上的最大結點數）層上的最大結點數）二叉樹的重要特性：二

14、叉樹的重要特性：12k1i1i2k6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 13二叉樹的重要特性：二叉樹的重要特性：性質性質3： 對任何一棵二叉樹，如果其終端結點數為對任何一棵二叉樹，如果其終端結點數為n0，度為度為2的結點數為的結點數為n2，則則n0n21。證明：證明：設二叉樹中度為設二叉樹中度為1的結點數為的結點數為n1，二叉樹中總結點，二叉樹中總結點數為數為N，因為二叉樹中所有結點均小于或等于，因為二叉樹中所有結點均小于或等于2，所以有：，所以有：Nn0n1n2 （1

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

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

17、樹從1到到n標號的結點相對標號的結點相對應，則稱這樣的二叉樹為應，則稱這樣的二叉樹為完全二叉樹完全二叉樹。完全二叉樹的特點完全二叉樹的特點是：是：（1）所有的葉結點都出現在第）所有的葉結點都出現在第k層或層或k1層。層。（2）對任一結點，如果其右子樹的最大層次為）對任一結點，如果其右子樹的最大層次為h，則其左子樹的最大層次為則其左子樹的最大層次為h或或h1。滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 16 性質性質4：具有：具有n個結點

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

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

20、 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 186.3 6.3 二叉樹的存儲結構二叉樹的存儲結構1.順序存儲結構順序存儲結構它是用一組連續的存儲單元存儲二叉樹的數據元素。它是用一組連續的存儲單元存儲二叉樹的數據元素。因此，必須把二叉樹的所有結點安排成為一個恰當的序因此，必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法：邏輯關系，用編號的方法： #define max-tree-size 100Typedef t

21、elemtype sqbitreemax-tree-size;Sqbitree bt 從樹根起，自上層至下層，每層自左至右的給所有從樹根起，自上層至下層，每層自左至右的給所有結點編號。結點編號。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹

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

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

24、4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 23lchildDatarchildABCDEFGH（2 2）二叉鏈表法）二叉鏈表法ABCDEFGH6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 25Status CreateBiTree(BiTree *T) /*創建一棵二叉樹創建一棵二叉樹*/ 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 二叉樹的存儲結構二叉樹的存儲結構鏈式存儲結構的算法：鏈式存儲結構的算法：6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 26三叉鏈表法三叉鏈表法ABCDEFGHDBCEFGHArchildparentdatalchild6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 286.4 6.4 二叉樹的遍歷二叉樹的遍歷一、問題的提出一、問題的提出順著某一條搜索路徑巡訪二叉樹中的結點，使得每順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。個結點均被訪問一次，而且僅被訪問一次?！霸L問訪問”的含

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

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

30、； （3）訪問根結點。）訪問根結點。 6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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分別稱為表達式的前綴表示法、

31、中綴表示法和后綴表示分別稱為表達式的前綴表示法、中綴表示法和后綴表示法（逆波蘭表示法）。法（逆波蘭表示法）。6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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）; / 訪問結點訪問結點Preorder(T-lchild

32、, visit); / 遍歷左子樹遍歷左子樹Preorder(T-rchild, visit); / 遍歷右子樹遍歷右子樹6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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）; / 訪問結點訪問結點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）; / 訪問結點訪問結點6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 33四、先序遍歷算法的非遞歸描述四、先序遍歷算法的

34、非遞歸描述先序遍歷的非遞歸算法。先序遍歷的非遞歸算法。t指向根，指向根，p為指針，指為指針，指向當前結點。使用一個堆棧向當前結點。使用一個堆棧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 調用調用 棧滿棧滿 10 else stop=p，p=lchild（p）11 if top！=012 p=stop; top-; p=rchild（p）13while( top=0 &

35、 p=null)算法結束算法結束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 調用調用 棧滿棧滿10 else stop=p，p=lchild（p）11 if top！=012 p=stop; top-; p=rchild（p）13while( top=0 & p=null)算法結束算法結束注注:結點旁結點旁的數字是

36、的數字是該結點的該結點的存儲地址存儲地址二叉樹執行先序遍歷二叉樹執行先序遍歷算法的過程算法的過程棧棧6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 35中序遍歷的非遞歸算法中序遍歷的非遞歸算法中序遍歷的非遞歸算法，使用堆棧中序遍歷的非遞歸算法，使用堆棧s（），（），top為指針，為指針，t指向根，指向根，p為指針，指向當前結點為指針，指向當前結點1 top=0,p=t2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn )6 then 調用調用 棧滿

37、棧滿7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 輸出輸出 data(p) 11 pn )6 then 調用調用 棧滿棧滿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); / 統計左子樹中葉子結點個數統計左子樹中葉子結點個數CountLeaf( T-rchild, count);/ 統計右子樹中葉子結點個

38、數統計右子樹中葉子結點個數6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 38五、遍歷算法的應用舉例五、遍歷算法的應用舉例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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 39五、遍歷算法的應用舉例五、遍歷算法的應用舉例3、復制二叉樹、復制二叉樹(后序遍歷后序遍歷)/ 生成一個二叉樹的結點生成一個二叉樹的結點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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 40五、遍歷算法的應用舉例五、遍歷算法的應用舉例3、復制二叉樹、復制二叉樹(后序遍歷后序遍歷)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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 416.5 6.5 線索二叉樹線索二叉樹一、何謂線索二叉樹？一、何謂線索二叉樹？遍歷二叉樹是按一定的規則將二叉樹中結點排列成遍歷二叉樹是按一定的規則將二叉樹中結點排列成

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

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

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

45、類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 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 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.6 樹和森林 6.7 哈夫曼樹與哈夫曼編碼 446.5 6.5 線索二叉樹線索二叉樹線索鏈表的結構描述：線索鏈表的結構描述：typedef enum Link, Thread PointerThr; /

46、 Link=0:指針，指針，Thread=1:線索線索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild, *rchild; / 左右指針左右指針PointerThr LTag, RTag; / 左右標志左右標志 BiThrNode, *BiThrTree;6.5 6.5 線索二叉樹線索二叉樹找結點的后繼找結點的后繼線索化線索化：對二叉樹以某種次序遍歷使其變為線索二叉樹的：對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做過程叫做線索化線索化。下面以下面以中序中序為例看看如何在線索二叉樹中為例看看如何在線索二叉樹中找結

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

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

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

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

51、s InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) / T指向頭結點，頭指向頭結點，頭結點的左鏈結點的左鏈lchild指向根結點，頭結點的右鏈指向根結點，頭結點的右鏈rchild， 指向指向中序遍歷的最后一個結點。中序遍歷二叉線索鏈表表示的中序遍歷的最后一個結點。中序遍歷二叉線索鏈表表示的二叉樹，對每個數據元素調用函數二叉樹，對每個數據元素調用函數Visit。p = T-lchild; / p指向根結點指向根結點while (p != T) / 空樹或遍歷結束時，空樹或遍歷結束時，p=T while (p-LTag=L

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

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

54、hrt, BiThrTree T) / 中中序遍歷二叉樹序遍歷二叉樹T，并將其中序線索化，并將其中序線索化，Thrt指向頭結點。指向頭結點。if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW);Thrt-LTag = Link; Thrt-RTag =Thread; / 建頭結點建頭結點Thrt-rchild = Thrt; / 右指針回指右指針回指if (!T) Thrt-lchild = Thrt; / 若二叉樹空，則左指針回指若二叉樹空，則左指針回指else Thrt-lchild = T; pre = Thrt

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

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

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

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

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

60、，子表用鏈接表示，子的所有子結點。結點表順序存放，子表用鏈接表示，子表中的元素按從左到右的次序存放。結構類型如下：表中的元素按從左到右的次序存放。結構類型如下：雙親結點結構雙親結點結構typedef struct Elem data;ChildPtr firstchild; / 孩子鏈的頭指針孩子鏈的頭指針 CTBox;樹結構樹結構:typedef struct CTBox nodesMAX_TREE_SIZE;int n, r; / 結點數和根結點的位置結點數和根結點的位置 CTree;孩子結點結構孩子結點結構:typedef struct CTNode int child;struct CTNode *next; *ChildPtr;6.1 樹的類型定義 6.2 二叉樹的類型定義 6.3 二叉樹的存儲結構 6.4 二叉樹的遍歷 6.5 線索二叉樹 6.