數(shù)據(jù)結構張華娣師樹與二叉樹PPT課件

1、 6.4.3樹和森林的遍歷 6.5 赫夫曼樹及其應用 6.5.1 最優(yōu)二叉樹（赫夫曼樹） 6.5.2 赫夫曼編碼學習綱要第1頁/共147頁ACGBDE FK LHMIJ 非線性結構 該結構中至少存在一個數(shù)據(jù)元素，有兩個或兩個以上的直接前驅或直接后繼.如： 樹型結構、圖型結構 樹型結構是一類重要的非線性結構。 是結點之間有分支，并且具有層次關系的結構。（直觀來看） 樹型結構的邏輯特征 樹中任一結點都可以有零個或多個后繼結點，但至多只能有一個前趨結點，只有根結點無前趨，葉子結點無后繼。 最為常用的樹型結構 樹 二叉樹6.1 樹的定義和基本術語第2頁/共147頁6.1 樹的基本概念及相關術語 一、樹

2、的定義 定義：樹(Tree)是n(n=0)個結點的有限集T，n=0時稱為空樹，否則對任意一棵非空樹，它滿足如下兩個條件：6.1 樹的定義和基本術語ACGBDE FKLHMIJ（1）有且僅有一個特定的稱為根(Root)的結點； (2)其余的結點可分為m(m0)個互不相交的子集T1,T2,T3Tm，其中每個子集又是一棵樹，并稱其為根的子樹(Subtree)。樹的定義是采用遞歸方法第3頁/共147頁6.1 樹的定義和基本術語(a) 一棵樹結構 (b)一個非樹結構 (c)一個非樹結構 一、樹的定義ACBGFEDHIACBGFDACBGFDE第4頁/共147頁6.1 樹的定義和基本術語樹的應用舉例文件結

3、構My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic第5頁/共147頁6.1 樹的定義和基本術語ACGBDEFKLHMIJ二、樹的特點第6頁/共147頁6.1 樹的定義和基本術語三、樹的基本術語結點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支結點的度：結點所擁有的子樹的個數(shù)。樹的度：樹中各結點度的最大值。CGBDEFKLHMIJA第7頁/共147頁6.1 樹的定義和基本術語三、樹的基本術語葉子結點：度為0的結點，也稱為終端結點。分支結點：度不為0的結點，也稱為非終端結點。CGBDEFKLHMIJA第8頁/共147頁6.1 樹的定義和基本術語三、

4、樹的基本術語孩子、雙親：樹中某結點子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；兄弟：具有同一個雙親的孩子結點互稱為兄弟。 CGBDEFKLHMIJA第9頁/共147頁6.1 樹的定義和基本術語三、樹的基本術語路徑：如果樹的結點序列n1, n2, , nk有如下關系：結點ni是ni+1的雙親（1=i=0)個結點的有限集合，此集合或者為空集（n=0），或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。123485679 10第19頁/共147頁6.2 6.2 二叉樹二叉樹 二、二叉樹的特點 1.每個結點至多只有二棵子樹（即二叉樹中不存在度大于2的結點)

5、; 2.該兩棵子樹可以為空; 3.該兩棵子樹有次序之分，分別稱之為左子樹和右子樹,其次序不能任意顛倒。123485679 10ABAB第20頁/共147頁6.2 6.2 二叉樹二叉樹 (a)空二叉樹空二叉樹 (b)僅有根結僅有根結點的二叉點的二叉樹樹 (c)右子樹為右子樹為空的二叉空的二叉樹樹L (d)左子樹為空的二叉樹R (e)左、右子樹均非左、右子樹均非空的二叉樹空的二叉樹LR三、二叉樹的基本形態(tài)第21頁/共147頁6.2 6.2 二叉樹二叉樹a ab bc cd de e(a)a ac cd de eb b(b)b bc cd de ea a(c)四、二叉樹與樹和有序樹的區(qū)別第22頁/共

6、147頁a ac cd de eb b(b)6.2 6.2 二叉樹二叉樹二叉樹與樹的區(qū)別：A樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為2。B樹的每個結點的子樹無左、右之分，二叉樹的結點子樹有明確的左、右之分。二叉樹與有序樹的區(qū)別：C.在有序樹中，某個結點只有一個孩子時就無左、右之分 特別要注意：二叉樹不是樹的特殊情況，它們是兩種不同的樹型結構。四、二叉樹與樹和有序樹的區(qū)別a ab bc cd de e(a)第23頁/共147頁練習：畫出含有3個結點（非空）的樹與二叉樹的所有不同形態(tài) 樹 二叉樹第24頁/共147頁6.2 二叉樹特殊的二叉樹斜樹1 . .所有結點都只有左子樹的二叉樹稱為左斜

7、樹2 . .所有結點都只有右子樹的二叉樹稱為右斜樹3.3.左斜樹和右斜樹統(tǒng)稱為斜樹。1. 在斜樹中，每一層只有一個結點；2. .斜樹的結點個數(shù)與其深度相同。 斜樹的特點：ABCABC第25頁/共147頁滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。 特點：6.2 二叉樹123485679 1011 1213 1415特殊的二叉樹特殊的二叉樹1. 葉子只能出現(xiàn)在最下一層；葉子只能出現(xiàn)在最下一層；2. 只有度為只有度為0和度為和度為2的結點。的結點。第26頁/共147頁6.2 二叉樹特殊的二叉樹特殊的二叉樹不是滿二叉樹，雖然

