61樹和二叉樹

1、第六章 樹和二叉樹 主要內(nèi)容 n樹和二叉樹定義 n二叉樹性質(zhì)，存貯結(jié)構(gòu)，遍歷算法 n遍歷二叉樹和線索二叉樹 n二叉樹和樹，樹和森林關(guān)系 nHuffman樹與Huffman編碼 樹例與特征 n1.社會(huì)的組織結(jié)構(gòu) n2.家族的族譜 n3.C語言中的結(jié)構(gòu)的描述 n4.計(jì)算機(jī)中的目錄組織 n描述層次結(jié)構(gòu)，是一種一 對(duì)多的邏輯關(guān)系 樹定義 n樹(Tree)是n(n=0)個(gè) 結(jié)點(diǎn)的有限集。n=0時(shí) 稱為空樹。 n有且僅有一個(gè)稱為根的 結(jié)點(diǎn)（Root）； nn1時(shí)，其余結(jié)點(diǎn)可分為 m(m0)個(gè)互不相交的有 限集T1Tm,其中每個(gè) 集合又是一棵樹，稱為 子樹(SubTree) A B CD E H FG I

2、1 2 3 4 樹定義 A CB GFEHIJ D MKL A T1T2T3 n結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及若干指向其子樹 的分支； n結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目。 Degree； n葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)；Leaf n分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié) 點(diǎn)；除根結(jié)點(diǎn)外，也稱內(nèi)部結(jié)點(diǎn)； n樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值； 概念_1 概念_2 n孩子，雙親，兄弟：結(jié)點(diǎn)的子樹稱為該結(jié)點(diǎn)的 孩子；該結(jié)點(diǎn)稱為孩子的雙親；同一個(gè)雙親的 孩子之間互稱兄弟（Sibling）,Child, Parent n祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié) 點(diǎn)。 n子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱 為該結(jié)

3、點(diǎn)的子孫。 n層次：結(jié)點(diǎn)在樹結(jié)構(gòu)中的層 n堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟； 概念_3 n深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深 度；Depth n有序樹：結(jié)點(diǎn)的子樹在樹中的位置固定， 不能互換，稱有序樹 n無序樹：可以互換 n森林：m(m0)棵互不相交的樹的集合。 n對(duì)于樹中的一個(gè)結(jié)點(diǎn)，其子樹即為森林。 概念示例 n結(jié)點(diǎn) n結(jié)點(diǎn)的度(Degree) n葉子（Leaf)或終端結(jié)點(diǎn) n分支結(jié)點(diǎn)或非終端結(jié)點(diǎn) n樹的度 n層次(Level) n樹的深度(Depth) n孩子（child) n雙親（Parent) n兄弟(Sibling) n堂兄第 A CB GFEHIJ D MKL n祖先 n子孫

