數(shù)據(jù)結構教學課件：Chapter Six Tree

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

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

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

4、)其它數(shù)據(jù)元素(一個前驅、 一個后繼)其它數(shù)據(jù)元素(一個前驅、 多個后繼) 樹和線性結構的對比2、二叉樹 (Binary Tree)2.1、二叉樹概念2.2、二叉樹的表示2.3、二叉樹遍歷 (Binary Tree Traversal)2.4、線索化二叉樹 (Threaded Binary Tree)2.5、堆 ( Heap )2.6、樹與森林 (Tree & Forest)2.7、二叉樹的計數(shù)2.8、霍夫曼樹 (Huffman Tree)2.1、二叉樹概念 定義 一棵二叉樹是結點的有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。ABCDEF

5、GHK根結點左子樹右子樹EF2.1、二叉樹概念 5種形態(tài)2.1、二叉樹概念 N個節(jié)點有多少種形態(tài)？2.1、二叉樹概念 N個節(jié)點有多少種形態(tài)？2.1、二叉樹概念兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。2.1、二叉樹概念兩類特殊的二叉樹：完全二叉樹：樹中所含的 n 個結點和滿二叉樹中編號為 1 至 n 的結點一一對應。2.1、二叉樹概念特殊二叉樹的練習：在一棵深度為K的滿二叉樹的總節(jié)點數(shù)目_。在一棵深度為K的完全二叉樹的節(jié)點總數(shù)：最小為為_ ；最大為_ 。2k-1 2k-1 2k-12.1、二叉樹概念二叉樹的性質性質1 若二叉樹的層次從1開始, 則在二叉樹的第 i

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

7、二叉樹中，假定度為2的結點個數(shù)為5個，度為1結點個數(shù)為6個，則葉結點數(shù)為_個。在一棵三叉樹中，度為3的結點數(shù)有2個，度為2的結點數(shù)有1個，度為1的結點數(shù)為2個，那么度為0的結點數(shù)有_個。 5*2+6*1+1-(5+6) =62*3+1*2+2*1+1-(2+1+2) =62.1、二叉樹概念二叉樹的性質性質4 具有n個結點的完全二叉樹的高度為 log2(n) +1證明：設完全二叉樹的高度為h，則有 2h-1 - 1 n 2h- 1 2h-1 n 2h 取對數(shù) h -1 log2(n) 1, 則 i 的雙親為i /2 若2*i= n, 則 i 的左子女為2*i 若2* i +1data=x) re

8、turn bt; /*查找成功返回*/*在bt-lchild為根結點指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-lchild!=NULL) return(Search(bt-lchild,x); /*在bt-rchild為根結點指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-rchild!=NULL) return(Search(bt-rchild,x); return NULL; /*查找失敗返回*/3、二叉樹遍歷的應用統(tǒng)計二叉樹葉子結點的數(shù)目(BinaryTree.cpp)/*開始時，bt為根結點所在鏈結點的指針，返回值為bt的葉子數(shù)*/int CountLeaf2(BiTree bt

9、) if (bt=NULL) return(0); if (bt-lchild=NULL & bt-rchild=NULL) return(1); return( CountLeaf2(bt-lchild) + CountLeaf2(bt-rchild) );3、二叉樹遍歷的應用統(tǒng)計二叉樹深度int Depth (BinaryTree bt ) / 返回二叉樹的深度 int depthval,depthLeft, depthRight; if ( bt = NULL ) depthval = 0; else depthLeft = Depth( bt-lchild ); depthRight=

10、 Depth( bt-rchild ); depthval =1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;3、二叉樹遍歷的應用表達式樣求解 求解 3x2+x-1/x+5 ？ 前綴表達式 +-+*3*xxx/1x5 后綴表達式 3xx*x+1x/-5+ 中綴表達式 3*x*x+x-1/x+5 前綴表達式和后綴表達式分別稱為波蘭式和逆波蘭式，它們在編譯程序中有著非常重要的作用4、線索二叉樹引二叉樹遍歷可以通過遞歸或堆棧實現(xiàn)，究其原因可以發(fā)現(xiàn)是因為二叉樹的鏈是單向的。如果，不用堆棧來實現(xiàn)遍歷，可以有如下方法

11、：三叉表結構二叉表結構+“倒鏈”操作線索二叉樹4、線索二叉樹結構一個具有n個結點的二叉鏈表存儲結構，在2n個指針域中只有n1個指針域是用來存儲結點孩子的地址，而另外n1個指針域存放的都是NULL。 可利用這些空指針域來指示結點在某種遍歷序列中直接前驅和直接后繼的位置信息。這些指向直接前驅結點和指向直接后繼結點的指針被稱為線索(thread)，加了線索的二叉樹稱為線索二叉樹(Threaded Binary Tree) 。4、線索二叉樹結構定義LeftThread = 0, LeftChild為左子女指針LeftThread = 1, LeftChild為前驅線索RightThread = 0,

12、RightChild為右子女指針RightThread = 1, RighrChild為后繼指針教材：ltag LeftThreadrtagRightThread4、線索二叉樹結構圖示4、線索二叉樹帶頭節(jié)點的結構圖示去除2個空置點，設置頭節(jié)點。4、線索二叉樹另一種結構定義增加Pred指針和Succ指針的二叉樹。4、線索二叉樹數(shù)據(jù)結構typedef char datatype;typedef struct BiThrNode datatype data; struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag:1; un

13、signed rtag:1; BiThrNodeType,*BiThrTree;4、線索二叉樹基本操作 建立一棵中序線索二叉樹 在中序線索二叉樹上查找任意結點的中序前驅結點 在中序線索二叉樹上查找任意結點的中序后繼結點 在中序線索二叉樹上查找任意結點在先序下的后繼 在中序線索二叉樹上查找任意結點在后序下的前驅 在中序線索二叉樹上查找值為x的結點 在中序線索二叉樹上的插入 在中序線索二叉樹上的刪除4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp) 建立一棵中序線索二叉樹建立線索二叉樹，實質上就是遍歷一棵二叉樹。在遍歷過程中，訪問結點的操作是檢查當前結點的左、右指針域是否為空，如果為空，將它們

