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

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

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

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

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

5、; 2.該兩棵子樹可以為空; 3.該兩棵子樹有次序之分，分別稱之為左子樹和右子樹,其次序不能任意顛倒。123485679 10ABAB第20頁/共147頁6.2 6.2 二叉樹二叉樹 (a)空二叉樹空二叉樹 (b)僅有根結(jié)僅有根結(jié)點的二叉點的二叉樹樹 (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樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。B樹的每個結(jié)點的子樹無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。二叉樹與有序樹的區(qū)別：C.在有序樹中，某個結(jié)點只有一個孩子時就無左、右之分 特別要注意：二叉樹不是樹的特殊情況，它們是兩種不同的樹型結(jié)構(gòu)。四、二叉樹與樹和有序樹的區(qū)別a ab bc cd de e(a)第23頁/共147頁練習(xí)：畫出含有3個結(jié)點（非空）的樹與二叉樹的所有不同形態(tài) 樹 二叉樹第24頁/共147頁6.2 二叉樹特殊的二叉樹斜樹1 . .所有結(jié)點都只有左子樹的二叉樹稱為左斜

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

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

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

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

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

12、了結(jié)點之間的邏輯關(guān)系。第36頁/共147頁6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 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é)點及其左右子樹在結(jié)點之間的關(guān)系。樹在結(jié)點之間的關(guān)系。第37頁/共147頁6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 在此過程中，可以從（2）和（3）推出（1），所以先證明（2）和（3）。 對于i1，由完全二叉樹的定義，其左孩子是結(jié)點2，若2n，即不存在結(jié)點2，此是，結(jié)點

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

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

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

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

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

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

19、行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。第53頁/共147頁6.3.16.3.1遍歷二叉樹遍歷二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹(右子樹)(根結(jié)點)(左子樹)DLR考慮二叉樹的組成：二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，則二叉樹遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結(jié)點。 第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; /遞歸調(diào)用的結(jié)束條件 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 課堂練習(xí)二第62頁/共147

23、頁6.3.1遍歷二叉樹層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。 - -/ /+ +* *abcdef遍歷結(jié)果：- + / a * e f b c d第63頁/共147頁6.3.1遍歷二叉樹若已知一棵二叉樹的先序（或中序，或后序，或?qū)有颍┬蛄校芊裎┮淮_定這棵二叉樹呢？遍歷的性質(zhì)性質(zhì)1 1、由一棵二叉樹的先序序列和中序序列可惟一確定這棵二叉樹性質(zhì)2 2、由一棵二叉樹的后序序列和中序序列可惟一確定這棵二叉樹由遍歷序列恢復(fù)二叉樹第64頁/共147頁6.3.1遍歷二叉樹例如，已知一棵二叉樹的中序序列和后序序列分別為B

24、DCEAFHG和DECBHGFA，試畫出這棵二叉樹。BDCEFHGAFHGABDCE由遍歷序列恢復(fù)二叉樹第65頁/共147頁FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍歷序列恢復(fù)二叉樹中序序列BDCEAFHG 后序序列DECBHGFA6.3.1遍歷二叉樹第66頁/共147頁6.3.1遍歷二叉樹練習(xí)三第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; /生成根結(jié)點生成根結(jié)點 CreateBiTree(TCreateBiTree(Tlchild); lchild); /構(gòu)造左子樹構(gòu)造左子樹 CreateBiTree(TCreateBiTree(Trchildd); rchildd); /構(gòu)造右子樹構(gòu)造右子樹 return OK; return OK; 例

27、二：構(gòu)建一棵二叉樹（使用先序遍歷）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）訪問根結(jié)點2）先序遍歷左子樹3）先序遍歷右子樹(右子樹)(根結(jié)點)(左子樹)vLRXTPre(T)Pre(t-lchild)Pre