8、不是滿二叉樹，雖然所有分支結點都有左所有分支結點都有左右子樹，但葉子不在右子樹，但葉子不在同一層上。同一層上。滿二叉樹在同樣深度的二叉樹中結點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結點個數(shù)最多A1523467BCDEFGLM89第27頁/共147頁6.2 二叉樹 -深度為k的，有n個結點的二叉樹，當且僅當每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹（也稱為近似滿二叉樹） 完全二叉樹123485679 10特點：（1 1）葉子結點只可能在層次最大的兩層上出現(xiàn) （2 2）對任一結點，若其右分支下的子孫最大層次為L L，則其左分支下的子孫最大層次必為L L或L+1

9、L+1特殊的二叉樹特殊的二叉樹123485679 10 111213 1415第28頁/共147頁12345612345721367(a)完全二叉樹(b)非完全二叉樹( c)非完全二叉樹滿二叉樹是完全二叉樹的特例。滿二叉樹是完全二叉樹的特例。6.2 二叉樹特殊的二叉樹特殊的二叉樹第29頁/共147頁由此可得出如下結論：對一棵完全二叉樹，有：1.至多只有最下面兩層上結點的度數(shù)可以小于22.最下面一層結點都集中在該層的最左邊3.滿二叉樹是完全二叉樹，反之不然，在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。123485679 106.2 二叉樹特殊的二叉樹特殊的二叉樹

10、第30頁/共147頁第31頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 性質1： 在二叉樹的第i層上至多有2i-1個結點(i=1)。第三層上(i=3)(i=3)，有2 23-13-1=4=4個結點。第四層上(i=4)(i=4)，有2 24-14-1=8=8個結點。第32頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 性質2：深度為k的二叉樹至多有2k1個結點（k=1)）.第33頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質性質3： 對任何一棵二叉樹，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0n21。第34頁/共147頁6.2.2 6.

11、2.2 二叉樹的性質二叉樹的性質 性質4：具有n個結點的完全二叉樹的深度為 符號 表示不大于x的最大整數(shù)。1log2n x123485679 10413110log2K完全二叉樹的兩個重要特性第35頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 性質5： 如果對一棵有n個結點的完全二叉樹的結點按層次編號,則對編號為i的結點（1=i1，則其雙親是結點。 （2）如果2in，則結點i為葉子結點，無左孩子； 否則，其左孩子是結點。 （3）如果2i1n， 則結點i無右孩子 否則，其右孩子是結點。123485679 10完全二叉樹的兩個重要特性性質5表明，在完全二叉樹中，結點的層序編號反映

12、了結點之間的邏輯關系。第36頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1完全二叉樹中結點i和i+1(a)i和i+1結點在同一層 (b)i和i+1結點不在同一層如圖所示為完全二叉樹上結點及其左右子如圖所示為完全二叉樹上結點及其左右子樹在結點之間的關系。樹在結點之間的關系。第37頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 在此過程中，可以從（2）和（3）推出（1），所以先證明（2）和（3）。 對于i1，由完全二叉樹的定義，其左孩子是結點2，若2n，即不存在結點2，此是，結點

13、i無孩子。結點i的右孩子也只能是結點3，若結點3不存在，即3n，此時結點i無右孩子。 對于i1，可分為兩種情況： （1）設第j（1=jn，則無左孩子：第38頁/共147頁6.2.2 6.2.2 二叉樹的性質二叉樹的性質 其右孩子必定為第j1層的第二個結點，編號為2i1。若2i+1n，則無右孩子。 （2）假設第j（1=j=log2n)層上的某個結點編號為i（2j-1=i= 2j -1),且2i11時，如果i為左孩子，即2（i/2)=i,則i/2是i的雙親；如果i為右孩子，i2p+1,i的雙親應為p，p（i1）/2=i/2. 證畢。第39頁/共147頁6.2.3 二叉樹的存儲結構順序存儲結構二叉樹

14、的順序存儲結構就是用一組連續(xù)的存儲單元存儲二叉樹中的結點，并且結點的存儲位置（下標）應能體現(xiàn)結點之間的邏輯關系 如何利用數(shù)組下標來反映結點之間的邏輯關系? ?完全二叉樹和滿二叉樹中結點的序號可以惟一地反映出結點之間的邏輯關系 。二叉樹的邏輯關系父子關系。 第40頁/共147頁6.2.3 二叉樹的存儲結構 A B C D E F G H I J數(shù)組下標 1 2 3 4 5 6 7 8 9 10完全二叉樹的順序存儲CDEFGHIJ以編號為下標第41頁/共147頁6.2.3 二叉樹的存儲結構二叉樹的順序存儲ABC DE F G數(shù)組下標 1 2 3 4 5 6 7 8 9 1

