數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Six Tree

1、數(shù)據(jù)結(jié)構(gòu)Chapter Six Tree1、樹和森林的概念n概念n二叉樹 (Binary Tree)n二叉樹的表示n二叉樹遍歷 (Binary Tree Traversal)n線索化二叉樹 (Threaded Binary Tree)n堆 ( Heap )n樹與森林 (Tree & Forest)n二叉樹的計數(shù)n霍夫曼樹 (Huffman Tree)1、樹和森林的概念樹的定義 樹是由n (n 0)個結(jié)點組成的有限集合。如果n = 0，稱為空樹；如果n 0，則 有一個特定的稱之為根(root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)； 除根以外的其它結(jié)點劃分為m (m 0)個互不相交的有限集合T0

2、, T1, , Tm-1，每個集合又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。1、樹和森林的概念樹的特點 (1) 樹的根結(jié)點沒有前驅(qū)結(jié)點，除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點。(2) 樹中所有結(jié)點可以有零個或多個后繼結(jié)點。1、樹和森林的概念n結(jié)點(node)n結(jié)點的度(degree)n分支(branch)結(jié)點n葉(leaf)結(jié)點n子女(child)結(jié)點n雙親(parent)結(jié)點n兄弟(sibling)結(jié)點n祖先(ancestor)結(jié)點n子孫(descendant)結(jié)點n結(jié)點所處層次(level)n樹的高度/深度(de

3、pth)n樹的度(degree)n有序樹n無序樹n森林1、樹和森林的概念樹的定義還可形式化的描述為二元組的形式： T(D，R)其中：D為樹T中結(jié)點的集合，R為樹中結(jié)點之間關(guān)系的集合。當(dāng)樹為空樹時，D；當(dāng)樹T不為空樹時有： DRootDF其中，Root為樹T的根結(jié)點，DF為樹T的根Root的子樹集合。DF可由下式表示： DFD1D2Dm且且DiDj(ij，1im，1jm)當(dāng)樹T中結(jié)點個數(shù)n1時，R；當(dāng)樹T中結(jié)點個數(shù)n1時有：R，i1，2，m。其中，Root為樹T的根結(jié)點，ri是樹T的根結(jié)點Root的子樹Ti的根結(jié)點。1、樹和森林的概念線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素 (無前驅(qū)) 根結(jié)點 (無前驅(qū))

4、最后一個數(shù)據(jù)元素 (無后繼)多個葉子結(jié)點 (無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、 一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、 多個后繼)n 樹和線性結(jié)構(gòu)的對比2、二叉樹 (Binary Tree)n2.1、二叉樹概念n2.2、二叉樹的表示n2.3、二叉樹遍歷 (Binary Tree Traversal)n2.4、線索化二叉樹 (Threaded Binary Tree)n2.5、堆 ( Heap )n2.6、樹與森林 (Tree & Forest)n2.7、二叉樹的計數(shù)n2.8、霍夫曼樹 (Huffman Tree)2.1、二叉樹概念n 定義 一棵二叉樹是結(jié)點的有限集合，該集合或者為空，或者是由一個根結(jié)