14、改為指向前驅結點或后繼結點的線索。為實現(xiàn)這一過程，設指針pre始終指向剛剛訪問過的結點，即若指針p指向當前結點，則pre指向它的前驅，以便增設線索。4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp)(2)在中序線索二叉樹上查找任意結點的中序前驅結點如果該結點的左標志為1，那么其左指針域所指向的結點便是它的前驅結點；如果該結點的左標志為0，表明該結點有左孩子 ,它的前驅結點是以該結點的左孩子為根結點的子樹的最右結點：while (pre-rtag=0) pre=pre-rchild;4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp)(3) 在中序線索二叉樹上查找任意結點的中序后繼結點 如

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

16、下的第一個結點。4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp)(6) 在中序線索二叉樹上查找值為x的結點利用在中序線索二叉樹上尋找后繼結點和前驅結點的算法，就可以遍歷到二叉樹的所有結點4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp)(7) 在中序線索二叉樹上的插入4、線索二叉樹操作實現(xiàn) (BiThrTree.cpp)(8) 在中序線索二叉樹上的刪除5、霍夫曼樹 (Huffman Tree)定義哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹，是指對于一組帶有確定權值的葉結點，構造的具有最小帶權路徑長度的二叉樹。 路徑長度 (Path Length)：兩個結點之間的路徑長度是連接兩結點的

17、路徑上的分支數(shù)。樹的路徑長度是各結點到根結點的路徑長度之和。5、霍夫曼樹 (Huffman Tree)圖示具有不同路徑長度的二叉樹5、霍夫曼樹 (Huffman Tree)路徑最小值n個結點的二叉樹的路徑長度不小于下述數(shù)列前n項的和，即：其路徑長度最小為：5、霍夫曼樹 (Huffman Tree)帶權路徑長度 ( Weighted Path Length, WPL )樹的帶權路徑長度是樹的各葉結點所帶的權值與該結點到根的路徑長度的乘積的和。27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 545、霍夫曼樹 (Huffm

18、an Tree)帶權路徑長度達到最小的擴充二叉樹即為霍夫曼樹。在霍夫曼樹中，權值大的結點離根最近。如何構造霍夫曼樹 ？5、霍夫曼樹 (Huffman Tree)算法(1) 由給定的n個權值w0, w1, w2, , wn-1，構造具有n棵擴充二叉樹的森林F = T0, T1, T2, , Tn-1，其中每一棵擴充二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。(2) 重復以下步驟, 直到F中僅剩下一棵樹為止： 在F中選取兩棵根結點的權值最小的擴充二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。 在F中刪去這兩棵二叉樹。 把新的

19、二叉樹加入F。5、霍夫曼樹 (Huffman Tree)算法圖示9例如: 已知權值 W= 5, 6, 2, 9, 7 56275276976713952767139527952716671329000011110001111001015、霍夫曼樹 (Huffman Tree)算法實現(xiàn)：設置一個結構數(shù)組HuffNode保存哈夫曼樹中各結點的信息，根據(jù)二叉樹的性質可知，具有n個葉子結點的哈夫曼樹最多2n1個結點。weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數(shù)組HuffNode中的序號。5、霍夫曼樹 (Huffman Tree)算法應用：霍夫曼編碼主要用

20、途是實現(xiàn)數(shù)據(jù)壓縮。 設給出一段報文： 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+7+4+5 ) * 2 = 36. 若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。 因各字符出現(xiàn)的概率為 2/18, 7/18, 4/18, 5/18 。5、霍夫曼樹 (Huffman Tree)算法應用：霍夫曼編碼化整為 2, 7, 4, 5 ，以它們?yōu)楦魅~結點上的權值，建立霍夫曼樹。左分支賦