15、0 11 12 13ABCDEGF以編號為下標ABCDEGF123561013按照完全二叉樹編號第42頁/共147頁6.2.3 二叉樹的存儲結構一棵斜樹的順序存儲會怎樣呢？深度為k的右斜樹，k個結點需分配2k1個存儲單元。 一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結點，造成存儲空間的浪費。二叉樹的順序存儲結構一般僅存儲完全二叉樹ABC137D15第43頁/共147頁6.2.3 二叉樹的存儲結構二叉鏈表基本思想：令二叉樹的每個結點對應一個鏈表結點，鏈表結點除了存放與二叉樹結點有關的數(shù)據(jù)信息外，還要設置指示左右孩子的指針。 第44頁/共147頁二叉樹的鏈表表示lChild data rChi

16、lddatalChildrChild每個結點由數(shù)據(jù)域、左指針域和右指針域組成。二叉鏈表其中，data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息； lchild：左指針域，存放指向左孩子的指針； rchild：右指針域，存放指向右孩子的指針。 結點結構第45頁/共147頁6.2.3 二叉樹的存儲結構GFEDBAABCDEFGC二叉鏈表具有n個結點的二叉鏈表中，有多少個空指針？n+1個第46頁/共147頁6.2.3 二叉樹的存儲結構ABCDEFGGFEDBAC在二叉鏈表中，如何求某結點的雙親？二叉鏈表第47頁/共147頁6.2.3 二叉樹的存儲結構leftChild data parent rightChil

17、dparentdataleftChildrightChild三叉鏈表三叉鏈表 在二叉鏈表的基礎上增加了一個指向雙親的指針域。第48頁/共147頁6.2.3 二叉樹的存儲結構ABCDEFGABDEFCG三叉鏈表第49頁/共147頁6.2.3 二叉樹的存儲結構 在二叉鏈表這種存儲結構上，二叉樹的多數(shù)基本運算如求根、求左、右孩子等很容易實現(xiàn)。但求雙親運算的實現(xiàn)比較麻煩，而且其時間性能較低 空間利用不高，在含有n個結點的二叉鏈表中有n+1個空鏈域， 三叉鏈表 優(yōu)點： 求雙親運算很容易實現(xiàn)，且時間性能很好二叉鏈表與三叉鏈表的比較第50頁/共147頁6.2.3 二叉樹的存儲結構typedef struct

18、 BiTNode /樹結點定義 ElemType data; /結點數(shù)據(jù)域 struct BiTNode *lChild, *rChild; /左右孩子指針左右孩子指針 BiTNode ,*BiTree;datalChildrChild第51頁/共147頁二叉樹存儲結構課堂練習 練習 分別畫出下圖所示二叉樹的二叉鏈表、三叉鏈表和順序存儲結構示意圖ABECFD第52頁/共147頁6.3 遍歷二叉樹和線索二叉樹 6.3.1遍歷二叉樹 二叉樹的遍歷是指從根結點出發(fā)，按照某種次序訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結果？非線性結構線性化抽象操作，可以是對結點進

19、行的各種處理，這里簡化為輸出結點的數(shù)據(jù)。第53頁/共147頁6.3.16.3.1遍歷二叉樹遍歷二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹(右子樹)(根結點)(左子樹)DLR考慮二叉樹的組成：二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，則二叉樹遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結點。 第54頁/共147頁6.3.1遍歷二叉樹- -/ /+ +* *abcdef.（前綴表示波蘭式）先序遍歷 (Preorder Traversal)(Preorder Traversal)第55頁

20、/共147頁6.3.1遍歷二叉樹void PreOrder (BiTNode *T) if (T = = NULL) return error; /遞歸調用的結束條件 visit (T-data); PreOrder (T-lChild); PreOrder (T-rChild);二叉樹遞歸的先序遍歷算法第56頁/共147頁6.3.1遍歷二叉樹- -/ /+ +* *abcdef.（中綴表示）中序遍歷 (Inorder Traversal)第57頁/共147頁6.3.1遍歷二叉樹void InOrder (BiTNode *T) if (T != NULL) InOrder (T-lChild

21、); visit (T-data); InOrder (T-rChild); 第58頁/共147頁6.3.1遍歷二叉樹.(后綴表示逆波蘭式)后序遍歷 (Postorder Traversal)- -/ /+ +* *abcdef第59頁/共147頁6.3.1遍歷二叉樹void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lChild); PostOrder (T-rChild); visit (T-data); 二叉樹遞歸的后序遍歷算法第60頁/共147頁AB1111111112222222223333先序序列：A B D E A B

22、D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.1遍歷二叉樹第61頁/共147頁6.3.1遍歷二叉樹BEAFDCGHIJBEAFDCGHIJ先序序列：A B C D A B C D E F G H I JE F G H I J中序序列：B C D B C D A F E H J I GA F E H J I G后序序列：D C B D C B F J I H G E A F J I H G E A 課堂練習二第62頁/共147