28、(t-rchild). .XLXR(a)(b)第73頁/共147頁6.3.26.3.2二叉樹遍歷的非遞歸實現(xiàn)abcde先序遍歷的定義：1）訪問根結(jié)點2）先序遍歷左子樹3）先序遍歷右子樹cdcc訪問訪問a進棧進棧c左進左進b訪問訪問b進棧進棧d左進左進空空退棧退棧d訪問訪問d左進左進空空退棧退棧c訪問訪問c左進左進e訪問訪問e左進左進空空退棧退棧 結(jié)束結(jié)束第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右空右空退棧訪問退棧訪問 棧空結(jié)束?？战Y(jié)束中序遍歷的定義：1）中序遍歷左子樹2）訪問根結(jié)點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); /訪問根結(jié)點 p = p-rChild; /遍歷右子樹 第77頁/共147頁6.3.2二叉樹遍歷的非遞歸實現(xiàn) 思考：后序遍歷的非遞歸算法第78頁/共147頁6.

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

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

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

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

35、個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在數(shù)組中的位置。 data parentdata：存儲樹中結(jié)點的數(shù)據(jù)信息parent：存儲該結(jié)點的雙親在數(shù)組中的下標(biāo)結(jié)點結(jié)構(gòu)： 第88頁/共147頁6.4.1 樹的存儲結(jié)構(gòu) #define MAXNODE typedef struct PTNode /結(jié)點結(jié)構(gòu) elemtype data; int parent; /雙親位置域 PTNode;PTNode tMAXNODE; data parent樹的雙親表示法實質(zhì)上是一個靜態(tài)鏈表。雙親表示法第89頁/共147頁6.4.1 樹的存儲結(jié)構(gòu)下標(biāo) 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）操作很方便不足：求某結(jié)點的孩子結(jié)點，即實現(xiàn)Child（t，x，i）操作時，則需要查詢整個數(shù)組。不能反映各兄弟結(jié)點之間的關(guān)系，所以實現(xiàn)RightSibling（t，x）操作也比較困難。第90頁/共147頁6.4.1 樹的存儲結(jié)構(gòu)鏈表中的每個結(jié)點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結(jié)點的一個孩子結(jié)點。 如何確定鏈表中的結(jié)點結(jié)構(gòu)？ 方案一：指針域的個數(shù)等于樹的度-同構(gòu)data child1 child2 childd 其中：data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)

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

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

39、1 樹的存儲結(jié)構(gòu)孩子鏈表表示法ACBHFEDGI012345678下標(biāo) data firstchild A B C D E F G H I 12 345 7 68 child next孩子結(jié)點data firstchild表頭結(jié)點第96頁/共147頁ACBHFEDGI6.4.1 樹的存儲結(jié)構(gòu)雙親孩子表示法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 樹的存儲結(jié)構(gòu)孩子兄弟表示法(二叉鏈表表示法)ACBHFEDGI某結(jié)點的第一個孩子是惟一的某結(jié)點的

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

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

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

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

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

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

46、二叉樹將如圖所示的森林轉(zhuǎn)換為二叉樹GHIJLNKOMADCBFEFADBECGHIJLKOMN6.4.2 樹、森林與二叉樹的轉(zhuǎn)換第114頁/共147頁FADBECGHIJLKOMN最后轉(zhuǎn)換成的二叉樹最后轉(zhuǎn)換成的二叉樹第115頁/共147頁6.4.3 樹與森林的遍歷1、先序（根）遍歷樹-先訪問樹根結(jié)點n，然后從左到右，依次先序遍歷根的每棵子樹T1,T2,.,Tk 。2、后序（根）遍歷樹-先從左到右，依次對樹的每棵子樹T1,T2,.,Tk進行后序遍歷，最后訪問樹根結(jié)點n。 設(shè)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先根遍歷樹先根遍歷樹 先序遍歷該樹先序遍歷該樹對應(yīng)的二叉樹對應(yīng)的二叉樹后根遍歷樹后根遍歷樹 中序遍歷該樹中序遍歷該樹對應(yīng)的二叉樹對應(yīng)的二叉樹第117頁/共147頁6.4.3 樹與森林的遍歷按照樹與森林相互遞歸定義，可推出森林的兩種遍歷方法：一、先序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.訪問森林中第一棵樹的根結(jié)點;

