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

1、第六章第六章樹和二叉樹樹和二叉樹6.1 樹的類型定義和基本術(shù)語樹的類型定義和基本術(shù)語6.2 6.2 二叉樹二叉樹6.3遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹*6.5樹與等價問題樹與等價問題6.4 樹和森林樹和森林6.6 哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼6.1 樹的類型定義樹的類型定義和基本術(shù)語和基本術(shù)語6.1.1 樹的類型定義樹的類型定義數(shù)據(jù)對象數(shù)據(jù)對象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n

2、1時，其余結(jié)點可分為時，其余結(jié)點可分為m (m0)個互個互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R： 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類 Root(T) / 求樹的根結(jié)點求樹的根結(jié)點 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點的元素值求當(dāng)前結(jié)點的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點的雙親結(jié)點求當(dāng)前結(jié)點的雙親結(jié)點LeftChild(T, cur_e) / 求當(dāng)

3、前結(jié)點的最左孩子求當(dāng)前結(jié)點的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點的右兄弟求當(dāng)前結(jié)點的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點賦值給當(dāng)前結(jié)點賦值InsertChild(&T, &am

4、p;p, i, c) / 將以將以c為根的樹插入為結(jié)點為根的樹插入為結(jié)點p的第的第i棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點刪除結(jié)點p的第的第i棵子樹棵子樹ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根例如例如: :() 有確定的根；() 樹根和子樹根之間為有向關(guān)系。有向樹：有向樹：有序樹：有序樹：子樹之間存在確定的次序關(guān)系。先左后右無序

5、樹：無序樹：子樹之間不存在確定的次序關(guān)系。DHIJM對比對比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(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é)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點多個葉子結(jié)點 ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 一個后繼一個后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) )6.1.2 6.1.2 基基 本本 術(shù)術(shù) 語語結(jié)點結(jié)點: :結(jié)點的度結(jié)點的度: :樹的度樹的度: :葉子結(jié)點葉

6、子結(jié)點: :分支結(jié)點分支結(jié)點: :數(shù)據(jù)元素+ +若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM孩子孩子結(jié)點: 樹中一個結(jié)點的子樹的根結(jié)點。 雙親雙親結(jié)點: 若樹中某結(jié)點有孩子結(jié)點，則這個結(jié)點就稱作它的孩子結(jié)點的雙親結(jié)點。兄弟兄弟結(jié)點： 具有相同的雙親結(jié)點的結(jié)點 。堂兄弟： 其雙親在同一層的結(jié)點互為堂兄弟。祖先祖先結(jié)點： 從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。子孫子孫結(jié)點： 以某結(jié)點為根的子樹中的任何一個結(jié)點都稱為該結(jié)點的子孫。ABCDEFGHIJMKL結(jié)點的層次結(jié)點的層次: :樹的深度：樹的深度：假設(shè)根結(jié)點的層次為1，第l 層的結(jié)點的子樹根結(jié)點的層次為l+

7、1樹中葉子結(jié)點所在的最大層次(從根到結(jié)點的)路徑路徑：由從根根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成。ABCDEFGHIJMKL任何一棵非空樹是一個二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點 F 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF6.2 二叉樹二叉樹6.2.1 6.2.1 二叉樹二叉樹的類型定義的類型定義 二叉樹或為空樹空樹，或是由一個根結(jié)根結(jié)點點加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不相交的互不相交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹二叉樹的基本特征: 每個結(jié)點最多只有兩棵子樹（不存在度大于2

8、的結(jié)點）； 左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹； 即使樹中某個結(jié)點只有一個子樹，也要分清它是左子樹還是右子樹。BACEDFGBACEDFG二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點只含根結(jié)點NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹 二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e);