23、頁6.3.1遍歷二叉樹層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。 - -/ /+ +* *abcdef遍歷結果：- + / a * e f b c d第63頁/共147頁6.3.1遍歷二叉樹若已知一棵二叉樹的先序（或中序，或后序，或層序）序列，能否惟一確定這棵二叉樹呢？遍歷的性質性質1 1、由一棵二叉樹的先序序列和中序序列可惟一確定這棵二叉樹性質2 2、由一棵二叉樹的后序序列和中序序列可惟一確定這棵二叉樹由遍歷序列恢復二叉樹第64頁/共147頁6.3.1遍歷二叉樹例如，已知一棵二叉樹的中序序列和后序序列分別為B

24、DCEAFHG和DECBHGFA，試畫出這棵二叉樹。BDCEFHGAFHGABDCE由遍歷序列恢復二叉樹第65頁/共147頁FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍歷序列恢復二叉樹中序序列BDCEAFHG 后序序列DECBHGFA6.3.1遍歷二叉樹第66頁/共147頁6.3.1遍歷二叉樹練習三第67頁/共147頁6.3.1遍歷二叉樹HBDFEKCGAEKCGABHDF第68頁/共147頁6.3.1遍歷二叉樹KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG 第69頁/共147頁6.3.1遍歷二叉樹int Height (BiTNode *T)

25、 if (T = NULL) return 0 0; else int m = Height (T-lChild); int n = Height (T-rChild); return (m n) ? m+1 : n+1; 第70頁/共147頁Status CreateBiTree(BiTree &T)Status CreateBiTree(BiTree &T)/建立一棵二叉樹建立一棵二叉樹 scanf(&ch); scanf(&ch); /依次輸入字符，空格字符表示空樹依次輸入字符，空格字符表示空樹 if(ch=) T=NULL;if(ch=) T=NULL;