4、樹的其它表示方式 A CB GFEHIJ D MKL A J I M H D G C F L K E B 凹入表示 A B F E K L G C D H M I J 嵌套集合 (A(B(E(K,L),F),C(G),D(H(M),I,J) 廣義表 樹和二叉樹的關(guān)系 n任何一棵樹是一個(gè)二元組Tree = ( root, F )，其中： root是數(shù)據(jù)元素，稱為樹的根結(jié)點(diǎn)；F是m( m= 0 )棵 樹的森林，F(xiàn) = ( T1, T2, Tm )，其中Ti = ( ri, Fi ) 稱為樹根root的第 i 棵子樹; 當(dāng)m != 0時(shí)，在樹根和其 子樹森林之間存在下列關(guān)系： RF = | i =

5、1,2,m, m 0 ADT表示1 ADT Tree n數(shù)據(jù)對(duì)象D： nD是具有相同特性的數(shù)據(jù)元素的集合 n數(shù)據(jù)關(guān)系R： n若D為空集，則稱為空樹； n若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則 R=H，H是如下二元關(guān)系： n 在D中存在唯一的稱為根的數(shù)據(jù)元素root， 它在關(guān)系H下無前驅(qū)； ADT表示2 n 若D-root,則存在D-root的一個(gè)劃分 D1,D2,Dm(m0)，對(duì)任意jk (1j,km) 又DjDk=,且對(duì)任意的i(1im)，唯一存 在數(shù)據(jù)元素xiDi，有H; n 對(duì)應(yīng)于D-root的劃分，H - , 有唯一的一個(gè)劃分 H1,H2,Hm，m0，對(duì)任意jk(1j,km) 有HjH

6、k=，且對(duì)任意i（1im），Hi是 Di上的二元關(guān)系，（Di,Hi）是一棵符合本 定義的樹，稱為根root的子樹。 ADT表示3 n基本操作： InitTree( / 初始化 DestroyTree( / 銷毀 CreateTree( / 按條件definition構(gòu)造樹 ClearTree( / 清空 TreeEmpty( T );/ 空？ TreeDepth( T );/ 樹的深度 Root( T );/ 樹根 Value( T, cur_e );/ 求結(jié)點(diǎn)cur_e的值 Assign( T, cur_e, value );/ 賦值 ADT表示3 Parent( T, cur_e );/

7、求cur_e的雙親 LeftChild( T, cur_e );/ 求cur_e的最左孩子 RightSibling( T, cur_e );/ 求cur_e的右兄弟 / 插入c為T中p所指結(jié)點(diǎn)的第I棵子樹 InsertChild( / 刪除T中，p所指結(jié)點(diǎn)的第I個(gè)子樹 DeleteChild( TraverseTree( T, visit() );/遍歷 /ADT Tree 二叉樹（Binary Tree） n最簡(jiǎn)單的樹 n特征： n1.每個(gè)結(jié)點(diǎn)最多只有兩棵子樹 n2.子樹有左右之分，其次序不能任意顛倒，是 一個(gè)有序樹 二叉樹的ADT表示 ADT BinaryTree 數(shù)據(jù)對(duì)象D：D是具有相

8、同特性的數(shù)據(jù)元素的集合； 數(shù)據(jù)關(guān)系R: 若D = ，則 R = ， 稱BinaryTree為空二叉樹； 若D ，則 R = H , H是如下的二元關(guān)系： (1) 在D中，存在唯一的稱為根的數(shù)據(jù)元素 root, 它在關(guān)系H下無前驅(qū)； (2) 若D root , 則存在D-root = Dl, Dr, 且 Dl Dr = ； 二叉樹的ADT表示 (3) 若Dl , 則Dl中存在唯一的元素xl, H, 且存在Dl上的關(guān)系 Hl H；若Dr , 則 Dr中存在唯一的元素xr, H, 且存 在Dr上的關(guān)系Hr H； H = , Hl, Hr; (4) ( Dl, Hl)是一棵符合本定義的二叉樹，稱為根

9、的左子樹；( Dr, Hr)是一棵符合本定義的二叉 樹，稱為根的右子樹； 基本操作： InitBiTree( / 初始化 DestroyBiTree( / 銷毀 二叉樹的ADT表示 CreateBiTree( / 創(chuàng)建二叉樹 ClearBiTree( / 清空 BiTreeEmpty( T );/ 空？ BiTreeDepth( T );/ 深度 Root( T );/ 根 Value( T, e );/ 求e的值 Assign( T, / 賦值 Parent( T, e );/ 求雙親 LeftChild( T, e );/ 左孩子 RightChild( T, e );/ 右孩子 Left

10、Sibling( T, e) ;/ 左兄弟 二叉樹的ADT表示 RightSibling( T, e );/ 右兄弟 InsertChild( T, p, LR, c );/ 插入 DeleteChild( T, p, LR );/ 刪除 PreOrderTraverse( T, Visit( );/ 先序遍歷 InOrderTraverse( T, Visit( );/ 中序遍歷 PostOrderTraverse( T, Visit( );/ 后序遍歷 LeverOrderTraverse( T, Visit( );/ 層序遍歷 / ADT BinaryTree 二叉樹的五種形態(tài) n有且僅

11、有： 空/僅有根/僅有左子樹/完整的是樹/僅有右子樹 (a)(a) (b)(b) (c)(c) (d)(d) (e)(e) 二叉樹的性質(zhì) 1.二叉樹第i層上，最多有2i-1個(gè)結(jié)點(diǎn)（i=1） 證明：i = 1, 只有根結(jié)點(diǎn)，顯然成立 設(shè)i = k時(shí)成立，最多有2k-1 當(dāng)i= k+1時(shí)，最多的結(jié)點(diǎn)個(gè)數(shù)： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1 2. 深度為k的二叉樹，最多有2k-1個(gè)結(jié)點(diǎn)。 證明：二叉樹的結(jié)點(diǎn)個(gè)數(shù)為： 1 + 2 + + 2k-1= 2k-1 二叉樹的性質(zhì) 3.對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0， 度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 +1

12、; 證明： 設(shè)n1為T中度為1的結(jié)點(diǎn)數(shù)，則總結(jié)點(diǎn)數(shù)： n = n0 + n1 + n2 另：除根結(jié)點(diǎn)外，所有結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn)， 也就是僅有一個(gè)分支進(jìn)入，若B為分支數(shù)，則 B = n1 + 2 * n2 = n - 1； n1 + 2 * n2 = n0 + n1 + n2 1; n0 = n2 + 1; 定義：滿二叉樹 n滿二叉樹：深度為k 且有2k-1個(gè)結(jié)點(diǎn)的二 叉樹。 n考慮到有序性，任一 結(jié)點(diǎn)在樹中都有確切 的位置，因此可以對(duì) 滿二叉樹進(jìn)行編號(hào)。 編號(hào)方式為：從上到 下，從左到右。 1 89101112131415 45 2 67 3 滿二叉樹 完全二叉樹 n完全二叉樹：深度為

13、k，有n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng) 其每一個(gè)結(jié)點(diǎn)都與深度為k的 滿二叉樹編號(hào)從1到n的結(jié)點(diǎn) 一一對(duì)應(yīng)時(shí)，成為完全二叉 樹。 n特征： n1.葉子結(jié)點(diǎn)只可能在層次 最大的兩層上出現(xiàn) n2.任一結(jié)點(diǎn)，若其右分支 下的子孫的最大層次為l， 則其左分支下的最大層次 為l或l+1. 1 89101112 45 2 67 3 完全二叉樹 完全二叉樹的特性 1.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k = Log2n +1 （x表示不大于x的最大整數(shù)） 證明：設(shè)樹的深度為k，則： 2k-1 1 n 2k 1 2k-1 n 2k k-1 log2n 1，則其雙親是i/2; n2。如果2i n ，則結(jié)點(diǎn)i 無左孩子，否

14、則其左孩子 是2i n3。如果2i +1 n，則結(jié)點(diǎn)i 無右孩子，否則其右孩 子是2i+1 示意圖 2i2i2i+12i+1 i i 2i+22i+2 2i+32i+3 i+1i+1 i/2i/2 j層 1 2 j i j+1層 i j 222 1 示意圖 2i2i+1 i 2i+2 2i+3 i+1 i/2 LCHILD(i)LCHILD(i+1) RCHILD(i)RCHILD(i+1) 2i+2 2i+3 i+1 2i2i+1 i . . 二叉樹的存貯結(jié)構(gòu) n順序存貯結(jié)構(gòu) n鏈?zhǔn)酱尜A結(jié)構(gòu) n考慮數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系 二叉樹的順序存貯結(jié)構(gòu) n考慮 n采用順序存貯結(jié)構(gòu)，實(shí)際要求對(duì)非線

15、性的結(jié)構(gòu)線性 化； n樹是一個(gè)層次結(jié)構(gòu) n二叉樹是有序樹 n整個(gè)二叉樹可以按照從上到下，從左到右的順序排 序，做標(biāo)號(hào)； n對(duì)于滿/完全二叉樹，可以從根結(jié)點(diǎn)開始按序號(hào)存放 n對(duì)于一般的二叉樹，可以參照滿二叉樹的編碼方法 進(jìn)行編碼，位置空的結(jié)點(diǎn)空置。 二叉樹的順序存貯結(jié)構(gòu)_C表示 #define MAX_TREE_SIZE100 / 0號(hào)單元存放根結(jié)點(diǎn)； typedef TElemType sqBiTreeMAX_TREE_SIZE; SqBiTree bi; 順序存貯結(jié)構(gòu)舉例 123456789 10 11 12 1 89101112 45 2 67 3 完全二叉樹 順序存貯結(jié)構(gòu)舉例 12345

16、 67 1 67 45 23 非完全二叉樹 12345000067 X 二叉樹的鏈?zhǔn)酱尜A結(jié)構(gòu) n考慮： n二叉樹的數(shù)據(jù)元素之間的關(guān)系 n任一個(gè)結(jié)點(diǎn)，最多有兩個(gè)孩子（直接后繼元 素） n二叉鏈表 pLChilddatapRChild data pLChild pRChild 找孩子容易，但不例于找雙親 二叉樹的鏈?zhǔn)酱尜A結(jié)構(gòu) n除根結(jié)點(diǎn)外，所有結(jié)點(diǎn)都有一個(gè)雙親結(jié)點(diǎn) （直接前驅(qū)元素）； n三叉鏈表 pLChilddatapRChild data pLChild pRChild 找孩子容易，但不利于找雙親 pParent pParent 二叉鏈表的C表示 typedef struct BiTNode

17、TElemTypedata; struct BiTNode *pLChild, *pRChild; BiTNode, *BiTree; 鏈?zhǔn)酱尜A結(jié)構(gòu)例 A B CD EF G A? B C?D E?F? G? 算法-寫出用二叉鏈表表示給定二叉樹的葉結(jié)點(diǎn)總數(shù)的算法 #include #include typedef char Datatype;/以下為二叉鏈表的結(jié)構(gòu)定義 typedef struct node Datatype data; node *lchild; node *rchild; BinTreeNode; 算法-寫出用二叉鏈表表示給定二叉樹的葉結(jié)點(diǎn)總數(shù)的算法 typedef Bin

18、TreeNode *BinTree; void CreatBinTree(BinTree *T) /構(gòu)造二叉鏈表。T是指向根的指針，故修改了*T就修改了實(shí)參 char ch; if (ch=getchar()= ) *T=NULL; else /讀入非空格 *T=(BinTreeNode *)malloc(sizeof(BinTreeNode);/生成結(jié)點(diǎn) (*T)-data=ch; CreatBinTree( /構(gòu)造左子樹 CreatBinTree( /構(gòu)造右子樹 算法-寫出用二叉鏈表表示給定二叉樹的葉結(jié)點(diǎn)總數(shù)的算法 /*以下為題目要求算法*/ int GetLeaves( BinTree

19、root) /求葉結(jié)點(diǎn)總數(shù) static int leaf=0;/此l用于記葉結(jié)點(diǎn)數(shù)，注意用靜態(tài)變量 if(root) /遞歸計(jì)算葉結(jié)點(diǎn)數(shù) if(!(root-lchild|root-rchild) leaf+; /如果該結(jié)點(diǎn)無左右孩子，則葉子數(shù)加1 GetLeaves(root-lchild);/算左子數(shù)的葉結(jié)點(diǎn)數(shù) GetLeaves(root-rchild);/算右子樹的葉結(jié)點(diǎn)數(shù) return leaf;/返回結(jié)果 /*算法結(jié)束*/ 算法-寫出用二叉鏈表表示給定二叉樹的葉結(jié)點(diǎn)總數(shù)的算法 void main() /以下為驗(yàn)證程序 BinTree root; CreatBinTree( int

20、 leaves=GetLeaves(root); printf(Total leaves=%d,leaves); 樹的存貯結(jié)構(gòu) n考慮存貯結(jié)構(gòu)時(shí)，主要考慮表示邏輯結(jié) 構(gòu)： n數(shù)據(jù)元素 n數(shù)據(jù)元素之間的關(guān)系 n樹的存貯結(jié)構(gòu)： n順序存貯結(jié)構(gòu) n鏈?zhǔn)酱尜A結(jié)構(gòu) 樹的存貯結(jié)構(gòu) A B E C D F 1. 除根外的任一個(gè)數(shù)據(jù)元素，都有且僅有一個(gè)雙親_ 從縱向，向上描述樹； 2. 任一數(shù)據(jù)元素，有0個(gè)或多個(gè)孩子_從縱向，向下描 述樹 ； 3. 任一數(shù)據(jù)元素，縱向有孩子，橫向有兄弟；_從縱 向和橫向描述樹 雙親表示法 n一個(gè)靜態(tài)數(shù)組，存放所有的結(jié)點(diǎn) n數(shù)組的每個(gè)數(shù)據(jù)元素，包括兩部 分：數(shù)據(jù)元素，整數(shù)表示該

21、結(jié)點(diǎn) 的雙親結(jié)點(diǎn)在數(shù)組中的位置；根 結(jié)點(diǎn)的整數(shù)為-1。 n特點(diǎn)： n1. 方便找結(jié)點(diǎn)的雙親； n2. 順序存貯結(jié)構(gòu)； A B C D E F -1 0 0 0 2 2 雙親表示法_C表示 / 樹的雙親表示法的存貯結(jié)構(gòu) #define MAX_TREE_SIZE100 typedef struct PTNode TElemType data;/ 數(shù)據(jù)元素 int nParent;/ 雙親結(jié)點(diǎn)在存貯區(qū)中的位置 PTNode; typedef struct PTNode astNodes MAX_TREE_SIZE ; int n;/ 結(jié)點(diǎn)數(shù) PTree; 算法：找根 / 采用遍歷 Status R

22、oot( PTree i T.n; i+ ) if( T.astNodesi.nParent = -1 ) root = T.astNodesi.data; return OK; return ERROR;/ 存貯結(jié)構(gòu)有錯(cuò)誤 / Root 算法：找根 / 找根：考慮樹的層次結(jié)構(gòu) Status Root( PTree k = 0; while( k+ T.n if( k T.n ) root = r.data; return OK; return ERROR; /Root 孩子表示法 n任一數(shù)據(jù)元素，有0個(gè)或多個(gè)孩子； n因此可以設(shè)計(jì)一個(gè)鏈?zhǔn)酱尜A結(jié)構(gòu)，其結(jié)點(diǎn)除放 置數(shù)據(jù)元素外，還可以放置若干指針

23、，分別用 來指示該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)在存貯空間中的 位置。 孩子表示法 n方法1 n根據(jù)結(jié)點(diǎn)的度，設(shè)置結(jié)點(diǎn)的指針個(gè)數(shù)，比如若結(jié)點(diǎn) 的度為d: datapChild1pChild2pChildd 問題： n不同的數(shù)據(jù)元素，結(jié)點(diǎn)構(gòu)造不同； n操作不方便 孩子表示法 n方法2_對(duì)方法1的改進(jìn) n按照樹的度定義結(jié)點(diǎn)。若樹的度為d n定義degree，表示該結(jié)點(diǎn)的度，指針 pChild1 pChildm非空，其他為空 datapChild1pChild2pChildddegree 問題： n因d為樹的度，是所有結(jié)點(diǎn)的最大的度，因此 樹中有相當(dāng)部分的指針域?yàn)榭眨速M(fèi)空間。 n有n個(gè)結(jié)點(diǎn)的樹的度為k，空指針

24、域有n(k-1)+1個(gè) 空鏈域 孩子表示法 n有n個(gè)結(jié)點(diǎn)的樹的度為k，空指針域有n(k-1)+1 個(gè)空鏈域 n證明： nn個(gè)結(jié)點(diǎn)的樹，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)雙親， 也就是樹中有n-1個(gè)分支，即有n-1個(gè)鏈域（指針） n而按該結(jié)點(diǎn)定義，n個(gè)結(jié)點(diǎn)總的指針域有：nk個(gè)。 n因此空鏈域： nk (n-1) = n ( k - 1 ) + 1 n一個(gè)靜態(tài)數(shù)組，存放所有的結(jié)點(diǎn) n數(shù)組的每個(gè)數(shù)據(jù)元素，包括兩部分：數(shù)據(jù)元素，指針；指針指向 一個(gè)鏈表，鏈表結(jié)點(diǎn)的數(shù)據(jù)域是一個(gè)整數(shù)，表示該結(jié)點(diǎn)的孩子在 數(shù)組中的位置； n特點(diǎn)： n順序+鏈?zhǔn)酱尜A結(jié)構(gòu)； n找孩子容易，找雙親難； A B C D E F 123 4

25、5 孩子表示法孩子表示法 孩子表示法 n在靜態(tài)數(shù)組的的結(jié)點(diǎn)增加一個(gè)域，表示 該結(jié)點(diǎn)的雙親在該樹組中的位置。 n有利于尋找雙親結(jié)點(diǎn)。 A B C D E F -1 0 0 0 2 2 123 45 孩子表示法_C表示 / 樹的孩子表示法 typedef struct CTNode intnChild;/ 該孩子在順序表中的位置 struct CTNode *pNext; CTNode, *ChildPtr;/ 鏈表結(jié)點(diǎn) typedef struct TElemType data; ChildPtrpFirstChild;/第一個(gè)孩子 CTBox;/ 順序表的數(shù)據(jù)元素 孩子表示法_C表示 type

26、def struct CTBox astNodes MAX_TREE_SIZE ; int n, r;/ 結(jié)點(diǎn)數(shù)和根的位置 CTree;/ 定義整個(gè)順序表 孩子兄弟表示法 n從向下的縱向和橫向描述樹； n考慮定義結(jié)點(diǎn)，除放數(shù)據(jù)元素外，放兩 個(gè)指針，一個(gè)指向該結(jié)點(diǎn)的第一個(gè)孩子， 另一個(gè)指向該結(jié)點(diǎn)的下一個(gè)兄弟； 孩子兄弟表示法 typedef struct CSNode TElemTypedata; struct CSNode *pFirstChild; struct CSNode *pNextSibling; CSNode, *CTree; 該表示方法又稱二叉樹表示法，或二叉鏈表表示法 data

27、pFirstChildpNextSibling 孩子兄弟表示法 A CBD EF 樹和二叉樹的關(guān)系 n若樹采用孩子兄弟表示法，二叉樹采用 二叉鏈表表示，則從存貯結(jié)構(gòu)上看，結(jié) 點(diǎn)定義完全相同。因此，在使用該存貯 結(jié)構(gòu)下，樹和二叉樹是等價(jià)的，樹可以 轉(zhuǎn)化為二叉樹。 npFirstChild pLChild; npNextSibling pRChild; 樹和二叉樹轉(zhuǎn)化例 A CBD EF A B C DE F 樹和二叉樹轉(zhuǎn)化例 A B C DE F A B C ED F 樹和二叉樹轉(zhuǎn)化特征 n從樹轉(zhuǎn)化為二叉樹，前提： n樹采用孩子兄弟表示法； n二叉樹采用二叉鏈表表示法； n從樹轉(zhuǎn)化的二叉樹，一定

28、沒有右子樹 n因?yàn)闃涞母Y(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，其 pNextSibling = NULL ，即二叉樹的pRChild = NULL; n二叉樹不一定能轉(zhuǎn)換為樹 森林和二叉樹的轉(zhuǎn)換 n若樹采用孩子兄弟表示法，二叉樹采用二叉鏈 表表示，則： n任一棵樹，都可以找到唯一的一棵二叉樹和它對(duì)應(yīng)， 而且該二叉樹沒有右子樹。(因此一棵二叉樹，不 一定保證能轉(zhuǎn)換為一棵樹) n若把森林中的第二棵樹的根結(jié)點(diǎn)，看成是第一棵樹 的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則這兩棵樹可以轉(zhuǎn)換為一棵 二叉樹（該二叉樹的右子樹沒有右子樹）。 n依次類推，可以認(rèn)為森林和二叉樹是一一對(duì)應(yīng)的， 從而得到二叉樹和森林的轉(zhuǎn)換規(guī)則 森林和二叉樹的轉(zhuǎn)換 n森林到二

29、叉樹的轉(zhuǎn)換方法： n如果F = T1, T2, Tm是森林，則 B= (root, LB, RB ). n1.若F為空，即m = 0 ， 則B為空樹； n2.若F非空，即m != 0; 則B的根就是ROOT( T1 )； LB是從T1中根結(jié)點(diǎn)的子樹森林F1 = T11, T12, T1m1轉(zhuǎn)換成的二叉樹； RB是森林F = T2, T3, , Tm轉(zhuǎn)換成的二叉樹。 森林到二叉樹的轉(zhuǎn)換_例 A BCD E F G HI J A B C D E F G H I J A B C D E F G H I J 森林和二叉樹的轉(zhuǎn)換 n二叉樹到森林的轉(zhuǎn)換方法： nB= (root, LB, RB ). F

30、= T1, T2, Tm: n1. 若B空，則F為空； n2. 若B非空，則F中T1的根ROOT(T1)就是B的根 root，T1中根結(jié)點(diǎn)的子樹森林F1就是B的LB轉(zhuǎn)換 而成的森林，F(xiàn)中除T1之外其余樹組成的森林 F=(T2, T3, Tm)是由B的RB轉(zhuǎn)換成的森林。 二叉樹到森林的轉(zhuǎn)換_例 A BC DE F H K JI G A BC DE F H K JI G 二叉樹到森林的轉(zhuǎn)換_例 A BC DE F H K JI G A B D EG CF HJ IK 二叉樹到森林的轉(zhuǎn)換_例 A BC DE F H K JI G A B D EG CF HJ IK 遍歷二叉樹遍歷二叉樹 n順序存貯結(jié)

31、構(gòu)：容易 n鏈?zhǔn)酱尜A結(jié)構(gòu)：不容易 A B E C D F 遍歷二叉樹遍歷二叉樹(Traversing Binary Tree) n遍歷：按某條搜索路徑尋訪樹中的每個(gè)結(jié)點(diǎn)， 使每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。 n實(shí)際上也就是把樹中的結(jié)點(diǎn)進(jìn)行一次排隊(duì)。 n也就是要把一個(gè)非線性結(jié)構(gòu)的樹轉(zhuǎn)化為一個(gè)線 性結(jié)構(gòu)； n若二叉樹采用順序存貯結(jié)構(gòu)，沒有問題，因?yàn)?已經(jīng)線性化了； n若二叉樹采用非順序存貯結(jié)構(gòu)，則必須考慮算 法。 遍歷二叉樹遍歷二叉樹 n從樹的定義看：遞歸。 n若有算法M可以遍歷二叉樹T：M(T)，則 M可以描述為： n對(duì)Root( T )訪問； n對(duì)T的左子樹LT，利用方法M訪問：M(L

32、T); n對(duì)T的右子樹RT，利用方法M訪問：M(RT); n因此：可以使用遞歸方法遍歷二叉樹。 遍歷二叉樹遍歷二叉樹 n若以LDR分別表示遍歷左子樹，訪問根結(jié) 點(diǎn)，遍歷右子樹，則可以有方法： nDLR，LDR，LRD，DRL，RDL，RLD n考慮到二叉樹有序： nDLR：先（根）序遍歷； nLDR：中（根）序遍歷； nLRD：后（根）序遍歷； 先序遍歷二叉樹先序遍歷二叉樹 n具體描述：DLR: n若二叉樹為空，則空操作；否則： n1.訪問根結(jié)點(diǎn)； n2.先序遍歷左子樹； n3.先序遍歷右子樹； 中序遍歷二叉樹中序遍歷二叉樹 n具體描述：LDR: n若二叉樹為空，則空操作；否則： n1. 中序

33、遍歷左子樹； n2. 訪問根結(jié)點(diǎn)； n3. 中序遍歷右子樹； 后序遍歷二叉樹后序遍歷二叉樹 n具體描述：LRD: n若二叉樹為空，則空操作；否則： n1. 后序遍歷左子樹； n2. 后序遍歷右子樹； n3. 訪問根結(jié)點(diǎn)； 遍歷二叉樹遍歷二叉樹 DLR：先（根）序遍歷； A B E C D F LDR：中（根）序遍歷； LRD：后（根）序遍歷； A B D G C E F D G B A E C F G D B E F C A G 先序遍歷二叉樹算法先序遍歷二叉樹算法 / 先序遍歷二叉樹 Status PreOrderTraverse( BiTree T, status ( * visit)(T

34、ElemType e) if( T ) if( (*Visit)(T-data ) if( PreOrderTraverse( T-pLChild, visit ) if( PreOrderTraverse( T-pRChild, visit ) return OK; return ERROR; 先序遍歷二叉樹算法先序遍歷二叉樹算法 else return OK; / PreOrderTraverse 中序遍歷二叉樹算法中序遍歷二叉樹算法 / 中序遍歷二叉樹 Status InOrderTraverse( BiTree T, status ( * visit)(TElemType e) if(

35、 T ) if(InOrderTraverse( T-pLChild, visit ) if( (*Visit)(T-data ) if( InOrderTraverse( T-pRChild, visit ) return OK; return ERROR; 中序遍歷二叉樹算法中序遍歷二叉樹算法 else return OK; / InOrderTraverse 后序遍歷二叉樹算法后序遍歷二叉樹算法 / 后序遍歷二叉樹 Status PostOrderTraverse( BiTree T, status (* visit)(TElemType e) if( T ) if( PostOrder

36、Traverse( T-pLChild, visit ) if( PostOrderTraverse( T-pRChild, visit ) if( (*Visit)(T-data ) return OK; return ERROR; 后序遍歷二叉樹算法后序遍歷二叉樹算法 else return OK; / PostOrderTraverse 二叉樹的遍歷過程二叉樹的遍歷過程 - * ab c - - * ab c - *c ba * ab c - * ab c b a 算法分析算法分析 n若不考慮visite()語句，則三種遍歷方法 完全相同。 n是遞歸算法： n樹的定義本身就是遞歸的； n

37、遞歸和棧密切聯(lián)系：遞歸過程實(shí)際就是對(duì)棧 的操作過程 n可以直接通過對(duì)棧的操作，來把遞歸算法寫 為非遞歸算法 算法分析算法分析 n在中序遍歷中，遞歸工作棧： n棧數(shù)據(jù)元素： n語句編號(hào)：函數(shù)返回后，下一條語句的執(zhí)行地址； n入口參數(shù)：BiTree T, 指向（子）樹的指針； n訪問（子）樹執(zhí)行過程： n左子樹-根結(jié)點(diǎn)-右子樹，。，在此過程中，程序 只是做了壓棧操作，直到最左下角的結(jié)點(diǎn)為止。因此最 先被執(zhí)行的是（子）樹的最左下的結(jié)點(diǎn)，該結(jié)點(diǎn)的 pLChild = NULL（否則要繼續(xù)遍歷左子樹），因此當(dāng)棧 的棧頂元素=NULL時(shí)，則該節(jié)點(diǎn)沒有左子樹，此時(shí)訪問 根結(jié)點(diǎn)，即出棧（NULL指針），然后訪

38、問根結(jié)點(diǎn)（棧頂 元素存放的就是根結(jié)點(diǎn)）； n開始訪問右子樹。訪問該子樹的方法同上：入棧pRChild， 再從1開始。當(dāng)該子樹訪問結(jié)束后，當(dāng)前子樹執(zhí)行結(jié)束， 需要繼續(xù)出棧。直到棧空為止。 非遞歸算法非遞歸算法 n初始化棧 n根指針入棧（樹入棧） n若棧非空： n把左子樹入棧，直到最左下角； nNULL指針出棧； n若非空： n（子樹）根指針出棧； n訪問（子樹）根結(jié)點(diǎn)； n把右子樹入棧（此時(shí)采用同一種方法，遍歷右子樹） 非遞歸程序非遞歸程序 / 中序遍歷的非遞歸算法 Status InOrderTraverse( BiTree T, status (*visit)(TElemType e ) I

39、nitStack( S ); Push( S, T );/ 根指針進(jìn)棧 while( ! StackEmpty( S ) while( GetTop( S, p ) /向左，直到最左下角 Pop( S, p );/ NULL退棧 非遞歸程序非遞歸程序 if( !StackEmpty( S) Pop( S, p );/ 根退出 if( ! ( *Visit)(p-data) ) return ERROR; Push( S, p-pRChild ); / if / while return OK; / InOrderTraverse 非遞歸程序非遞歸程序 / 中序遍歷的非遞歸算法 Status I

40、nOrderTraverse( BiTree T, status (*visit)(TElemType e ) InitStack( S ); p = T; while( p | !StackEmpty( S ) if( p )/ 根指針進(jìn)棧，遍歷左子樹 Push( S, p ); p = ppLChild; 非遞歸程序非遞歸程序 else / 根指針出棧，訪問根結(jié)點(diǎn)，遍歷右子樹 Gettop ( S, p ); Pop( S, p ); if( !(*Visit)( p-data) return ERROR; p = p-pRChild;/ 右子樹 / else / while return

41、 OK; / InOrderTraverse 建立樹建立樹 n根據(jù)一個(gè)輸入序列，可以構(gòu)建一棵樹嗎？ n例：先序序列：ABDCEF，則樹=? n根A，B? n加條件：中序序列：DBAECF，則樹： n根A,左？DB,右：ECF nB左根 nC右根 建立樹建立樹 A BC DEF 先序：ABDCEF 后序：DBEFCA A根，其他B和C不等，因此A有兩棵 子樹，B和C為根，且BD為一棵左子 樹，CEF為右子棵。 1。單獨(dú)一個(gè)遍歷序列，無法建立樹（唯一確定一棵樹）； 2。若把樹中終端結(jié)點(diǎn)的信息補(bǔ)上，則可以通過一個(gè)序列 確定一課樹 中序：DBAECF 后序：DBEFCA 根：A 左：DB,右：ECF

42、建立樹算法建立樹算法 / 根據(jù)先序序列，創(chuàng)建一棵二叉樹 Status CreateBiTree( BiTree if( ch = ) T=NULL; else 建立樹算法建立樹算法 if( ! (T=(BiTNode *)malloc(sizeof(BiTNode) exit( OVERFLOW ); T-data = ch; CreateBiTree( T-pLChild ); CreateBiTree( T-pRChild ); return OK; / CreateBiTree; 先序建立樹示例先序建立樹示例 A B C D E G F A B C D E G F A B CD E G

43、F 遍歷二叉樹遍歷二叉樹 遍歷二叉樹，就是按照一定的順序，訪問 結(jié)點(diǎn)，實(shí)際上就是把非線性的樹結(jié)構(gòu)線 性化。 如果在實(shí)際應(yīng)用中，需要反復(fù)執(zhí)行遍歷操 作。就有必要保存這種線性化后的結(jié)果。 方法？ 遍歷二叉樹遍歷二叉樹 n開一個(gè)數(shù)組，保存遍歷的結(jié)果； n增加空間開銷 n元素之間的關(guān)系丟失； n每個(gè)結(jié)點(diǎn)增加（一）兩個(gè)指針域，分別 放遍歷后結(jié)點(diǎn)的直接前驅(qū)和直接后繼元 素 n增加空間開銷 n使用二叉鏈表中原有的空間。 遍歷二叉樹遍歷二叉樹 n二叉鏈表的特點(diǎn)： nn個(gè)結(jié)點(diǎn)的二叉樹中，存在n+1個(gè)空鏈域， 放NULL指針。 n定義結(jié)點(diǎn)： pLChildlTagdataRTag pRChild 遍歷二叉樹遍歷二

44、叉樹 nlTag: n0：表示pLChild指示結(jié)點(diǎn)的左孩子； n1：表示pLChild指示結(jié)點(diǎn)的前驅(qū)； nRtag： n0：表示pLChild指示結(jié)點(diǎn)的右孩子； n1：表示pLChild指示結(jié)點(diǎn)的后繼； 遍歷二叉樹遍歷二叉樹 nC表示： ntypedef enum n nLink,/指針 nThread/線索 nPointerTag; 遍歷二叉樹遍歷二叉樹 ntypedef struct BiThrNode n nTElemTypedata; nStruct BiThrNode *plChild, *pRChild; nPointerTaglTag, Rtag; nBiThrNode, *B

45、iThrTree; 線索二叉樹線索二叉樹 n以BiThrNode為結(jié)點(diǎn)的二叉鏈表作為二叉 樹的存貯結(jié)構(gòu)，叫做線索鏈表； n指向結(jié)點(diǎn)前驅(qū)和后繼的指針，叫做線索； n加上線索的二叉樹，稱謂線索二叉樹 （Threaded Binary Tree） 。 n對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索 二叉樹的過程叫線索化。 線索二叉樹線索二叉樹 A BC D E G F 中序遍歷：D B F E G A C 00A 00BC 1 D00E FG 1 1111 11 01 線索二叉樹線索二叉樹 n為方便，在二叉樹的線索鏈表上增加一 個(gè)頭結(jié)點(diǎn)， n其pLChild指向二叉樹的根結(jié)點(diǎn)，pRChild指 向中序遍歷時(shí)訪

46、問的最后一個(gè)結(jié)點(diǎn)； n二叉樹中序遍歷中的第一個(gè)結(jié)點(diǎn)的pLChild指 向該頭結(jié)點(diǎn)； n二叉樹中序遍歷中的最后一個(gè)結(jié)點(diǎn)的 pRChild指向該頭結(jié)點(diǎn)； 線索二叉樹線索二叉樹 n中序遍歷的特征： n對(duì)任一棵二叉樹（子樹），最先訪問的結(jié)點(diǎn)是該樹 的最左下角的結(jié)點(diǎn)； n所有的非終端結(jié)點(diǎn)，下一個(gè)結(jié)點(diǎn)一定是右子樹的第 一個(gè)被訪問的結(jié)點(diǎn)（右子樹的最左下角的結(jié)點(diǎn)）； n對(duì)任一棵二叉樹（子樹），最后一個(gè)被訪問的結(jié)點(diǎn) 是該樹的最右下角的結(jié)點(diǎn)； n所有的非終端結(jié)點(diǎn)，上一個(gè)結(jié)點(diǎn)一定是左子樹的最 后一個(gè)被訪問的結(jié)點(diǎn)（左子樹的最右下角的結(jié)點(diǎn)）； 線索二叉樹線索二叉樹 n線索化后：任一結(jié)點(diǎn)： n直接前驅(qū)： n若lTag = 0，左子樹的最右下角的結(jié)點(diǎn)； n若lTag = 1, plChild就指向其直接前驅(qū)； n直接后繼： n若RTag = 0，右子樹的最左下角的結(jié)點(diǎn)； n若RTag = 1, pRChild就指向其直接后繼； 線索二叉樹的遍歷線索二叉樹的遍歷 / 遍歷一棵線索二叉樹： Status InOrderTraverse_Thr(BiThrTree T,status (*Visit)(TElemType