5、點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹EF2.1、二叉樹概念n 5種形態(tài)2.1、二叉樹概念n N個節(jié)點有多少種形態(tài)？2.1、二叉樹概念n N個節(jié)點有多少種形態(tài)？NNCN2*)1/(1 (2.1、二叉樹概念n兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。2.1、二叉樹概念n兩類特殊的二叉樹：完全二叉樹：樹中所含的 n 個結(jié)點和滿二叉樹中編號為 1 至 n 的結(jié)點一一對應(yīng)。2.1、二叉樹概念n特殊二叉樹的練習(xí)：在一棵深度為K的滿二叉樹的總節(jié)點數(shù)目_。在一棵深度為K的完全二叉樹的節(jié)點總數(shù)：最小為為_ ；最大為_ 。2k

6、-1 2k-1 2k-12.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1 個結(jié)點。(i 1) 證明用數(shù)學(xué)歸納法性質(zhì)2 高度為k的二叉樹最多有 2k-1個結(jié)點。(k 1) 證明用求等比級數(shù)前k項和的公式2.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)3 對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2, 則有 n0n21。證明：若設(shè)度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有 2n2 + n1 = n0 + n1 +

7、 n2 - 1 n2 = n0 - 1 n0 = n2 + 1 2.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)3 練習(xí)在一棵二叉樹中，假定度為2的結(jié)點個數(shù)為5個，度為1結(jié)點個數(shù)為6個，則葉結(jié)點數(shù)為_個。在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有_個。 5*2+6*1+1-(5+6) =62*3+1*2+2*1+1-(2+1+2) =62.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)4 具有n個結(jié)點的完全二叉樹的高度為 log2(n) +1證明：設(shè)完全二叉樹的高度為h，則有 2h-1 - 1 n 2h- 1 2h-1 n 2h 取對數(shù) h -1 log2(n

8、) 1, 則 i 的雙親為i /2n 若2*i= n, 則 i 的左子女為2*i 若2* i +1data=x) return bt; /*查找成功返回*/*在bt-lchild為根結(jié)點指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-lchild!=NULL) return(Search(bt-lchild,x); /*在bt-rchild為根結(jié)點指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-rchild!=NULL) return(Search(bt-rchild,x); return NULL; /*查找失敗返回*/3、二叉樹遍歷的應(yīng)用n統(tǒng)計二叉樹葉子結(jié)點的數(shù)目(BinaryTree.c

9、pp)/*開始時，bt為根結(jié)點所在鏈結(jié)點的指針，返回值為bt的葉子數(shù)*/int CountLeaf2(BiTree bt) if (bt=NULL) return(0); if (bt-lchild=NULL & bt-rchild=NULL) return(1); return( CountLeaf2(bt-lchild) + CountLeaf2(bt-rchild) );3、二叉樹遍歷的應(yīng)用n統(tǒng)計二叉樹深度int Depth (BinaryTree bt ) / 返回二叉樹的深度 int depthval,depthLeft, depthRight; if ( bt = NULL ) d

10、epthval = 0; else depthLeft = Depth( bt-lchild ); depthRight= Depth( bt-rchild ); depthval =1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;3、二叉樹遍歷的應(yīng)用n表達(dá)式樣求解 求解 3x2+x-1/x+5 ？ 前綴表達(dá)式 +-+*3*xxx/1x5 后綴表達(dá)式 3xx*x+1x/-5+ 中綴表達(dá)式 3*x*x+x-1/x+5 前綴表達(dá)式和后綴表達(dá)式分別稱為波蘭式和逆波蘭式，它們在編譯程序中有著非常重要的作用4、線索

11、二叉樹n引二叉樹遍歷可以通過遞歸或堆棧實現(xiàn)，究其原因可以發(fā)現(xiàn)是因為二叉樹的鏈?zhǔn)菃蜗虻?。如果，不用堆棧來實現(xiàn)遍歷，可以有如下方法： 三叉表結(jié)構(gòu) 二叉表結(jié)構(gòu)+“倒鏈”操作 線索二叉樹4、線索二叉樹n結(jié)構(gòu)一個具有n個結(jié)點的二叉鏈表存儲結(jié)構(gòu)，在2n個指針域中只有n1個指針域是用來存儲結(jié)點孩子的地址，而另外n1個指針域存放的都是NULL。 可利用這些空指針域來指示結(jié)點在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息。這些指向直接前驅(qū)結(jié)點和指向直接后繼結(jié)點的指針被稱為線索(thread)，加了線索的二叉樹稱為線索二叉樹 。4、線索二叉樹n結(jié)構(gòu)定義LeftThread = 0, LeftChild為左子女指針為