26、 else else if(!(T=(BiTNode if(!(T=(BiTNode * *)malloc(sizeof(BiTNode) )malloc(sizeof(BiTNode) exit(OVERFLOW); exit(OVERFLOW); T Tdata=ch; data=ch; /生成根結點生成根結點 CreateBiTree(TCreateBiTree(Tlchild); lchild); /構造左子樹構造左子樹 CreateBiTree(TCreateBiTree(Trchildd); rchildd); /構造右子樹構造右子樹 return OK; return OK; 例

27、二：構建一棵二叉樹（使用先序遍歷）6.3.1遍歷二叉樹第71頁/共147頁AB1111111112222222223333先序序列：A B D E A B D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.2二叉樹遍歷的非遞歸實現(xiàn)第72頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn)先序遍歷的定義：1）訪問根結點2）先序遍歷左子樹3）先序遍歷右子樹(右子樹)(根結點)(左子樹)vLRXTPre(T)Pre(t-lchild)Pre

28、(t-rchild). .XLXR(a)(b)第73頁/共147頁6.3.26.3.2二叉樹遍歷的非遞歸實現(xiàn)abcde先序遍歷的定義：1）訪問根結點2）先序遍歷左子樹3）先序遍歷右子樹cdcc訪問訪問a進棧進棧c左進左進b訪問訪問b進棧進棧d左進左進空空退棧退棧d訪問訪問d左進左進空空退棧退棧c訪問訪問c左進左進e訪問訪問e左進左進空空退棧退棧 結束結束第74頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn)void PreOrder(BiTree T) stack S; InitStack(&S); /遞歸工作棧 BiTNode * p = T; Push (&S, NULL);

29、 while (p != NULL) visit(p-data); if (p-rChild != NULL) Push(&S, p-rChild); if (p-lChild != NULL) p = p-lChild; /進左子樹 else Pop(&S, p-rChild); /左子樹空, 進右子樹 第75頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn)abcdebaadaa左空左空退棧退棧訪問訪問左空左空 退棧退棧訪問訪問退棧退棧訪問訪問左空左空ec退棧訪問退棧訪問cc右空右空退棧訪問退棧訪問 棧空結束?？战Y束中序遍歷的定義：1）中序遍歷左子樹2）訪問根結點3）中序遍歷右

30、子樹第76頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn)void InOrder(BiTree T) stack S; InitStack(S); /遞歸工作棧 BiTNode *p = T; /初始化 while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lChild; /根指針進棧，根指針進棧，遍歷左子樹遍歷左子樹 else Pop(S, p); /退棧 visit(p-data); /訪問根結點 p = p-rChild; /遍歷右子樹 第77頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn) 思考：后序遍歷的非遞歸算法第78頁/共147頁6.

31、3.2 線索二叉樹如何保存二叉樹的某種遍歷序列？ 將二叉鏈表中的空指針域指向其前驅結點和后繼結點 當以二叉鏈表作為存儲結構時, ,只能找到結點的左右孩子的信息, ,而不能找到結點的任一序列的前驅與后繼信息, ,這種信息只有在遍歷的動態(tài)過程中才能得到。第79頁/共147頁6.3.2 線索二叉樹線索：將二叉鏈表中的空指針域指向前驅結點和后繼結點的指針被稱為線索；線索化：使二叉鏈表中結點的空鏈域存放其前驅或后繼信息的過程稱為線索化；加上線索的二叉鏈表稱為線索鏈表線索二叉樹：加上線索的二叉樹稱為線索二叉樹。第80頁/共147頁6.3.2 線索二叉樹 ltag lchild data child rta

32、g0: lchild指向該結點的左孩子1: lchild指向該結點的前驅結點0: rchild指向該結點的右孩子1: rchild指向該結點的后繼結點ltag=rtag=結點結構線索鏈表第81頁/共147頁例如下圖（a）是一棵中序線索二叉樹，它的線索鏈表如圖 (b)所示。 （a）n注：不同的遍歷次序注：不同的遍歷次序其得到的線索二叉樹其得到的線索二叉樹也不同也不同( (可分別稱為可分別稱為先序線索二叉樹、中先序線索二叉樹、中序線索二叉樹和后序序線索二叉樹和后序線索二叉樹線索二叉樹) )6.3.2 線索二叉樹第82頁/共147頁線索鏈表preprep(b)6.3.2 線索二叉樹第83頁/共147

33、頁如何在線索二叉樹中找結點的前驅和后繼結點？： 1）樹中所有葉結點的左鏈是線索，因此葉結點的左鏈域直接指向其前驅結點。 2）對于非終端結點，若該結點無左孩子，則其左鏈域為線索，直接指向其前驅結點。若有左孩子，則該結點的前驅為中序遍歷其左子樹時最后訪問的那個結點，即左子樹中最右下的結點為其前驅結點。 1）樹中所有葉結點的右鏈是線索，因此葉結點的右鏈域直接指示該結點的后繼結點。 2）非終端結點若無右孩子，則其右鏈是線索，指向后繼，若有右孩子，則其后繼是中序遍歷其右子樹時訪問的第一個結點，即右子樹中最左下結點 。6.3.2 線索二叉樹第84頁/共147頁線索鏈表preprepT T6.3.2 線索二

34、叉樹第85頁/共147頁如何進行二叉樹的線索化呢？ 線索化的實質是將二叉鏈表中的空指針改為指向結點前驅或后繼的線索，而一個結點的前驅和后繼的信息只有在遍歷時才能得到，因此線索化過程即為在遍歷的過程中修改空指針的過程。6.3.2 線索二叉樹第86頁/共147頁6.4 樹與森林實現(xiàn)樹的存儲結構，關鍵是什么? ?樹中結點之間的邏輯關系是什么? ?思考問題的出發(fā)點：如何表示結點的雙親和孩子如何表示樹中結點之間的邏輯關系。6.4.1 6.4.1 樹的存儲結構父子關系第87頁/共147頁6.4.1 樹的存儲結構雙親表示法基本思想：用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹的各個結點（一般按層序存儲），同時在每

35、個結點中附設一個指示器指示其雙親結點在數(shù)組中的位置。 data parentdata：存儲樹中結點的數(shù)據(jù)信息parent：存儲該結點的雙親在數(shù)組中的下標結點結構： 第88頁/共147頁6.4.1 樹的存儲結構 #define MAXNODE typedef struct PTNode /結點結構 elemtype data; int parent; /雙親位置域 PTNode;PTNode tMAXNODE; data parent樹的雙親表示法實質上是一個靜態(tài)鏈表。雙親表示法第89頁/共147頁6.4.1 樹的存儲結構下標 data parent012345678 A - -1 B 0 C

36、0 D 1 E 1 F 1 G 2 H 2 I 4 雙親表示法ACBHFEDGI優(yōu)點： 實現(xiàn)Parent（t，x）操作 和Root（x）操作很方便不足：求某結點的孩子結點，即實現(xiàn)Child（t，x，i）操作時，則需要查詢整個數(shù)組。不能反映各兄弟結點之間的關系，所以實現(xiàn)RightSibling（t，x）操作也比較困難。第90頁/共147頁6.4.1 樹的存儲結構鏈表中的每個結點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結點的一個孩子結點。 如何確定鏈表中的結點結構？ 方案一：指針域的個數(shù)等于樹的度-同構data child1 child2 childd 其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)

37、信息； child1childd：指針域，指向該結點的孩子。 孩子鏈表表示法第91頁/共147頁6.4.1 樹的存儲結構缺點：浪費空間ACBHFEDGIABCDEFGHI 孩子鏈表表示法第92頁/共147頁6.4.1 樹的存儲結構鏈表中的每個結點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結點的一個孩子結點。 如何確定鏈表中的結點結構？方案二： 指針域的個數(shù)等于該結點的度-異構 data degree child1 child2 childd其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息； degree：度域，存放該結點的度； child1childd：指針域，指向該結點的孩子孩子鏈表表示法第9

38、3頁/共147頁6.4.1 樹的存儲結構缺點：結點結構不一致，操作不方便ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0孩子鏈表表示法第94頁/共147頁6.4.1 樹的存儲結構孩子鏈表表示法基本思想：把每個結點的孩子排列起來，看成是一個線性表，且以單鏈表存儲，則n個結點共有 n 個孩子鏈表。這 n 個單鏈表共有 n 個頭指針，這 n 個頭指針又組成了一個線性表，為了便于進行查找采用順序存儲。最后，將存放 n 個頭指針的數(shù)組和存放n個結點的數(shù)組結合起來，構成孩子鏈表的表頭數(shù)組。 如何確定鏈表中的結點結構？將結點的所有孩子放在一起，構成線性表。第95頁/共147頁6.4.