9、RightSibling(T, e); BiTreeEmpty(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(&am

10、p;T); DestroyBiTree(&T);DeleteChild(T, p, LR);刪刪 除除 類：類：6.2.2 二叉樹二叉樹的重要特性的重要特性 性質(zhì)性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i-1 個結(jié)點。 (i1)用歸納法證明用歸納法證明： 歸納的基礎(chǔ)歸納的基礎(chǔ)： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時，只有一個根結(jié)點： 2i-1 = 20 = 1；假設(shè)對所有的 j，1 j i，命題成立；二叉樹上每個結(jié)點至多有兩棵子樹，則第 i 層的結(jié)點數(shù) = 2i-2 2 = 2i-1 。性質(zhì)性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個結(jié)點（k1）。

11、證明：證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點數(shù)至多為 20+21+ +2k-1 = 2k-1 。S= 20+21+ +2k-1,2S=2*(20+21+ +2k-1)= 21+22 + +2k,2S-S= 2k-1 性質(zhì)性質(zhì) 3 ： 對任何一棵二叉樹，若它含有n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點，則必存在關(guān)系式：n0 = n2+1。證明：證明：設(shè)設(shè) 二叉樹上結(jié)點總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。根結(jié)點無前驅(qū)兩類兩類特殊特殊的二叉樹

12、：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個結(jié)點和滿二叉樹中編號編號為為 1 至至 n 的結(jié)點的結(jié)點一一對應(yīng)。123456789 10 11 12 13 14 15abcdefghij12345712367非完全二叉樹:對應(yīng)滿二叉樹編號有空缺的。完全二叉樹是滿二叉樹的一部分，滿二叉樹是完全二叉樹的特例(結(jié)點最多)。問題問題: :一個深度為一個深度為k k的完全二叉樹的完全二叉樹最多有多少個結(jié)點最多有多少個結(jié)點? ?最少有多少個結(jié)點最少有多少個結(jié)點? ?2k-12k-12k-1-1+1 性質(zhì)性質(zhì) 4 ： 具有 n 個結(jié)點的完全

13、二叉樹的深度深度為 log2n +1 。其中符號： x表示不大于x的最大整數(shù)。 x 表示不小于x的最小整數(shù)。證明：證明：設(shè)設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其左孩子左孩子結(jié)點；(3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為2i+1 的結(jié)點為其右孩子右孩子結(jié)點。舉例說明性質(zhì)5：1、當(dāng)i=1時，是根結(jié)點，無雙親； 當(dāng)i=71時,它的雙親是i/2 = 7/2 =3, 當(dāng)i=4時，雙親是i/2 4/2 =2；123456789 10 11 122、當(dāng)i=5時，2*5=10，小于總

14、結(jié)點數(shù)12，所以5的左孩子是10； 而結(jié)點7，2*7=1412所以沒有左孩子，是葉子結(jié)點。3、自己舉例證明。i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1圖 完全二叉樹中結(jié)點i和i+1(a)i和i+1結(jié)點在同一層 (b)i和i+1結(jié)點不在同一層下圖所示為完全二叉樹上結(jié)點及其左右結(jié)點編號之間的關(guān)系。6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)蕉⒍鏄涞逆準(zhǔn)?存儲表示存儲表示一、一、 二叉樹的順序二叉樹的順序 存儲表示存儲表示#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點數(shù)typedef TElemType SqB

15、iTreeMAX_ TREE_SIZE; / 0號單元存儲根結(jié)點SqBiTree bt;一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示BACEDFGHIJKLMNOA B C DONMLKJIHGFE1 204357611810912 13 14例例1：滿二叉樹的順序存儲：滿二叉樹的順序存儲根據(jù)完全二叉樹的性質(zhì)5可以求出第i個結(jié)點的雙親和左右孩子的位置。BACEDFGHIJABCDJIHGFE1204357689例例2：完全二叉樹的順序存儲：完全二叉樹的順序存儲BACDEGFBACDEGF(a)一般二叉樹 (b)完全二叉樹形態(tài)(c) 在數(shù)組中的存儲形式 A BC 0G00F000ED120

16、4357611810912數(shù)組下標(biāo)例例3：非完全二叉樹的順序存儲：非完全二叉樹的順序存儲 對于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)?？梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮嬖诘目战Y(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。 練習(xí)練習(xí):ABCDEF14013260123456789 10 11 12 13ABD0C0E000000F對于一般二叉樹其存儲空間浪費很大！二、二叉樹的鏈?zhǔn)酱鎯Ρ硎径⒍鏄涞逆準(zhǔn)酱鎯Ρ硎?. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表* *3 3線索鏈表線索鏈表ADEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):1. 1

17、. 二叉鏈表二叉鏈表typedef struct BiTNode / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :ADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): typedef struct TriTNode / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; struct TriTNode *lchild,

18、 *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :47（請見后面的線索二叉樹線索二叉樹）* *3 3線索鏈表線索鏈表6.3 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹6.3.1 遍歷二叉樹遍歷二叉樹一、問題的提出一、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、遍歷算法的應(yīng)用舉例四、遍歷算法的應(yīng)用舉例*五五、中序遍歷算法的非遞歸描述中序遍歷算法的

19、非遞歸描述 順著某一條搜索路徑巡訪巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一均被訪問一次次，而且僅被訪問一次僅被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)點的信息等。 “遍歷遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼每個結(jié)點有兩個后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問題。 對對“二叉樹二叉樹”而言，可以有而言，可以有三條搜索路徑：三條搜索路徑： 1先上后下先上后下的按層次遍歷； 2先左先左（子樹）后右后右（子樹）的遍歷；

20、3先右先右（子樹）后左后左（子樹）的遍歷。二、先左后右的遍歷算法二、先左后右的遍歷算法先先（根）序的遍歷算法中中（根）序的遍歷算法后后（根）序的遍歷算法 若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法先（根）序的遍歷算法（DLR）：55ABCDEFGHA先序遍歷：ABCDEFGHB D C E G H FB中序遍歷：D A G E H C FD后序遍歷：B G H E F C A二叉樹遍歷的輸出順序示例演示56NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍歷：中序遍歷：后序遍歷：