12、左子女指針LeftThread = 1, LeftChild為前驅(qū)線索為前驅(qū)線索RightThread = 0, RightChild為右子女指針為右子女指針RightThread = 1, RighrChild為后繼指針為后繼指針教材：ltag LeftThreadrtagRightThread4、線索二叉樹n結(jié)構(gòu)圖示4、線索二叉樹n帶頭節(jié)點的結(jié)構(gòu)圖示去除2個空置點，設(shè)置頭節(jié)點。4、線索二叉樹n另一種結(jié)構(gòu)定義增加Pred指針和Succ指針的二叉樹。4、線索二叉樹n數(shù)據(jù)結(jié)構(gòu)typedef char datatype;typedef struct BiThrNode datatype data;

13、 struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag:1; unsigned rtag:1; BiThrNodeType,*BiThrTree;4、線索二叉樹n基本操作(1) 建立一棵中序線索二叉樹(2) 在中序線索二叉樹上查找任意結(jié)點的中序前驅(qū)結(jié)點(3) 在中序線索二叉樹上查找任意結(jié)點的中序后繼結(jié)點(4) 在中序線索二叉樹上查找任意結(jié)點在先序下的后繼(5) 在中序線索二叉樹上查找任意結(jié)點在后序下的前驅(qū)(6) 在中序線索二叉樹上查找值為x的結(jié)點(7) 在中序線索二叉樹上的插入(8) 在中序線索二叉樹上的刪除4、線索

14、二叉樹n操作實現(xiàn) (BiThrTree.cpp)(1) 建立一棵中序線索二叉樹建立線索二叉樹，實質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點的操作是檢查當(dāng)前結(jié)點的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索。為實現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點，即若指針p指向當(dāng)前結(jié)點，則pre指向它的前驅(qū)，以便增設(shè)線索。4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(2)在中序線索二叉樹上查找任意結(jié)點的中序前驅(qū)結(jié)點如果該結(jié)點的左標(biāo)志為1，那么其左指針域所指向的結(jié)點便是它的前驅(qū)結(jié)點；如果該結(jié)點的左標(biāo)志為0，表明該結(jié)點有左孩子 ,它的前驅(qū)結(jié)點是以該結(jié)點的左孩子

15、為根結(jié)點的子樹的最右結(jié)點：while (pre-rtag=0) pre=pre-rchild;4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(3) 在中序線索二叉樹上查找任意結(jié)點的中序后繼結(jié)點 如果該結(jié)點的右標(biāo)志為1，那么其右指針域所指向的結(jié)點 便是它的后繼結(jié)點；如果該結(jié)點的右標(biāo)志為0，表明該結(jié) 點有右孩子，它的前驅(qū)結(jié)點是以該結(jié)點的右孩子為根結(jié)點 的子樹的最左結(jié)點 : while (post-rtag=0) post=post-lchild;4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(4) 在中序線索二叉樹上查找任意結(jié)點在先序下的后繼若一個結(jié)點是某子樹在中序下的最后一個