39、1 樹的存儲結構孩子鏈表表示法ACBHFEDGI012345678下標 data firstchild A B C D E F G H I 12 345 7 68 child next孩子結點data firstchild表頭結點第96頁/共147頁ACBHFEDGI6.4.1 樹的存儲結構雙親孩子表示法012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 第97頁/共147頁6.4.1 樹的存儲結構孩子兄弟表示法(二叉鏈表表示法)ACBHFEDGI某結點的第一個孩子是惟一的某結點的

40、右兄弟是惟一的設置兩個分別指向該結點的第一個孩子和右鄰兄弟的指針 第98頁/共147頁6.4.1 樹的存儲結構類型描述如下：Typedef struct CSNode elemtype data; /結點信息 struct CSNode *firstchild, /指向第一個孩子結點的指針 *nextsibling; /指向下一個兄弟結點的指針 CSNode,*CSTree; /用指向樹的根結點的指針來表示一棵樹結點結構firstchild data nextsiblingdata：數(shù)據(jù)域，存儲該結點的數(shù)據(jù)信息；firstchild：指針域，指向該結點第一個孩子；nextsibling：指針域

41、，指向該結點的右兄弟結點。 孩子兄弟表示法第99頁/共147頁6.4.1 樹的存儲結構孩子兄弟表示法ACBHFEDGI A B C D E F G H I第100頁/共147頁優(yōu)缺點： 可以直接實現(xiàn)樹的大部分操作，如找結點的孩子、兄弟等操作。但對樹結點作Parent操作時需遍歷樹。如果要反復執(zhí)行Parent操作， 則可為每個結點增設一個parent域，這樣就能方便地實現(xiàn)parent(T,x)運算6.4.1 樹的存儲結構第101頁/共147頁6.4.1 樹的存儲結構畫出下列樹的孩子兄弟表示法的結構圖(a)(c)樹二叉樹ABCDEFGA BCED F GAEBCFDG(b)練習第102頁/共147

42、頁 以二叉鏈表為媒介可導出樹與二叉樹之間的對應關系。將樹轉換為二叉樹，這樣，對樹的操作就可以借助二叉樹存儲，利用二叉樹上的操作來實現(xiàn)。6.4.2 樹、森林與二叉樹的轉換第103頁/共147頁6.4.2 樹、森林與二叉樹的轉換方法一：借助二叉鏈表，讓該結點的左分枝指向該結點的第一個孩子，右分枝指向該結點的下一個兄弟。ABCDEFGAEBCFDG第104頁/共147頁 I A B C DE F G H(b) A B CDE G H FI(a)ABEFCDGHI(d)ABCDEFGHI(c)方法二： 在樹中所有的兄弟結點之間加一連線； 對每個結點，除保留與其長子（最左孩子）的連線外，去除該結點與其它

43、孩子之間的聯(lián)線； 以根結點為軸心，將整個樹順時針轉4545度。6.4.2 樹、森林與二叉樹的轉換第一步：在樹中所有的兄弟結點之間加一連線第二步：對每個結點，除保留與其長子（最左孩子）的連線外，去除該結點與其它孩子之間的聯(lián)線；第三步：以根結點為軸心，將整個樹順時針轉45度。第105頁/共147頁6.4.2 樹、森林與二叉樹的轉換 將下列的樹轉換為二叉樹課堂練習第106頁/共147頁6.4.2 樹、森林與二叉樹的轉換 將下列的樹轉換為二叉樹DIABECFGH轉換后的二叉樹課堂練習第107頁/共147頁6.4.2 樹、森林與二叉樹的轉換2. 森林轉換為二叉樹 森林轉換為二叉樹的方法： 逐個轉換 將森

44、林中的每一棵樹分別轉換成二叉樹； 加線 將各二叉樹的根結點視為兄弟用線連起來； 層次調整 以第一棵樹的根結點作為二叉樹的根結點，按順時針方向適當旋轉。第108頁/共147頁ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ6.4.2 樹、森林與二叉樹的轉換將如圖所示的森林轉換為二叉樹第109頁/共147頁ADCBEFHIGJ二、二叉樹轉換成樹、森林二、二叉樹轉換成樹、森林方法一方法一1.二叉樹的根作為森林中第一棵樹的根二叉樹的根作為森林中第一棵樹的根2.二叉樹的左子樹轉換成森林中第一棵樹的子樹二叉樹的左子樹轉換成森林中第一棵樹的子樹森林森林3.二叉樹的右子樹轉換成

45、森林中其它的樹二叉樹的右子樹轉換成森林中其它的樹6.4.2 樹、森林與二叉樹的轉換第110頁/共147頁6.4.2 樹、森林與二叉樹的轉換ADCBEFHIGJEFADCBHIGJADCBEFHIGJ二叉樹轉換為森林第111頁/共147頁方法二1）將結點的左孩子的右孩子、右孩子的右孩子與該結點連接起來2）去掉所有結點與其右孩子的連線EFADCBEFHIGJADCBHIGJ6.4.2 樹、森林與二叉樹的轉換第112頁/共147頁將如圖所示的森林轉換為二叉樹將如圖所示的森林轉換為二叉樹GHIJLNKOMADCBFE6.4.2 樹、森林與二叉樹的轉換課堂練習第113頁/共147頁將如圖所示的森林轉換為