21、0，右分支賦 1，得霍夫曼編碼(變長編碼)。 A : 0 T : 10 C : 110 S : 111它的總編碼長度：7*1+5*2+( 2+4 )*3 = 35。比等長編碼的情形要短。 總編碼長度正好等于霍夫曼樹的帶權路徑長度WPL。 霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。6、樹樹的4種表示方法(1) 直觀表示法(2) 嵌套集合表示法(3) 凹入表示法(4) 廣義表表示法6、樹樹的4種表示方法(1) 直觀表示法:倒著的分支樹的形式表示 6、樹樹的4種表示方法嵌套集合表示法：根結點視為一個大的集合，其若干棵子樹構成這個大集合中若干個互不相交的子集，如此嵌套下去，即構成一棵樹的嵌套集合表示

22、6、樹樹的4種表示方法(3) 凹入表示法：主要用于樹的屏幕和打印輸出 。6、樹樹的4種表示方法(4) 廣義表表示法：將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將書表示出來。(A,(B(D,E(H,I),F),C(G) 6、樹樹的4種存儲結構(1) 雙親表示法(2) 孩子表示法(3) 雙親孩子表示法(4) 孩子兄弟表示法6、樹樹的4種存儲結構(1) 雙親表示法定義：由樹的定義可知：樹中的每個結點都有唯一的一個雙親結點，根據(jù)這一特性，可用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹中的各個結點，數(shù)組中的一個元素表示樹中的一個結點，數(shù)組元素為結構體類型，其中包括結點本身的信息以及結點的雙親結點在

23、數(shù)組中的序號6、樹樹的4種存儲結構(1) 雙親表示法圖示：6、樹樹的4種存儲結構(1) 雙親表示法數(shù)據(jù)結構： #define MAXNODE typedef struct datatype data; int parent; NodeType; NodeType tMAXNODE;6、樹樹的4種存儲結構(2) 孩子表示法：多重鏈表方法令每個結點包括一個結點信息域和多個指針域，每個指針域指向該結點的一個孩子結點，通過各個指針域值反映出樹中各結點之間的邏輯關系。在這種表示法中，樹中每個結點有多個指針域，形成了多條鏈表，所以這種方法又常稱為多重鏈表法。每個結點的度數(shù)各異,只有兩種可能性：每一個都單獨

24、設置(不現(xiàn)實)；或取最大度數(shù)(樹的度)，但空間浪費。6、樹樹的4種存儲結構(2) 孩子表示法：多重鏈表方法圖示6、樹樹的4種存儲結構(2) 孩子表示法：多重鏈表方法數(shù)據(jù)結構 #define MAXSON typedef struct TreeNode elemtype data; struct TreeNode *sonMAXSON; NodeType;6、樹樹的4種存儲結構(2) 孩子表示法：孩子鏈表方法其主體是一個與結點個數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個元素有兩個域組成，一個域用來存放結點信息，另一個用來存放指針，該指針指向由該結點孩子組成的單鏈表的首位置。單鏈表的結構也由兩個域組成，一

25、個存放孩子結點在一維數(shù)組中的序號，另一個是指針域，指向下一個孩子。6、樹樹的4種存儲結構(2) 孩子表示法：孩子鏈表圖示6、樹樹的4種存儲結構(2) 孩子表示法：孩子鏈表數(shù)據(jù)結構 #define MAXNODE typedef struct ChildNode int childcode; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; NodeType tMAXNODE;6、樹樹的4種存儲結構(3) 雙親孩子鏈表方法 雙親表示法是將雙親表示法和

26、孩子表示法相結合的結果。其仍將各結點的孩子結點分別組成單鏈表，同時用一維數(shù)組順序存儲樹中的各結點，數(shù)組元素除了包括結點本身的信息和該結點的孩子結點鏈表的頭指針之外，還增設一個域，存儲該結點雙親結點在數(shù)組中的序號。6、樹樹的4種存儲結構(3) 雙親孩子鏈表圖示6、樹樹的4種存儲結構(3) 雙親孩子鏈表數(shù)據(jù)結構 #define MAXNODE typedef struct ChildNode int childcode,parent; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *first

27、child; NodeType; NodeType tMAXNODE;6、樹樹的4種存儲結構(4)孩子兄弟鏈表方法在樹中，每個結點除其信息域外，再增加兩個分別指向該結點的第一個孩子結點和下一個兄弟結點的指針。6、樹樹的4種存儲結構(4)孩子兄弟鏈表圖示6、樹樹的4種存儲結構(4)孩子兄弟鏈表數(shù)據(jù)結構 typedef struct TreeNode elemtype data; struct TreeNode *son; struct TreeNode *next; NodeType;7、樹、森林與二叉樹的轉換樹轉換為二叉樹1：樹中所有相鄰兄弟之間加一條連線。7、樹、森林與二叉樹的轉換樹轉換為二叉樹2：樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線。7、樹、森林與二叉樹的轉換樹轉換為二叉樹3：以樹的根結點為軸心，將整棵樹順時針轉動一定的角度，使之結構層次分明。7、樹、森林與二叉樹的轉換