16、結(jié)點，則它必是該子樹在先序下的最后一個結(jié)點4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(5) 在中序線索二叉樹上查找任意結(jié)點在后序下的前驅(qū)若一個結(jié)點是某子樹在中序下的第一個結(jié)點，則它必是該子樹在后序下的第一個結(jié)點。4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(6) 在中序線索二叉樹上查找值為x的結(jié)點利用在中序線索二叉樹上尋找后繼結(jié)點和前驅(qū)結(jié)點的算法，就可以遍歷到二叉樹的所有結(jié)點4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(7) 在中序線索二叉樹上的插入4、線索二叉樹n操作實現(xiàn) (BiThrTree.cpp)(8) 在中序線索二叉樹上的刪除5、霍夫曼樹 (Hu

17、ffman Tree)n定義哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹，是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。 路徑長度 (Path Length)：兩個結(jié)點之間的路徑長度是連接兩結(jié)點的路徑上的分支數(shù)。樹的路徑長度是各結(jié)點到根結(jié)點的路徑長度之和。5、霍夫曼樹 (Huffman Tree)n圖示具有不同路徑長度的二叉樹5、霍夫曼樹 (Huffman Tree)n路徑最小值n個結(jié)點的二叉樹的路徑長度不小于下述數(shù)列前n項的和，即：其路徑長度最小為：1021)(logniiPL1021)(logniiPL3322221105、霍夫曼樹 (Huffman Tree)n帶權(quán)

18、路徑長度 ( Weighted Path Length, WPL )樹的帶權(quán)路徑長度是樹的各葉結(jié)點所帶的權(quán)值與該結(jié)點到根的路徑長度的乘積的和。10niiilwWPL27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 545、霍夫曼樹 (Huffman Tree)帶權(quán)路徑長度達(dá)到最小的擴(kuò)充二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點離根最近。如何構(gòu)造霍夫曼樹 ？5、霍夫曼樹 (Huffman Tree)n算法(1) 由給定的n個權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有n棵擴(kuò)充二叉樹的森林F = T0, T1,

19、T2, , Tn-1，其中每一棵擴(kuò)充二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空。(2) 重復(fù)以下步驟, 直到F中僅剩下一棵樹為止： 在F中選取兩棵根結(jié)點的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。 在F中刪去這兩棵二叉樹。 把新的二叉樹加入F。5、霍夫曼樹 (Huffman Tree)n算法圖示9例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 56275276976713952767139527952716671329000011110001111001015、霍夫曼樹 (Huffman Tree)

20、n算法實現(xiàn)：設(shè)置一個結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹最多2n1個結(jié)點。weight域保存結(jié)點的權(quán)值，lchild和rchild域分別保存該結(jié)點的左、右孩子結(jié)點在數(shù)組HuffNode中的序號。5、霍夫曼樹 (Huffman Tree)n算法應(yīng)用：主要用途是實現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各個字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 。 若給每個字符以等長編碼 A : 00 T : 10 C : 01 S : 11則總編碼長度為 ( 2

21、+7+4+5 ) * 2 = 36. 若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。 因各字符出現(xiàn)的概率為 2/18, 7/18, 4/18, 5/18 。5、霍夫曼樹 (Huffman Tree)n算法應(yīng)用：化整為 2, 7, 4, 5 ，以它們?yōu)楦魅~結(jié)點上的權(quán)值，建立霍夫曼樹。左分支賦 0，右分支賦 1，得霍夫曼編碼(變長編碼)。 A : 0 T : 10 C : 110 S : 111它的總編碼長度：7*1+5*2+( 2+4 )*3 = 35。比等長編碼的情形要短。 總編碼長度正好等于霍夫曼樹的帶權(quán)路徑長度WPL。 霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。6、樹n