46、二叉樹將如圖所示的森林轉換為二叉樹GHIJLNKOMADCBFEFADBECGHIJLKOMN6.4.2 樹、森林與二叉樹的轉換第114頁/共147頁FADBECGHIJLKOMN最后轉換成的二叉樹最后轉換成的二叉樹第115頁/共147頁6.4.3 樹與森林的遍歷1、先序（根）遍歷樹-先訪問樹根結點n，然后從左到右，依次先序遍歷根的每棵子樹T1,T2,.,Tk 。2、后序（根）遍歷樹-先從左到右，依次對樹的每棵子樹T1,T2,.,Tk進行后序遍歷，最后訪問樹根結點n。 設T以n為樹根，樹根的子樹從左到右依次為T1,T2,.,Tk，那么有：第116頁/共147頁6.4.3 樹與森林的遍歷先根：A

47、 B E F C D G H I 后根：E F B C G H I D A 例如例如,右圖樹右圖樹 AEI B CD E G H FI樹樹ABFCDGH二叉樹二叉樹右圖二叉樹右圖二叉樹先序先序: A B E F C D G H I 中序：中序：E F B C G H I D A先根遍歷樹先根遍歷樹 先序遍歷該樹先序遍歷該樹對應的二叉樹對應的二叉樹后根遍歷樹后根遍歷樹 中序遍歷該樹中序遍歷該樹對應的二叉樹對應的二叉樹第117頁/共147頁6.4.3 樹與森林的遍歷按照樹與森林相互遞歸定義，可推出森林的兩種遍歷方法：一、先序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.訪問森林中第一棵樹的根結點;

48、2.先序遍歷第一棵樹中根結點的子樹森林;3.先序遍歷除去第一棵樹之后剩余的樹構成的森林。二、中序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.中序遍歷森林中第一棵樹的根結點的子樹森林;2.訪問第一棵樹的根結點;3.中序遍歷除去第一棵樹之后剩余的樹構成的森林 第118頁/共147頁6.4.3 樹與森林的遍歷ADCBEFHIGJ先序遍歷序列：先序遍歷序列：A B C D E F G H J I中序遍歷序列：中序遍歷序列：B C D A F E J H I G先序遍歷森林 先序遍歷該森林對應的二叉樹中序遍歷森林 中序遍歷該森林對應的二叉樹ADCBEFHIGJ第119頁/共147頁6.4.3 樹與森林

49、的遍歷總 結 由上述討論可知: 當用二叉鏈表作樹和森林的存儲結構時，樹和森林的先根遍歷（先序）和后根遍歷（中序）可借助二叉樹的先序遍歷和中序遍歷算法來實現(xiàn)第120頁/共147頁相關概念1.1.結點間的路徑長度-從樹中一個結點到另一個結點之間的分支數(shù)目6.5 赫夫曼樹及其應用2.葉子結點的權值-對葉子結點賦予的一個有意義的數(shù)值。 3.3.結點帶權的路徑長度從該根結點到該結點之間的路徑長度與該結點上權值的乘積。2347第121頁/共147頁6.5 赫夫曼樹及其應用4.4.二叉樹的帶權路徑長度（weighted path weighted path length of treelength of t

50、ree）-二叉樹中所有葉子結點的帶權路徑長度之和。WPL= nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度AB CD2347WPL=2*2+3*2+4*2+7*2=32第122頁/共147頁6.5 赫夫曼樹及其應用5.赫夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。例：給定4個葉子結點，其權值分別為2，3，4，7，可以構造出形狀不同的多個二叉樹。 WPL=32 WPL=41 WPL=30234723477423第123頁/共147頁6.5 赫夫曼樹及其應用赫夫曼樹的特點：1. 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。 2. 只有度為

51、0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點. 2347WPL=32 WPL=41 WPL=3023477423第124頁/共147頁6.5 赫夫曼樹及其應用赫夫曼算法基本思想：赫夫曼算法基本思想： 初始化初始化：由給定的：由給定的n n個權值個權值 w w1 1，w w2 2，w wn n 構構造造n n棵只有一個根結點的二叉樹，從而得到一個棵只有一個根結點的二叉樹，從而得到一個二叉樹集合二叉樹集合F F T T1 1，T T2 2，T Tn n ； 選取與合并選取與合并：在：在F F中選取根結點的權值中選取根結點的權值最小最小的的兩棵二叉樹分別作為左、右子樹構造一棵新的兩棵

52、二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；、右子樹根結點的權值之和； 刪除與加入刪除與加入：在：在F F中刪除作為左、右子樹的兩中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到棵二叉樹，并將新建立的二叉樹加入到F F中；中； 重復重復、兩步，當集合、兩步，當集合F F中只剩下一棵二叉中只剩下一棵二叉樹時，這棵二叉樹便是赫夫曼樹。樹時，這棵二叉樹便是赫夫曼樹。 怎樣構造一棵赫夫曼樹呢？第125頁/共147頁第1步：初始化例：給定權值 W2，3，4，5 ，構造赫夫曼樹3524第2步：選取與