21、ABDB D C E G H FD A G E H C FB G H E F C A二叉樹遍歷過程的示例演示BACEDFGBACEDFG練習(xí)：先序遍歷的結(jié)果：1、ABDCEGF2、ABDGECF 若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法中（根）序的遍歷算法（LDR） ：BACEDFGBACEDFG練習(xí)：中序遍歷的結(jié)果：1、DBAGECF2、DGBEACF 若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法后（根）序的遍歷算法（LRD） ：BACEDFGBAC

22、EDFG練習(xí)：后序遍歷的結(jié)果：1、DBGEFCA2、GDEBFCA 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹由二叉樹的先序和中序序列建樹 如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？ 二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列推導(dǎo)遍歷結(jié)果練習(xí)1： 已知先序遍歷序列和中序遍歷序列，求二叉樹（或后序遍歷序列） 例：先序序列：ABCDEF 中序序列：CBAEDF

23、求后序：？樹的圖為：后序序列為：CBEFDABADECF練習(xí)2： 已知中序遍歷序列和后序遍歷序列，求二叉樹（或先序遍歷序列） 例：中序序列：ABCDEFG 后序序列：BDCAFGE 求前序：？樹的圖為：先序序列為：EACBDGFAEGFBCD研究遍歷算法有什么用？ 用圖形表示樹的結(jié)構(gòu)對人來說非常直觀和容易理解，而計算機只能處理線性序列，遍歷其實就是把樹中的結(jié)點變成某種意義的線性序列，這就給程序的實現(xiàn)帶來好處。三、遍歷算法的遞歸描述三、遍歷算法的遞歸描述void Preorder (BiTree T, void( *visit)(TElemType &e) / 先序遍歷二叉樹 if (T

24、) visit(T-data); / 訪問結(jié)點 Preorder(T-lchild, visit); / 遍歷左子樹 Preorder(T-rchild, visit);/ 遍歷右子樹 void InOrder(BiTreeNode t, void (*Visit)(DataType item)/*中序遍歷二叉樹t */ if(t != NULL) InOrder(t-leftChild, Visit);Visit(t-data);InOrder(t-rightChild, Visit); void PostOrder(BiTreeNode t, void (*Visit)(DataType

25、item)/*后序遍歷二叉樹t */ if(t != NULL) PostOrder(t-leftChild, Visit);PostOrder(t-rightChild, Visit);Visit(t-data); 課堂練習(xí)：寫出中序和后序遍歷的遞歸算法四、二叉樹遍歷的應(yīng)用四、二叉樹遍歷的應(yīng)用:1、按給定的表達式建相應(yīng)二叉樹、按給定的表達式建相應(yīng)二叉樹例：表達式：(a+b)c d/e d/e可以用以下二叉樹表示規(guī)定： 操作數(shù)為葉子葉子結(jié)點 運算符為分支分支結(jié)點a+b(a+b)c d/e d/ea+bc 分析表達式和二叉樹的關(guān)系分析表達式和二叉樹的關(guān)系:ab+abc+abc+(a+b)cabc

26、de- -+/遍歷其二叉樹二叉樹對應(yīng)的表達式為：先綴表達式 ： - -+ + a b c / d e中綴表達式 ：( a + + b)cd / e后綴表達式 ： a b + + cd e / - -abcde- -+/人喜歡中綴形式的算術(shù)表達式,而對于計算機,使用后綴易于求值（編譯原理）。例2表達式：a+b*(c-d)-e/f構(gòu)建其二叉樹：若先序遍歷此二叉樹,其先序序列為：（波蘭式）*a/b-dcfe -+a*b-cd/ef按中序遍歷,其中序序列為： a+b*(c-d)-e/f按后序遍歷,其后序序列為:(逆波蘭式) abcd-*+ef/-練習(xí)：對于表達式 (a+b)/c-d+e*f 將操作數(shù)作

27、為二叉樹的葉子結(jié)點，操作符作為二叉樹的非葉子結(jié)點，建立二叉樹的圖示。進行先序遍歷，則可得到二叉樹的先序序列為： +-/+abcd*ef 進行中序遍歷，則可得到二叉樹的中序序列為：(a+b)/c-d+e*f 進行后序遍歷，則可得到二叉樹的后序序列為：ab+c/d-ef*+ 2 2、構(gòu)造二叉樹、構(gòu)造二叉樹 在遍歷的過程中生成結(jié)點，建在遍歷的過程中生成結(jié)點，建立二叉樹的存儲結(jié)構(gòu)。立二叉樹的存儲結(jié)構(gòu)。 不同的遍歷方法相應(yīng)有不同的不同的遍歷方法相應(yīng)有不同的建立存儲結(jié)構(gòu)的算法。建立存儲結(jié)構(gòu)的算法。 例：按先序次序輸入二叉樹中例：按先序次序輸入二叉樹中結(jié)點的值構(gòu)造二叉鏈表的算法結(jié)點的值構(gòu)造二叉鏈表的算法76

28、 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如例如: :ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空樹只含一個根結(jié)點的二叉樹A以字符串“A ”表示以下列字符串表示Status CreateBiTree(BiTree &T) /p131算法算法6.4 scanf(&ch); if (ch= ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根結(jié)點 CreateBiTree

29、(T-lchild); / 構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; / CreateBiTreeA B C D A BCD上頁算法執(zhí)行過程舉例如下：ATBCD*五、中序遍歷算法的非遞歸描述五、中序遍歷算法的非遞歸描述 設(shè)設(shè)T是指向二叉樹根結(jié)點的指針變量，非遞歸算法是：是指向二叉樹根結(jié)點的指針變量，非遞歸算法是： 若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T 若若p不為空，不為空，p進棧，進棧， p=p-Lchild ； 否則否則(即即p為空為空)，退棧到，退棧到p，訪問，訪問p所指向的結(jié)點；所指向的結(jié)點； p=p-

30、Rchild ，轉(zhuǎn)，轉(zhuǎn)(1)；直到?？諡橹?。直到棧空為止。算法實現(xiàn)算法實現(xiàn)：p131 算法算法6.3（比較與（比較與p130算法算法6.2的不同）的不同）statuse InorderTraverse( BiTree T, Status(*visit(TElemType e) InitStack(S) , p=T ; while (p |!StackEmpty(S) if (p) Push(S,p); p=p-Lchild ; /根指針進棧，遍歷左子樹根指針進棧，遍歷左子樹 else / 根指針退棧，訪問根結(jié)點，遍歷右子樹根指針退棧，訪問根結(jié)點，遍歷右子樹 Pop(S,p); if (!(vi

31、sit(p-data) ) return ERROR; p=p-Rchild ; /else /while return OK; /InOrderTraverse*6.3.2線索二叉樹線索二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A83 遍歷引起的思考： 遍歷二叉樹把

32、非線性結(jié)構(gòu)以序列的形式加以“線性化”了，那么u 所得序列信息可否長期利用？u 信息保持可否盡量少占用額外的存儲空間？u 是否能否形成一般化的方法？處理辦法： 在遍歷時，串聯(lián)起前驅(qū)、后繼的關(guān)系鏈，以備后期的再利用。84 指向該線性序列中的“前驅(qū)”和“后繼”的指針指針，稱作“線索線索”D B G E H A C I J F 以中序為例,看結(jié)點H的前驅(qū)線索和后繼線索ABCFDGEH IJ的前驅(qū)線索H的后繼線索H85 與其相應(yīng)的二叉樹，稱作 “線索線索二叉樹二叉樹” 包含 “線索” 的存儲結(jié)構(gòu)，稱作 “線索鏈表線索鏈表”根據(jù)遍歷方法的不同，可分成： “先序線索二叉樹線索二叉樹”、 “中序線線索二叉樹索

33、二叉樹”和“后序線索二叉樹線索二叉樹”86typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; struct BiThrNode * pred, *succ; / 前驅(qū)、后繼線索 BiThrNode, *BiThrTree;線索二叉樹線索二叉樹的類型定義：的類型定義：predlchilddatarchildsucc結(jié)點結(jié)構(gòu)：87HABCDEGHFIJT中序線索化二叉樹示例88DBGEHACIJF線索關(guān)系表現(xiàn)為雙向循環(huán)鏈表查找前驅(qū)和后繼變得異常容易出現(xiàn)的問題： 1、新增加的線索指針域增加了存儲空間；

34、 2、左右孩子為空的指針域還是為空，浪費存儲空間；如何改進？改進后的線索化二叉樹： 在二叉樹的二叉鏈表表示方法中，在二叉樹的二叉鏈表表示方法中，n個結(jié)點的二叉鏈表中含有個結(jié)點的二叉鏈表中含有n+1個個空指針域，可以利用這些空指針域空指針域，可以利用這些空指針域來存儲二叉鏈表的前驅(qū)和后繼信息來存儲二叉鏈表的前驅(qū)和后繼信息。 在一個線索二叉樹中，為了區(qū)別每個在一個線索二叉樹中，為了區(qū)別每個結(jié)點的左、右指針域所存放的是孩子結(jié)點的左、右指針域所存放的是孩子指針指針，還是，還是其前驅(qū)或后繼指針其前驅(qū)或后繼指針，就需，就需要要在結(jié)點結(jié)構(gòu)中增加兩個標(biāo)志域：在結(jié)點結(jié)構(gòu)中增加兩個標(biāo)志域：ltag和和rtag。其

35、中。其中l(wèi)tag為左線索標(biāo)志域為左線索標(biāo)志域，rtag為右線索標(biāo)志域。因此，線索為右線索標(biāo)志域。因此，線索化二叉樹的結(jié)點結(jié)構(gòu)如下圖所示?；鏄涞慕Y(jié)點結(jié)構(gòu)如下圖所示。圖 二叉樹的帶線索標(biāo)志的存儲結(jié)構(gòu)結(jié)點示意圖ltag和rtag的取值情況如下：0, lchildltag1, lchild指向結(jié)點的左孩子指向結(jié)點的前驅(qū)0, rchildrtag1, rchild指向結(jié)點的左孩子指向結(jié)點的后繼問題：還是需要5個域來存儲信息呀？其實：ltag和rtag只是存儲0或1數(shù)字的布爾型變量，其占用的內(nèi)存空間要小于指針變量pred,succ的。對對線索鏈表線索鏈表中結(jié)點的約定：中結(jié)點的約定：若該結(jié)點的左子樹不空

36、，若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“指針 Link”； 否則，Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 Thread” 。若該結(jié)點的右子樹不空，若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “指針 Link”；否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 Thread”。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表線索鏈表”。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild,

37、 *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表的類型描述： typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索AFHIEGBDC(a) 二叉樹二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結(jié)點序列：結(jié)點序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹的邏輯形式后序線索樹的邏輯形式 結(jié)點序列：結(jié)點序列：DBGEHIFCA(c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結(jié)點序列：結(jié)點序列：DBAG

38、ECHFIAFHIEGBDCNILNILAFHIEGBDCNIL 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 (e) 中序線索樹的鏈表結(jié)構(gòu)中序線索樹的鏈表結(jié)構(gòu)圖圖 線索二叉樹及其存儲結(jié)構(gòu)線索二叉樹及其存儲結(jié)構(gòu)說明說明：畫線索二叉樹時，畫線索二叉樹時，實線實線表示指針，表示指針，指向其左指向其左、右孩子；右孩子；虛線虛線表示線索，指向表示線索，指向其直接前驅(qū)或直接后繼。其直接前驅(qū)或直接后繼。 98 0 1TA0 0 0B00C10D11E00G11H11F01I10J11P中序線索化二叉樹練習(xí)帶頭結(jié)點的線索二叉樹的線索化二、在線索樹

39、上如何進行遍歷？二、在線索樹上如何進行遍歷？ 遍歷帶有線索的二叉樹，由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。既無需遞歸遍歷，也無需棧的協(xié)助，只進行相當(dāng)“線性結(jié)構(gòu)線性結(jié)構(gòu)”的尋訪即可，而且可正反雙向進行。例如例如: 對中序線索化鏈表的遍歷算法對中序線索化鏈表的遍歷算法 中序遍歷的第一個結(jié)點中序遍歷的第一個結(jié)點 ？ 在中序線索化鏈表中結(jié)點的后繼在中序線索化鏈表中結(jié)點的后繼 ？左子樹上處于“最左下最左下”（沒有左子樹）的結(jié)點。若若無右子樹，則為則為后繼線索后繼線索所指結(jié)點；否則為否則為對其右子樹右子樹進行中序遍歷遍歷時訪問的第一個結(jié)點。第一個結(jié)點。 void

40、 InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e) /p134算法6.5中序遍歷線索二叉樹 p = T-lchild; / p指向根結(jié)點，T是頭結(jié)點 while (p != T) / 空樹或遍歷結(jié)束時，p= =T while (p-LTag=Link) p = p-lchild; / 找第一個結(jié)點 if(!Visit(p-Data) return ERROR; /訪問其左子樹為空的結(jié)點 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data);

41、 / 訪問后繼結(jié)點 p = p-rchild; / p進至其右子樹根 / InOrderTraverse_Thr 在中序遍歷過程中修改結(jié)點的在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)左、右指針域，以保存當(dāng)前訪問結(jié)點的點的“前驅(qū)前驅(qū)”和和“后繼后繼”信息。遍信息。遍歷過程中，附設(shè)指針歷過程中，附設(shè)指針pre, 并始終保并始終保持指針持指針pre指向當(dāng)前訪問的指針指向當(dāng)前訪問的指針p所所指結(jié)點的前驅(qū)。指結(jié)點的前驅(qū)。三、如何建立線索鏈表？三、如何建立線索鏈表？Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 構(gòu)建中序

42、線索鏈表，p134算法6.6 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加頭結(jié)點 return OK; / InOrderThreading if (!T) Thrt-lchild = Thrt; /空樹頭結(jié)點左孩子指向自己else Thrt-lchild = T; /非空樹頭結(jié)點左孩子指向樹根 pre = Thrt; /頭結(jié)點是樹根的前驅(qū) InThreading(T); /線索化樹

43、 pre-rchild = Thrt; / 處理最后一個結(jié)點 pre-RTag = Thread; Thrt-rchild = pre; void InThreading(BiThrTree p) /p135算法6.7 if (p) / 對以p為根的非空二叉樹進行線索化 InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pr

44、e 指向 p 的前驅(qū) InThreading(p-rchild); / 右子樹線索化 / if / InThreading 6.4 樹和森林樹和森林 的表示方法的表示方法樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲表示法存儲表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一、雙親表示法一、雙親表示法： typedef struct PTNode TElemType data; int paren

45、t; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C語言的類型描述語言的類型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點的位置和結(jié)點個數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):二、孩子鏈表表示法二、孩子鏈表表示法樹中每個結(jié)點有多個指針域，每個指針指向其一棵子樹樹中每個結(jié)點有多個指針域，每個指針指向其一棵子樹的根結(jié)點的根結(jié)點。有。有兩種結(jié)點結(jié)構(gòu)兩種結(jié)點結(jié)構(gòu)。 定長結(jié)點結(jié)構(gòu)定長結(jié)點結(jié)構(gòu) 指針域的數(shù)目就是樹的度指針域的數(shù)目就是樹的度。 其特點是其特點是：

46、鏈表結(jié)構(gòu)簡單，但指針域的浪費明顯：鏈表結(jié)構(gòu)簡單，但指針域的浪費明顯。結(jié)點結(jié)構(gòu)如下圖結(jié)點結(jié)構(gòu)如下圖所示所示。data child1 child2 childn 定長結(jié)點結(jié)構(gòu)定長結(jié)點結(jié)構(gòu)ABCDEFGAB CD E F G root不不定長結(jié)點結(jié)構(gòu)定長結(jié)點結(jié)構(gòu)data k child1 child2 childk 不定長結(jié)點結(jié)構(gòu)不定長結(jié)點結(jié)構(gòu) 樹中每個結(jié)點的指針域數(shù)量不同，樹中每個結(jié)點的指針域數(shù)量不同，是該結(jié)點的度，如下圖所示。沒有多是該結(jié)點的度，如下圖所示。沒有多余的指針域，但操作不便。余的指針域，但操作不便。ABCDEFGA3B 0C 2D 0E 0F 1G 0root （3）復(fù)合孩子鏈表結(jié)構(gòu)

47、）復(fù)合孩子鏈表結(jié)構(gòu) 對于樹中的每個結(jié)點，其孩子結(jié)點用對于樹中的每個結(jié)點，其孩子結(jié)點用帶頭結(jié)點的帶頭結(jié)點的單鏈表單鏈表表示，孩子結(jié)點和頭結(jié)表示，孩子結(jié)點和頭結(jié)點的結(jié)構(gòu)如圖所示點的結(jié)構(gòu)如圖所示。 n個結(jié)點的樹有個結(jié)點的樹有n個個(孩子孩子)單鏈表單鏈表(葉子葉子結(jié)點的孩子鏈表為空結(jié)點的孩子鏈表為空)，而，而n個頭結(jié)點又組個頭結(jié)點又組成一個線性表且以成一個線性表且以順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)表示表示。data firstchild(a) 頭結(jié)點頭結(jié)點child next(b) 孩子結(jié)點孩子結(jié)點圖圖 孩子鏈表結(jié)點結(jié)構(gòu)孩子鏈表結(jié)點結(jié)構(gòu)CTBox（頭結(jié)點）（頭結(jié)點）6 1235 40123456MAX_TR

48、EE_SIZE-1rnA B C D FG E 07圖圖 孩子鏈表存儲結(jié)構(gòu)孩子鏈表存儲結(jié)構(gòu)CTNode（孩子結(jié)點）Ctree樹結(jié)點ABCDEFGtypedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點結(jié)構(gòu)孩子結(jié)點結(jié)構(gòu): child nextC語言的類型描述語言的類型描述: : typedef struct TElemType data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;頭結(jié)點結(jié)構(gòu)頭結(jié)點結(jié)構(gòu) data firstchildtypedef struct CTBox nodesM

49、AX_TREE_SIZE; int n, r; / 結(jié)點數(shù)和根結(jié)點的位置 CTree;樹結(jié)構(gòu)樹結(jié)構(gòu):ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 4r=0n=7 data firstchild 1 2 34 56（4）帶雙親的復(fù)合鏈表結(jié)構(gòu)）帶雙親的復(fù)合鏈表結(jié)構(gòu)-1000224 typedef struct TElemType data; int parent; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;帶雙親的頭結(jié)點結(jié)構(gòu)帶雙親的頭結(jié)點結(jié)構(gòu)dataparentfirstchild三、樹的二叉鏈表三、樹的二叉鏈表 (孩子孩子-兄

50、弟）存儲表示法兄弟）存儲表示法設(shè)結(jié)點的左指針指示其第一個孩子， 右指針指示其兄弟。firstchild data nextsibling孩子兄弟表示法rootBCDEFGAABCDEFGABCDEFG AB C E D F Groot AB C E D F G 順時針旋轉(zhuǎn)一下typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C語言的類型描述語言的類型描述: :結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): firstchild data nextsibling6.4.2 森林與二叉樹

51、的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，對比各自的結(jié)點結(jié)構(gòu)可以看出，以二叉鏈表構(gòu)，對比各自的結(jié)點結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹和二叉樹之間的一個對應(yīng)關(guān)作為媒介可以導(dǎo)出樹和二叉樹之間的一個對應(yīng)關(guān)系。系。 從物理結(jié)構(gòu)來看，樹和二叉樹的二叉鏈表從物理結(jié)構(gòu)來看，樹和二叉樹的二叉鏈表是相同的，只是對指針的邏輯解釋不同而已。是相同的，只是對指針的邏輯解釋不同而已。 從樹的二叉鏈表表示的定義可知，任何一從樹的二叉鏈表表示的定義可知，任何一棵和樹對應(yīng)的二叉樹，其右子樹一定為空。棵和樹對應(yīng)的二叉樹，其右子樹一定為空。 下圖直觀地展示了

52、樹和二叉樹之間的對應(yīng)關(guān)下圖直觀地展示了樹和二叉樹之間的對應(yīng)關(guān)系。系。圖圖6-18 樹與二叉樹的對應(yīng)關(guān)系樹與二叉樹的對應(yīng)關(guān)系二叉樹二叉樹 CERADB R A D C B E 樹樹 RABCDE對應(yīng)關(guān)系對應(yīng)關(guān)系 R A D C B E C B E R A D 存儲存儲解釋解釋存儲存儲解釋解釋1 樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹 對于一般的樹，可以方便地轉(zhuǎn)換成一棵唯一的二叉對于一般的樹，可以方便地轉(zhuǎn)換成一棵唯一的二叉樹與之對應(yīng)。將樹轉(zhuǎn)換成二叉樹在樹與之對應(yīng)。將樹轉(zhuǎn)換成二叉樹在“孩子兄弟表示法孩子兄弟表示法”中已給出，其詳細步驟是：中已給出，其詳細步驟是： 加虛線加虛線。在樹的每層按從。在樹的每層按從“

53、左至右左至右”的順序在兄的順序在兄弟結(jié)點之間加虛線相連。弟結(jié)點之間加虛線相連。 去連線去連線。除最左的第一個子結(jié)點外，父結(jié)點與所。除最左的第一個子結(jié)點外，父結(jié)點與所有其它子結(jié)點的連線都去掉。有其它子結(jié)點的連線都去掉。 旋轉(zhuǎn)旋轉(zhuǎn)。將樹順時針旋轉(zhuǎn)。將樹順時針旋轉(zhuǎn)450，原有的實線左斜。，原有的實線左斜。 整型整型。將旋轉(zhuǎn)后樹中的所有虛線改為實線，并向。將旋轉(zhuǎn)后樹中的所有虛線改為實線，并向右斜。該轉(zhuǎn)換過程如下圖所示。右斜。該轉(zhuǎn)換過程如下圖所示。 這樣轉(zhuǎn)換后的二叉樹的特點是這樣轉(zhuǎn)換后的二叉樹的特點是： 二叉樹的二叉樹的根結(jié)點沒有右子樹根結(jié)點沒有右子樹，只有左子樹；，只有左子樹； 左子結(jié)點仍然是原來樹中

54、相應(yīng)結(jié)點的左子結(jié)點，左子結(jié)點仍然是原來樹中相應(yīng)結(jié)點的左子結(jié)點，而所有沿右鏈往下的右子結(jié)點均是原來樹中該結(jié)點的而所有沿右鏈往下的右子結(jié)點均是原來樹中該結(jié)點的兄弟結(jié)點。兄弟結(jié)點。樹向二叉樹的轉(zhuǎn)換過程：樹向二叉樹的轉(zhuǎn)換過程：(a) 一般的樹一般的樹 FGRABCDEFGRABCDE(b) 加虛線加虛線，去連線后去連線后 (C) 轉(zhuǎn)換后的二叉樹轉(zhuǎn)換后的二叉樹FGRACDBEABCDEFGHIJMKL練習(xí)練習(xí): :將下面這棵樹轉(zhuǎn)換成二叉樹將下面這棵樹轉(zhuǎn)換成二叉樹轉(zhuǎn)換后的二叉樹ABCDEFGHIJMKL2 二叉樹轉(zhuǎn)換成樹二叉樹轉(zhuǎn)換成樹 對于一棵轉(zhuǎn)換后的二叉樹，如何還原成原來的樹對于一棵轉(zhuǎn)換后的二叉樹，如何

55、還原成原來的樹? 其步驟是：其步驟是： 加虛線加虛線。若某結(jié)點。若某結(jié)點i是其父結(jié)點的左子樹的根結(jié)是其父結(jié)點的左子樹的根結(jié)點，則將該結(jié)點點，則將該結(jié)點i的右子結(jié)點以及沿右子鏈不斷地搜的右子結(jié)點以及沿右子鏈不斷地搜索所有的右子結(jié)點，將所有這些右子結(jié)點與索所有的右子結(jié)點，將所有這些右子結(jié)點與i結(jié)點的結(jié)點的父結(jié)點之間加虛線相連，父結(jié)點之間加虛線相連，如下圖如下圖(a)所示所示。 去連線去連線。去掉二叉樹中所有父結(jié)點與其右子結(jié)點。去掉二叉樹中所有父結(jié)點與其右子結(jié)點之間的連線，之間的連線，如下圖如下圖(b)所示所示。 規(guī)整化規(guī)整化。將圖中各結(jié)點按層次排列且將所有的虛。將圖中各結(jié)點按層次排列且將所有的虛線

56、變成實線，線變成實線，如下圖如下圖(c)所示。所示。圖圖 二叉樹向樹的轉(zhuǎn)換過程二叉樹向樹的轉(zhuǎn)換過程(C) 還原后的樹還原后的樹FGRABCDE(b) 去連線后去連線后 (a) 加虛線后加虛線后 FGRACDBECFGRADBE練習(xí)：二叉樹轉(zhuǎn)換成樹BACEDFGBACEDFG3 森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹 當(dāng)一般的樹轉(zhuǎn)換成二叉樹后，二叉樹的當(dāng)一般的樹轉(zhuǎn)換成二叉樹后，二叉樹的右子樹必為空右子樹必為空。若把森林中的第二棵樹。若把森林中的第二棵樹( (轉(zhuǎn)換轉(zhuǎn)換成二叉樹后成二叉樹后) )的根結(jié)點作為第一棵樹的根結(jié)點作為第一棵樹(二叉樹二叉樹)的根結(jié)點的兄弟結(jié)點，則可導(dǎo)出森林轉(zhuǎn)換成的根結(jié)點的兄弟結(jié)點

57、，則可導(dǎo)出森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換步驟如下：二叉樹的轉(zhuǎn)換步驟如下： 轉(zhuǎn)換步驟轉(zhuǎn)換步驟： 將將F=T1, T2, ,Tn 中的每棵樹轉(zhuǎn)換成二叉樹中的每棵樹轉(zhuǎn)換成二叉樹。 按給出的森林中樹的次序，從最后一棵二叉樹開按給出的森林中樹的次序，從最后一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的根結(jié)點的右子始，每棵二叉樹作為前一棵二叉樹的根結(jié)點的右子樹，依次類推，則第一棵樹的根結(jié)點就是轉(zhuǎn)換后生樹，依次類推，則第一棵樹的根結(jié)點就是轉(zhuǎn)換后生成的二叉樹的根結(jié)點，成的二叉樹的根結(jié)點，如下圖如下圖所示所示。ACBDGMLHK(a) 森林森林圖圖 森林轉(zhuǎn)換成二叉樹的過程森林轉(zhuǎn)換成二叉樹的過程(b) 森林中每棵樹森林中每

58、棵樹 對應(yīng)的二叉樹對應(yīng)的二叉樹ABCDGLKHM(c) 森林對應(yīng)的二叉樹森林對應(yīng)的二叉樹ABCDGLKHM練習(xí)：森林轉(zhuǎn)換成二叉樹BACEDFGIHJLKM轉(zhuǎn)換后的二叉樹：BACEDFGIHJLKM4 二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林 若若B=(root，LB，RB)是一棵二叉樹，是一棵二叉樹，則可以將其轉(zhuǎn)換成由若干棵樹構(gòu)成的森林：則可以將其轉(zhuǎn)換成由若干棵樹構(gòu)成的森林：F=T1, T2, ,Tn 。轉(zhuǎn)換步驟轉(zhuǎn)換步驟： 去連線去連線。將二叉樹。將二叉樹B的根結(jié)點與其右子的根結(jié)點與其右子結(jié)點以及沿右子結(jié)點鏈方向的所有右子結(jié)點結(jié)點以及沿右子結(jié)點鏈方向的所有右子結(jié)點的連線全部去掉，得到若干棵孤立的二叉樹

59、，的連線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來森林每一棵就是原來森林F中的樹依次對應(yīng)的二中的樹依次對應(yīng)的二叉樹，叉樹，如下圖如下圖 (b)所示所示。 二叉樹的還原二叉樹的還原。將各棵孤立的二叉樹按二。將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹，叉樹還原為樹的方法還原成一般的樹，如下如下圖圖(c)所示所示。圖圖 二叉樹還原成森林的過程二叉樹還原成森林的過程ACBDMGLHK(c) 還原成森林還原成森林(a) 二叉樹二叉樹ABCDGLKHM(b) 去連線后去連線后ABCDMGLKH練習(xí)：二叉樹轉(zhuǎn)換成森林ABCFDGEH IJ轉(zhuǎn)換后的森林：ABCFDGEH IJ 由此，樹的各種

60、操作均可對應(yīng)二叉樹的操作來完成。 應(yīng)當(dāng)注意的是，應(yīng)當(dāng)注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。左是孩子，右是兄弟。6.4.3樹和森林的遍歷樹和森林的遍歷一、樹的遍歷一、樹的遍歷二、森林的遍歷二、森林的遍歷一、樹的遍歷一、樹的遍歷 可有兩條搜索路徑可有兩條搜索路徑:先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷: 若樹不空，則先訪問根結(jié)點，然后若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。依次先根遍歷各棵子樹。 若樹不空，則先依次后根遍歷各棵若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。子樹，然后訪問根結(jié)點。 A B C DE F G H I J K 先根遍歷時頂點先根遍歷時頂點的訪問次序：的訪問次序：A B E F C D G H I J K 后根遍歷時頂點后根