48、2.先序遍歷第一棵樹中根結(jié)點的子樹森林;3.先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。二、中序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.中序遍歷森林中第一棵樹的根結(jié)點的子樹森林;2.訪問第一棵樹的根結(jié)點;3.中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林 第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先序遍歷森林 先序遍歷該森林對應(yīng)的二叉樹中序遍歷森林 中序遍歷該森林對應(yīng)的二叉樹ADCBEFHIGJ第119頁/共147頁6.4.3 樹與森林

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

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

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

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

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

54、時，利用赫夫曼樹可以得到最佳判定算法。例1 將學(xué)生百分成績按分?jǐn)?shù)段分級的程序。若學(xué)生成績分布是均勻的，可用圖（a)二叉樹結(jié)構(gòu)來實現(xiàn)。 a60 a70 a80 a90 不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個數(shù)據(jù)，則需進行31500次比較。6.5 赫夫曼樹及其應(yīng)用第130頁/共147頁分?jǐn)?shù)分?jǐn)?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 學(xué)生成績分布不是均勻的情況：以

55、比例數(shù)為權(quán)構(gòu)造一棵赫夫曼樹，如（b)判斷樹所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹。輸入10000個數(shù)據(jù)，僅需進行22000次比較。6.5 赫夫曼樹及其應(yīng)用第131頁/共147頁赫夫曼樹的應(yīng)用-赫夫曼編碼 利用赫夫曼樹構(gòu)造通訊中電文編碼例如：要傳輸一個電文：CAS；CAT；SAT；AT;要傳輸?shù)淖址?D=C，A，S，T， ；每個字符出現(xiàn)的頻率是W= 2，4， 2，3， 3 6.5 赫夫曼樹及其應(yīng)用等長編碼等長編碼：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 赫夫曼樹及其應(yīng)用電文總長達到最短的前綴編碼的方法-構(gòu)造一棵赫夫曼樹（1）用頻率作為葉子結(jié)點的權(quán)值生成一棵赫夫曼樹，并將對應(yīng)權(quán)值wi的葉子結(jié)點注明對應(yīng)的字符；（2）約定左分支表示字符“0”，

57、右分支表示字符1 則從根結(jié)點到每個葉結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點對應(yīng)字符的編碼，我們稱之為赫夫曼編碼。求編碼的過程：從葉子結(jié)點出發(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 赫夫曼樹及其應(yīng)用第134頁/共147頁赫夫曼樹的存儲結(jié)構(gòu)及其算法的實現(xiàn)1. 設(shè)置一個數(shù)組huffTree2n-1保存赫夫曼樹中各點的信息，數(shù)組元素的結(jié)點結(jié)構(gòu) ：其存儲結(jié)構(gòu)為：Typedef struct float weight; int lchild,rchild,parent; hufmtree;hufmtree treem;/設(shè)patent域不僅是為了使涉及雙親的運算方便，其主要作用是區(qū)分根和非根結(jié)點，若parent的值為-1，則表示該結(jié)點是無雙親的根結(jié)點，否則非根結(jié)點。weightweightLchildLchildParentParentrchildrchild結(jié)點結(jié)構(gòu)第135頁/共147頁6.5 赫夫曼樹及其應(yīng)用1. 數(shù)組huffTree初始化，所有元素結(jié)點的雙親、左、右孩子都置為- -1；2. 數(shù)組huffTree的前n個元素的權(quán)值置給定值wn；3. 進行n- -1次合并 3.1 在二叉樹集合中選取兩個權(quán)值最小的根結(jié)點，其下標(biāo)分別為i1, i2； 3.2 將二叉樹i1、i2合并為一棵新的二叉樹k；在上述存儲結(jié)構(gòu)上實現(xiàn)hufmtreehufmtree算法的基本步驟：第136頁/共1