53、合并32 5第3步：刪除與加入5432 5赫夫曼樹的構造過程6.5 赫夫曼樹及其應用第126頁/共147頁W2，3，4，5 赫夫曼樹的構造過程重復第2步5432 554 9重復第3步 554 9326.5 赫夫曼樹及其應用第127頁/共147頁W2，3，4，5 赫夫曼樹的構造過程重復第2步重復第3步 554 932 554 932146.5 赫夫曼樹及其應用第128頁/共147頁6.5 赫夫曼樹及其應用 給定權值7，18，3，32，5，26，12，8，構造相應的赫夫曼樹,要求左子樹根結點的權值盡可能地小于右子樹根結點的權值。課堂練習第129頁/共147頁赫夫曼樹的應用-判定樹在解決某些判定問題

54、時，利用赫夫曼樹可以得到最佳判定算法。例1 將學生百分成績按分數(shù)段分級的程序。若學生成績分布是均勻的，可用圖（a)二叉樹結構來實現(xiàn)。 a60 a70 a80 a90 不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個數(shù)據(jù)，則需進行31500次比較。6.5 赫夫曼樹及其應用第130頁/共147頁分數(shù)分數(shù)0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格中等良好 80a90 60a70 不及格優(yōu)秀YNYYYNNN(b) 不及格Y a90 a80 a70 a60 優(yōu)秀中等及格良好YNNN(c)YYY 學生成績分布不是均勻的情況：以

55、比例數(shù)為權構造一棵赫夫曼樹，如（b)判斷樹所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹。輸入10000個數(shù)據(jù)，僅需進行22000次比較。6.5 赫夫曼樹及其應用第131頁/共147頁赫夫曼樹的應用-赫夫曼編碼 利用赫夫曼樹構造通訊中電文編碼例如：要傳輸一個電文：CAS；CAT；SAT；AT;要傳輸?shù)淖址?D=C，A，S，T， ；每個字符出現(xiàn)的頻率是W= 2，4， 2，3， 3 6.5 赫夫曼樹及其應用等長編碼等長編碼：C(000)A(001)S(010)T(011);(100)000001010100000001011100010001011100001011 42位不等長編

56、碼不等長編碼：C(0)A(00)S(1)T(01);(10)000110000011010001100001 24位 無法翻譯前綴編碼：前綴編碼：任一個字符的編碼都不是另一個字符編碼的前綴任一個字符的編碼都不是另一個字符編碼的前綴C(0)A(10)S(110)T(1110);(1111)0101101111010111011111101011101111101110 40位前綴碼第132頁/共147頁6.5 赫夫曼樹及其應用電文總長達到最短的前綴編碼的方法-構造一棵赫夫曼樹（1）用頻率作為葉子結點的權值生成一棵赫夫曼樹，并將對應權值wi的葉子結點注明對應的字符；（2）約定左分支表示字符“0”，

57、右分支表示字符1 則從根結點到每個葉結點所經過的路徑分支組成的0和1的序列便為該結點對應字符的編碼，我們稱之為赫夫曼編碼。求編碼的過程：從葉子結點出發(fā)走一條從葉子到根的路徑求譯碼的過程：從根出發(fā)走一條從根到葉子的路徑怎樣才能使總的串長達到最小呢？第133頁/共147頁例子：要傳輸?shù)碾娢氖荂AS；CAT；SAT；AT要傳輸?shù)淖址?D=C，A，S，T， ；每個字符出現(xiàn)的頻率是W= 2，4， 2，3， 3 各字符編碼是 T ； A C S 00 01 10 110 111上述電文編碼：（32位）1101011101110100001111100001100003342200111T;ACS106

58、14846.5 赫夫曼樹及其應用第134頁/共147頁赫夫曼樹的存儲結構及其算法的實現(xiàn)1. 設置一個數(shù)組huffTree2n-1保存赫夫曼樹中各點的信息，數(shù)組元素的結點結構 ：其存儲結構為：Typedef struct float weight; int lchild,rchild,parent; hufmtree;hufmtree treem;/設patent域不僅是為了使涉及雙親的運算方便，其主要作用是區(qū)分根和非根結點，若parent的值為-1，則表示該結點是無雙親的根結點，否則非根結點。weightweightLchildLchildParentParentrchildrchild結點結構第135頁/共147頁6.5 赫夫曼樹及其應用1. 數(shù)組huffTree初始化，所有元素結點的雙親、左、右孩子都置為- -1；2. 數(shù)組huffTree的前n個元素的權值置給定值wn；3. 進行n- -1次合并 3.1 在二叉樹集合中選取兩個權值最小的根結點，其下標分別為i1, i2； 3.2 將二叉樹i1、i2合并為一棵新的二叉樹k；在上述存儲結構上實現(xiàn)hufmtreehufmtree算法的基本步驟：第136頁/共1