22、樹的4種表示方法(1) 直觀表示法(2) 嵌套集合表示法(3) 凹入表示法(4) 廣義表表示法6、樹n樹的4種表示方法(1) 直觀表示法:倒著的分支樹的形式表示 6、樹n樹的4種表示方法(2) 嵌套集合表示法：根結(jié)點視為一個大的集合，其若干棵子樹構(gòu)成這個大集合中若干個互不相交的子集，如此嵌套下去，即構(gòu)成一棵樹的嵌套集合表示6、樹n樹的4種表示方法(3) 凹入表示法：主要用于樹的屏幕和打印輸出 。6、樹n樹的4種表示方法(4) 廣義表表示法：將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將書表示出來。(A,(B(D,E(H,I),F),C(G) 6、樹n樹的4種存儲結(jié)構(gòu)(1) 雙親表示法

23、(2) 孩子表示法(3) 雙親孩子表示法(4) 孩子兄弟表示法6、樹n樹的4種存儲結(jié)構(gòu)(1) 雙親表示法定義：由樹的定義可知：樹中的每個結(jié)點都有唯一的一個雙親結(jié)點，根據(jù)這一特性，可用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹中的各個結(jié)點，數(shù)組中的一個元素表示樹中的一個結(jié)點，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點本身的信息以及結(jié)點的雙親結(jié)點在數(shù)組中的序號6、樹n樹的4種存儲結(jié)構(gòu)(1) 雙親表示法圖示：6、樹n樹的4種存儲結(jié)構(gòu)(1) 雙親表示法數(shù)據(jù)結(jié)構(gòu)： #define MAXNODE typedef struct datatype data; int parent; NodeType; NodeType

24、tMAXNODE;6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法令每個結(jié)點包括一個結(jié)點信息域和多個指針域，每個指針域指向該結(jié)點的一個孩子結(jié)點，通過各個指針域值反映出樹中各結(jié)點之間的邏輯關(guān)系。在這種表示法中，樹中每個結(jié)點有多個指針域，形成了多條鏈表，所以這種方法又常稱為多重鏈表法。每個結(jié)點的度數(shù)各異,只有兩種可能性：每一個都單獨設(shè)置(不現(xiàn)實)；或取最大度數(shù)(樹的度)，但空間浪費。6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法圖示6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法數(shù)據(jù)結(jié)構(gòu) #define MAXSON typedef struct TreeNode ele

25、mtype data; struct TreeNode *sonMAXSON; NodeType;6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：孩子鏈表方法其主體是一個與結(jié)點個數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個元素有兩個域組成，一個域用來存放結(jié)點信息，另一個用來存放指針，該指針指向由該結(jié)點孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個域組成，一個存放孩子結(jié)點在一維數(shù)組中的序號，另一個是指針域，指向下一個孩子。6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：孩子鏈表圖示6、樹n樹的4種存儲結(jié)構(gòu)(2) 孩子表示法：孩子鏈表數(shù)據(jù)結(jié)構(gòu) #define MAXNODE typedef struct Child

26、Node int childcode; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; NodeType tMAXNODE;6、樹n樹的4種存儲結(jié)構(gòu)(3) 雙親孩子鏈表方法 雙親表示法是將雙親表示法和孩子表示法相結(jié)合的結(jié)果。其仍將各結(jié)點的孩子結(jié)點分別組成單鏈表，同時用一維數(shù)組順序存儲樹中的各結(jié)點，數(shù)組元素除了包括結(jié)點本身的信息和該結(jié)點的孩子結(jié)點鏈表的頭指針之外，還增設(shè)一個域，存儲該結(jié)點雙親結(jié)點在數(shù)組中的序號。6、樹n樹的4種存儲結(jié)構(gòu)(3) 雙親孩

27、子鏈表圖示6、樹n樹的4種存儲結(jié)構(gòu)(3) 雙親孩子鏈表數(shù)據(jù)結(jié)構(gòu) #define MAXNODE typedef struct ChildNode int childcode,parent; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; NodeType tMAXNODE;6、樹n樹的4種存儲結(jié)構(gòu)(4)孩子兄弟鏈表方法在樹中，每個結(jié)點除其信息域外，再增加兩個分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點的指針。6、樹n樹的4種存儲結(jié)構(gòu)(4)孩子兄

28、弟鏈表圖示6、樹n樹的4種存儲結(jié)構(gòu)(4)孩子兄弟鏈表數(shù)據(jù)結(jié)構(gòu) typedef struct TreeNode elemtype data; struct TreeNode *son; struct TreeNode *next; NodeType;7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹1：樹中所有相鄰兄弟之間加一條連線。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹2：樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其它孩子結(jié)點之間的連線。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹3：以樹的根結(jié)點為軸心，將整棵樹順時針轉(zhuǎn)動一定的角度，使之結(jié)構(gòu)層次分明。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹分析1： 可以證明，樹