數(shù)據(jù)結(jié)構(gòu)與第5章_樹

1、第五章 樹和二叉樹北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與STL第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏輯結(jié)構(gòu)4. 二叉樹的存儲結(jié)構(gòu)5. 樹、森林、二叉樹的轉(zhuǎn)換6. 哈夫曼樹（計(jì)劃學(xué)時(shí)6h）21. 樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與STL5.1 樹的邏輯結(jié)構(gòu)定義 樹是n (n0) 個結(jié)點(diǎn)的有限集, 如果n=0，稱為空樹；如果n0，則 (1) 有且僅有一個稱為根的結(jié)點(diǎn)root (2) n1時(shí)，其余結(jié)點(diǎn)可分為m個互不相交的有限集T1 Tn，其中每一個集合又是一棵樹，稱為根的子樹3數(shù)據(jù)結(jié)構(gòu)與STL5.1 樹的邏輯結(jié)構(gòu)4ABCDEFGHIJMKLrootT1T3T2數(shù)據(jù)結(jié)構(gòu)

2、與STL2. 樹的基本術(shù)語結(jié)點(diǎn)的度樹的度葉結(jié)點(diǎn)分支結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)與STL5ABCDEFGHIJMKL結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的個數(shù)。樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。2. 樹的基本術(shù)語孩子雙親兄弟祖先子孫數(shù)據(jù)結(jié)構(gòu)與STL6ABCDEFGHIJMKL 結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子的雙親。 同一雙親的孩子之間互稱兄弟。結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)。2. 樹的基本術(shù)語路徑路徑長度數(shù)據(jù)結(jié)構(gòu)與STL7ABCDEFGHIJMKL路徑：從根結(jié)點(diǎn)到其他結(jié)點(diǎn)的一條路經(jīng)。路徑長度：路經(jīng)經(jīng)過的邊的

3、個數(shù)。路徑長度=32. 樹的基本術(shù)語結(jié)點(diǎn)層次樹的深度數(shù)據(jù)結(jié)構(gòu)與STL8ABCDEFGHIJMKL結(jié)點(diǎn)層次：從根開始，根為第一層，根的孩子 為第二層，以此類推。1234樹的深度：樹中結(jié)點(diǎn)的最大層次。2. 樹的基本術(shù)語層序編號數(shù)據(jù)結(jié)構(gòu)與STL912345678910131112 將樹中結(jié)點(diǎn)按照從上到下. 同層從左到右的次序依次給它們從1開始編號，這種方式就是層序編號。2. 樹的基本術(shù)語有序樹無序樹數(shù)據(jù)結(jié)構(gòu)與STL10ABCDEFGHIJMKL 如果樹中各結(jié)點(diǎn)的子樹從左至右是有次序的（不能互換），則稱該樹為有序樹；否則為無序樹。2. 樹的基本術(shù)語森林?jǐn)?shù)據(jù)結(jié)構(gòu)與STL11 m(m=0)棵互不相交的樹的

4、集合構(gòu)成森林。BCDEFGHIJMKL2. 樹的基本術(shù)語同構(gòu)數(shù)據(jù)結(jié)構(gòu)與STL12 兩棵樹同構(gòu)就是這兩棵樹的形狀相同。BCEFKLDGHIJM第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏輯結(jié)構(gòu)4. 二叉樹的存儲結(jié)構(gòu)5. 樹、森林、二叉樹的轉(zhuǎn)換6. 哈夫曼樹132. 樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與STL5.2 樹的存儲結(jié)構(gòu)四種存儲結(jié)構(gòu)雙親表示法孩子表示法雙親孩子表示法 孩子兄弟表示法樹的基本操作14數(shù)據(jù)結(jié)構(gòu)與STL1）雙親表示法15dataparentA-1B0C0D0E2F2G50123456size=7ABCDEFG數(shù)據(jù)結(jié)構(gòu)與STL結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)的C+描述 datap

5、arent #define MaxSize 100 template struct pNode T data; int parent; ; 樹的描述： pNode TreeMaxSize; int size;帶右兄弟的雙親表示法16ABCDEFGdataparentrightsibA-1-1B02C03D0-1E25F2-1G5-10123456size=7數(shù)據(jù)結(jié)構(gòu)與STL結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)的C+描述 dataparentrightsibtemplate struct pNode T data; int parent，rightsib; ;樹描述：pNode TreeMaxSize;int size

6、;2）孩子表示法多重鏈表表示法17ABFDECGrootABCDEFG數(shù)據(jù)結(jié)構(gòu)與STLdatachild1child2childd結(jié)點(diǎn)結(jié)構(gòu)缺點(diǎn)：會浪費(fèi)大量的指針域2）孩子表示法18dataABCDEFG0123456 1 2 34 56ABCDEFG數(shù)據(jù)結(jié)構(gòu)與STLstruct CNode int child; CNode *next; template struct CBNode T data; CNode *firstchild; childnextdatafirstchild孩子結(jié)點(diǎn)表頭結(jié)點(diǎn)孩子鏈表表示法3）雙親孩子表示法19dataparentA-1B0C0D0E2F2G4012345

7、6 1 2 34 56ABCDEFG數(shù)據(jù)結(jié)構(gòu)與STL4）孩子兄弟表示法20ABFDECGrootABCDEFG數(shù)據(jù)結(jié)構(gòu)與STL結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)描述template struct TNode T data; TNode *firstchild,*rightsib; ;firstchilddatarightsib樹的基本操作InitTree()DestroyTree() Root()Parent()Depth() /求樹的深度PreOrder() /先序遍歷PostOrder() /后序遍歷LevelOrder() /層次遍歷21數(shù)據(jù)結(jié)構(gòu)與STL樹的遍歷定義 從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問樹的所有

8、結(jié)點(diǎn)，使每個結(jié)點(diǎn)僅被訪問一次。分類 1. 前序遍歷 2. 后序遍歷 3. 層序遍歷22數(shù)據(jù)結(jié)構(gòu)與STL 訪問：對結(jié)點(diǎn)的各種處理，比如，輸出結(jié)點(diǎn)內(nèi)容如何遍歷這棵樹？23ABCDEFGHIJMKLrootT1T3T2數(shù)據(jù)結(jié)構(gòu)與STL樹的遍歷1. 前序遍歷 （1）訪問根結(jié)點(diǎn) （2）按照從左到右的順序依次遍歷根結(jié)點(diǎn)的每一棵子樹。24數(shù)據(jù)結(jié)構(gòu)與STLABCDEFGHIJMKLA BEFKL CG DHIJM樹的遍歷2. 后序遍歷 （1）按照從左到右的順序依次遍歷根結(jié)點(diǎn)的每一棵子樹 （2）訪問根結(jié)點(diǎn)。25數(shù)據(jù)結(jié)構(gòu)與STLABCDEFGHIJMKLEKLFB GC HIMJD A樹的遍歷3. 層序遍歷（也稱

9、為廣度遍歷）從第一層開始，從上到下逐層遍歷，同層按從左到右的順序遍歷。26數(shù)據(jù)結(jié)構(gòu)與STLABCDEFGHIJMKLA BCD EFGHIJ KLM練習(xí)寫出該樹的前序. 后序. 層次遍歷序列27ABCDEFG前序：ABCEFGD后序：BEGFCDA層次：ABCDEFG數(shù)據(jù)結(jié)構(gòu)與STL練習(xí)寫出該樹的度. 深度，以及前序. 后序. 層次遍歷序列28DECBAIHJKFGLM前序：ABEFCGDHKLMIJ后序：EFBGCKLMHIJDA層次：ABCDEFGHIJKLM樹的度為3，深度為4數(shù)據(jù)結(jié)構(gòu)與STL第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏輯結(jié)構(gòu)4. 二叉

10、樹的存儲結(jié)構(gòu)5. 樹、森林、二叉樹的轉(zhuǎn)換6. 哈夫曼樹293. 二叉樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與STL5.2 二叉樹的邏輯結(jié)構(gòu)定義 n(n=0)個結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個根結(jié)點(diǎn)和兩棵互不相交的左右子樹組成。特點(diǎn) 1. 每個結(jié)點(diǎn)最多只有兩個子樹 2. 左右子樹次序不能顛倒30FGDEBCA數(shù)據(jù)結(jié)構(gòu)與STL5.2 二叉樹的邏輯結(jié)構(gòu)樹和二叉樹的區(qū)別 31ABABABAB同一棵樹不同的二叉樹數(shù)據(jù)結(jié)構(gòu)與STL5.2 二叉樹的邏輯結(jié)構(gòu)二叉樹具備5種形態(tài)32RLLR二叉樹的五種不同形態(tài)數(shù)據(jù)結(jié)構(gòu)與STL5.2 二叉樹的邏輯結(jié)構(gòu)特殊的二叉樹 （1）斜樹 （2）滿二叉樹 （3）完全二叉樹33數(shù)據(jù)結(jié)構(gòu)

11、與STL特殊的二叉樹（1）斜樹 所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹； 所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹。數(shù)據(jù)結(jié)構(gòu)與STL34ABCABC特殊的二叉樹（2）滿二叉樹所有的分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。35數(shù)據(jù)結(jié)構(gòu)與STL891011121314154567231特殊的二叉樹（3）完全二叉樹按從上到下. 從左到右的順序?yàn)榻Y(jié)點(diǎn)編號，與滿二叉樹序號一一對應(yīng)的二叉樹。36數(shù)據(jù)結(jié)構(gòu)與STL819104567232. 二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有 2i-1個結(jié)點(diǎn)(i1).37數(shù)據(jù)結(jié)構(gòu)與STL數(shù)學(xué)歸納法證明當(dāng)i=1 只有一個根結(jié)點(diǎn) 2i-1=20=1成立假設(shè)

12、i=k 結(jié)論成立，即第k層最多有2k-1結(jié)點(diǎn)則i=k+1時(shí)，由于第k層每個結(jié)點(diǎn)最多有兩個孩子結(jié)點(diǎn)，所以該層最多有結(jié)點(diǎn)2*2k-1 =2k結(jié)點(diǎn).由此，該結(jié)論成立2. 二叉樹的性質(zhì)性質(zhì)2 深度為 k 的二叉樹至多有 2k-1 個結(jié)點(diǎn) (k0)。38數(shù)據(jù)結(jié)構(gòu)與STL根據(jù)性質(zhì)1，求等比數(shù)列的前k項(xiàng)和： 20 + 21 + 22 + + 2k-1 = 2k-1提示：試試?yán)眯再|(zhì)12. 二叉樹的性質(zhì)性質(zhì)3任何一棵二叉樹T，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1.39數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCA2. 二叉樹的性質(zhì)1）二叉樹只有三類結(jié)點(diǎn)，度為0. 1. 2的結(jié)點(diǎn)，所以 樹總的結(jié)點(diǎn)： n

13、0 +n1+ n22）二叉樹n0沒有分支， n1有1個分支； n2有2個分支，所以 樹的總分支: 2*n2 + n140 結(jié)點(diǎn)數(shù)和分支數(shù)的關(guān)系？FGDEBCA結(jié)點(diǎn)分支數(shù)據(jù)結(jié)構(gòu)與STL習(xí)題已知正則二叉樹中（只有度為0和2的結(jié)點(diǎn)）有n個葉子結(jié)點(diǎn)，則這個二叉樹的結(jié)點(diǎn)總數(shù)是_ A 2*n B 2*n-1 C 2*n+1 D 不確定41數(shù)據(jù)結(jié)構(gòu)與STL2. 二叉樹的性質(zhì)性質(zhì)4具有n個結(jié)點(diǎn)的完全二叉樹的深度為 +1。42數(shù)據(jù)結(jié)構(gòu)與STL根據(jù)性質(zhì)2: 設(shè)完全二叉樹的深度為k，則其結(jié)點(diǎn)數(shù) 2k-1-1 n 2k-1 2k-1 n 2k 所以 k-1 Log2n k Log2n 1，則其雙親為i/2 (2) 如

14、果2in，則結(jié)點(diǎn)無左孩子，否則其左孩子為2i (3) 如果2i+1n，則無右孩子，否則其右孩子為2i+144數(shù)據(jù)結(jié)構(gòu)與STL819104567232. 二叉樹的性質(zhì)452i2i+12i+22i+3ii+1i/2雙親左孩子右孩子數(shù)據(jù)結(jié)構(gòu)與STL81910456723用歸納法可證（2）和（3），再用（2）和（3）證明（1）。3. 二叉樹的基本操作InitBiTree()DestroyBiTree()PreOrder() /前序遍歷InOrder() / 中序遍歷PostOrder() /后序遍歷LevelOrder() /層次遍歷46數(shù)據(jù)結(jié)構(gòu)與STL4. 二叉樹的遍歷三種遍歷方式 1）前序遍歷（D

15、LR） 2）中序遍歷（LDR） 3）后序遍歷（LRD） 4）層序遍歷約定 D：根結(jié)點(diǎn) L：左子樹 R：右子樹47數(shù)據(jù)結(jié)構(gòu)與STL4. 二叉樹的遍歷1. 前序遍歷（DLR） （1）訪問根結(jié)點(diǎn) （2）前序遍歷左子樹 （3）前序遍歷右子樹 48數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAA BDEFG C4. 二叉樹的遍歷2. 中序遍歷（LDR） （1）中序遍歷左子樹 （2）訪問根結(jié)點(diǎn) （3）中序遍歷右子樹49數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCADBFEG A C4. 二叉樹的遍歷3. 后序遍歷（LRD） （1）后序遍歷左子樹 （2）后序遍歷右子樹 （3）訪問根結(jié)點(diǎn)50數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCADFGEB C A4

16、. 二叉樹的遍歷4. 層序遍歷（也稱為廣度遍歷） 從第一層開始，從上到下逐層遍歷，同層按從左到右的順序遍歷51數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAA BC DE FG練習(xí)寫出二叉樹的前序. 中序. 后序. 層序序列52FGDEBCAH前序：A BDEF CGH中序：DBFE A GHC后序：DFEB HGC A層序：A BC DEG FH數(shù)據(jù)結(jié)構(gòu)與STL思考已知二叉樹的前序序列 ABCDEFGH 和中序序列 CDBAFEHG ，能否唯一確定一棵二叉樹? D L R L D R L R D53數(shù)據(jù)結(jié)構(gòu)與STL54前序序列 A BCD EFGH 中序序列 CDB A FEHG BCDEFGHAAABEF

17、GHCDAABEFGHCDAABGHCDEF數(shù)據(jù)結(jié)構(gòu)與STL練習(xí)已知二叉樹的前序序列 ABHFDECKG 和中序序列 HBDFAEKCG ，畫出該二叉樹。55數(shù)據(jù)結(jié)構(gòu)與STL56HBDFEKCGA前序 ABHFDECKG 中序 HBDFAEKCG AABEKCGHDFAAB EKCGHFDAB KCGHFDEAB HFDECKG數(shù)據(jù)結(jié)構(gòu)與STL思考什么樣的二叉樹前序序列和中序序列相同？什么樣的二叉樹后序序列和中序序列相同？什么樣的二叉樹前序序列和后序序列相同？ D L R L D R L R D57數(shù)據(jù)結(jié)構(gòu)與STL第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏

18、輯結(jié)構(gòu)4. 二叉樹的存儲結(jié)構(gòu)5. 樹、森林、二叉樹的轉(zhuǎn)換6. 哈夫曼樹584. 二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與STL5.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 1）順序存儲結(jié)構(gòu) 2）二叉鏈表 3）三叉鏈表 4）線索鏈表59數(shù)據(jù)結(jié)構(gòu)與STL1）順序存儲結(jié)構(gòu)60數(shù)據(jù)結(jié)構(gòu)與STL 用一維數(shù)組存儲二叉樹中的結(jié)點(diǎn) 結(jié)點(diǎn)的存儲位置（下標(biāo)）體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系父子關(guān)系。 完全二叉樹 一般二叉樹00 1 2 3 4 5 6 7 8 990 1 2 3 4 5 6 7 8 9137894562012543678順序存儲結(jié)構(gòu)61FGDEBCAHFGDEBCAHHHHHH12345678910111213ABCDEGF

19、H1 2 3 4 5 6 7 8 9 10 11 12 13數(shù)據(jù)結(jié)構(gòu)與STL方法：1. 將二叉樹按照完全二叉樹編號 2. 然后用一維數(shù)組存儲該二叉樹，其中無結(jié)點(diǎn)的位置使用NULL表示完全二叉樹適合采用順序存儲結(jié)構(gòu)2）二叉鏈表62lchilddatarchild 結(jié)點(diǎn)結(jié)構(gòu)：LeftChilddataRightChildFGDEBCAACGBErootDF數(shù)據(jù)結(jié)構(gòu)與STL結(jié)點(diǎn)的C+的類型描述： template struct Node T data; Node* lch; Node* rch; ;二叉樹的C+描述template class BiTreeprotected: Node *root;

20、 void Create (Node* &R, int i); void Release(Node *R);public: BiTree(): root(NULL) BiTree(Node *R); void PreOrder ( Node *R ); void InOrder ( Node *R ); void PostOrder ( Node *R ); void LevelOrder ( Node *R ); BiTree();63數(shù)據(jù)結(jié)構(gòu)與STL建立二叉樹基本思想 以順序存儲結(jié)構(gòu)作為建立二叉樹的輸入，根據(jù)二叉樹的定義，分三步建樹： 1. 建立根結(jié)點(diǎn) 2. 建立左子樹 3. 建立右子樹6

21、4數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAHABCDEG000F00Htemplate void BiTree:Create(Node *&R, int i, char ch, int num) if (inum | chi=0) R = NULL; else R=new Node; R-data = chi; Create(R-lch, 2*i, ch, num); Create(R-rch, 2*i+1 , ch, num); /注意，ch0沒用。65FGDEBCAHABCDEG000F00H數(shù)據(jù)結(jié)構(gòu)與STL二叉鏈表的遍歷假設(shè)使用二叉鏈表表示二叉樹已經(jīng)建立，則如何實(shí)現(xiàn)以下四種遍歷操作？ PreOrd

22、er() /前序遍歷 InOrder() /中序遍歷 PostOrder() /后序遍歷 LevelOrder() /層次遍歷66數(shù)據(jù)結(jié)構(gòu)與STL PreOrder() 前序遍歷 DLR遞歸實(shí)現(xiàn)template void BiTree:PreOrder ( Node *Root ) if (Root!=NULL) coutdata; / 訪問結(jié)點(diǎn) PreOrder(Root -lchild); / 遍歷左子樹 PreOrder(Root -rchild); / 遍歷右子樹 67數(shù)據(jù)結(jié)構(gòu)與STL PreOrder() 前序遍歷 DLR非遞歸實(shí)現(xiàn)二叉樹前序遍歷非遞歸的關(guān)鍵 在前序遍歷完某結(jié)點(diǎn)的左子

23、樹后，如何找到該結(jié)點(diǎn)的右子樹的根？ 68 這就需要棧：保存當(dāng)前結(jié)點(diǎn)，然后當(dāng)該結(jié)點(diǎn)的左子樹訪問完畢后，當(dāng)前結(jié)點(diǎn)出棧，訪問其右子樹。數(shù)據(jù)結(jié)構(gòu)與STLlchDrchlchBrchlchArch前序遍歷過程69FGDEBCAAPrint(A)出棧出棧ABPrint(B)ABDPrint(D)AB出棧A出棧AEPrint(E)AEFPrint(F)AE出棧CPrint(C)CGPrint(G)C出棧A出棧數(shù)據(jù)結(jié)構(gòu)與STL注意：實(shí)際是指向結(jié)點(diǎn)的指針進(jìn)棧，此處僅是示意圖?；舅枷?）如果當(dāng)前結(jié)點(diǎn)非空訪問當(dāng)前結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)入棧；將當(dāng)前結(jié)點(diǎn)的左孩子作為當(dāng)前結(jié)點(diǎn)；2）如果當(dāng)前結(jié)點(diǎn)為空棧頂結(jié)點(diǎn)出棧，將該結(jié)點(diǎn)的右孩子作

24、為當(dāng)前結(jié)點(diǎn)； 反復(fù)執(zhí)行1）2)，直到當(dāng)前結(jié)點(diǎn)=NULL & ?？? 70數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAtemplate void BiTree:PreOrder(Node *R)StackNode* S;while(!S.IsEmpty() | (R!=NULL)if (R!=NULL) coutdata; S.Push(R); R=R-lch; else R=S.Pop(); R=R-rch; 71數(shù)據(jù)結(jié)構(gòu)與STLA0B00C0rootInOrder() 中序遍歷LDR-遞歸template void BiTree:InOrder ( Node *Root ) if (Root!=NULL)

25、 InOrder(Root -lchild); / 遍歷左子樹 coutdata; / 訪問結(jié)點(diǎn) InOrder(Root -rchild); / 遍歷右子樹 72數(shù)據(jù)結(jié)構(gòu)與STLA0B00C0rootInOrder() 中序遍歷LDR-非遞歸中序與前序遍歷的區(qū)別 前序遍歷：1）先訪問該結(jié)點(diǎn)2）再入棧3）然后訪問其左子樹；4）出棧，訪問其右子樹 中序遍歷： 1）先入棧2）訪問其左子樹3）結(jié)點(diǎn)出棧，訪問該結(jié)點(diǎn)； 4）訪問該結(jié)點(diǎn)的右子樹73數(shù)據(jù)結(jié)構(gòu)與STL中序遍歷過程74FGDEBCAA入棧AB入棧ABD入棧ABPrint(D)APrint(B)AE入棧AEF入棧AEPrint(F)C入棧CG入棧

26、CPrint(G)Print(C)APrint(E)Print(A)數(shù)據(jù)結(jié)構(gòu)與STL注意：實(shí)際是指向結(jié)點(diǎn)的指針進(jìn)棧，此處僅是示意圖。基本思想1）如果當(dāng)前結(jié)點(diǎn)非空當(dāng)前結(jié)點(diǎn)入棧；將當(dāng)前結(jié)點(diǎn)的左孩子作為當(dāng)前結(jié)點(diǎn)；2）如果當(dāng)前結(jié)點(diǎn)為空棧頂結(jié)點(diǎn)出棧，訪問當(dāng)前結(jié)點(diǎn)將該結(jié)點(diǎn)的右孩子作為當(dāng)前結(jié)點(diǎn)；反復(fù)執(zhí)行1）2)，直到當(dāng)前結(jié)點(diǎn)NULL & ?？?75數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAtemplate void BiTree:InOrder (Node *R) StackNode* S; while(!S.IsEmpty() | (R!=NULL) if (R!=NULL) S.Push(R); R=R-lch;

27、else R=S.Pop(); coutdata; R=R-rch; 76數(shù)據(jù)結(jié)構(gòu)與STLPostOrder() 后序遍歷LRD -遞歸template void BiTree:PostOrder ( Node *Root ) if (Root!=NULL) PostOrder(Root -lchild); / 遍歷左子樹 PostOrder(Root -rchild); / 遍歷右子樹 coutdata; / 訪問結(jié)點(diǎn) 77數(shù)據(jù)結(jié)構(gòu)與STLPostOrder() 后序遍歷LRD 非遞歸二叉樹后序遍歷的關(guān)鍵 1）當(dāng)前結(jié)點(diǎn)入棧，訪問其左子樹 2）利用棧頂結(jié)點(diǎn)，訪問其右子樹 3）當(dāng)前結(jié)點(diǎn)出棧，訪問

28、該結(jié)點(diǎn)78數(shù)據(jù)結(jié)構(gòu)與STL 因此，必須為棧中的元素設(shè)置標(biāo)記，用來判斷什么時(shí)候出棧。后序遍歷過程79FGDEBCAl,A,r,1入棧l,A,r,1l,B,r,1入棧l,A,r,1l,B,r,1l,D,r,1-2入棧l,A,r,1l,B,r,2Print(D)l,A,r,1l,B,r,2l,E,r,1入棧l,F,r,1-2l,A,r,1l,B,r,2l,E,r,1入棧l,A,r,2l,C,r,1-2Print(G)l,A,r,2l,C,r,1l,G,r,1-2入棧l,A,r,2Print(C)l,A,r,1l,B,r,2l,E,r,2Print(F)l,A,r,1l,B,r,2Print(E)l,

29、A,r,2Print(B)l,A,r,2l,C,r,1入棧Print(A)數(shù)據(jù)結(jié)構(gòu)與STL進(jìn)棧，標(biāo)志置1；為棧頂（標(biāo)志為1），標(biāo)志置2；再為棧頂（標(biāo)志為2），出棧輸出。三部曲PostOrder() 后序遍歷LRD-非遞歸后序遍歷的過程1.當(dāng)前結(jié)點(diǎn)指針!=NULL時(shí)，入棧，置標(biāo)記(L)，遍歷左子樹;2.當(dāng)前結(jié)點(diǎn)指針=NULL時(shí)，(1)若棧頂元素標(biāo)記為R，退棧打印，直到棧頂元素標(biāo)記為L；(2)若棧頂元素標(biāo)記為L，改標(biāo)記R,則遍歷右子樹；反復(fù)執(zhí)行1）2）直到?？?。80數(shù)據(jù)結(jié)構(gòu)與STL棧中元素的結(jié)構(gòu)template struct SNode Node *ptr; int tag; /1左 2右 ;te

30、mplate void BiTreee:Postorder (Node *R) SNode SMAXSIZE; int top = -1; do while (R!=NULL) /左子樹不空，進(jìn)棧 S+top.ptr=R; Stop.tag=1； R=R-lch; while(top!=-1 & Stop.tag=2) /右子樹返回,訪問結(jié)點(diǎn)； coutdata; top-; if(top!=-1 & Stop.tag=1) /左子樹返回，修改標(biāo)志； R=Stop.ptr-rch; Stop.tag=2; while(top!=-1)81數(shù)據(jù)結(jié)構(gòu)與STLint tagNode *ptrLeve

31、lOrder() /層次遍歷層序遍歷從上到下，從左到右依次訪問每一個結(jié)點(diǎn)。先訪問的結(jié)點(diǎn)，其左右孩子結(jié)點(diǎn)也會先訪問。 82數(shù)據(jù)結(jié)構(gòu)與STLFGDEBCAABCDEGFLevelOrder() 層次遍歷這是一個隊(duì)列的應(yīng)用基本思想 根結(jié)點(diǎn)非空，入隊(duì)。 如果隊(duì)列不空 隊(duì)頭元素出隊(duì) 訪問該元素 若該結(jié)點(diǎn)的左孩子非空，則左孩子入隊(duì)； 若該結(jié)點(diǎn)的右孩子非空，則右孩子入隊(duì)； 83FGDEBCA數(shù)據(jù)結(jié)構(gòu)與STLtemplate void BiTree:LevelOrder (Node *R) QueueNode* Q; if (R!=NULL) Q.InQueue(R); while (!Q.IsEmpty()

32、 Node *p=Q.DelQueue(); coutdata; if (p-lchild!=NULL) Q.InQueue(p-lchild); if (p-rchild!=NULL) Q.InQueue(p-rchild) 84數(shù)據(jù)結(jié)構(gòu)與STL析構(gòu)函數(shù)template void BiTree:Release ( Node *Root ) if (Root!=NULL) Release(Root -lchild); / 釋放左子樹 Release(Root -rchild); / 釋放右子樹 delete Root; / 釋放根結(jié)點(diǎn) 85數(shù)據(jù)結(jié)構(gòu)與STL例1統(tǒng)計(jì)二叉樹中的結(jié)點(diǎn)總數(shù) 86LRF

33、GDEBCAH提示： 結(jié)點(diǎn)總數(shù)= 左子樹 + 右子樹 + 1數(shù)據(jù)結(jié)構(gòu)與STL統(tǒng)計(jì)二叉樹中的結(jié)點(diǎn)總數(shù)template int Count(Node *R)if (R=NULL) return 0;elseint m=Count(R-lch);int n=Count(R-rch);return m+n+1;87FGDEBCAH數(shù)據(jù)結(jié)構(gòu)與STL思考題已知二叉樹的前序序列 和中序序列 ，編寫算法建立二叉樹。 測試數(shù)據(jù)： 前序序列 ABHFDECKG 中序序列 HBDFAEKCG 88數(shù)據(jù)結(jié)構(gòu)與STL89HBDFEKCGA前序 ABHFDECKG 中序 HBDFAEKCG AABEKCGHDFAAB E

34、KCGHFDAB KCGHFDEAB HFDECKG數(shù)據(jù)結(jié)構(gòu)與STLHBDFEKCGA基本思路1. 前序序列(s1,e1)中的s1位置是根結(jié)點(diǎn)R2. 在中序序列(s2,e2)中找R的位置pos3. 將前序序列進(jìn)行分割 i= s1+pos-s2， (s1+1, i) (i+1, e1)4. 將中序序列進(jìn)行分割 (s2, pos-1) (pos+1, e2)反復(fù)繼續(xù)，1，2，3,4直到區(qū)間中只有一個元素。90數(shù)據(jù)結(jié)構(gòu)與STL前序 ABHFDECKG 中序 HBDFAEKCG 基于中序序列數(shù)出左子樹結(jié)點(diǎn)數(shù)目分割序列代碼/輔助函數(shù)，查找元素x中序序列的位置template int BiTree:Fin

35、d(T x, T InBuf, int s, int e) /s中序序列查找區(qū)間左邊界 e 右邊界for(int i=s; idatas1e1s2e2posiA131322template void BiTree:Create(Node* &R, T PreBuf, T InBuf, int s1, int e1, int s2, int e2) if (s1=e1) int pos=Find(PreBufs1, InBuf, s2, e2);if (pos=0) R=NULL;else R=new Node; R-data = PreBufs1; int i = s1+pos-s2; Cre

36、ate(R-lch, PreBuf, InBuf, s1+1,i,s2,pos-1); Create(R-rch, PreBuf, InBuf, i+1, e1, pos+1,e2); else R=NULL; /需要將各參數(shù)畫表解釋92數(shù)據(jù)結(jié)構(gòu)與STL前序 ABC 中序 BAC 3）三叉鏈表93 A D E B C Frootlchilddatarchild 結(jié)點(diǎn)結(jié)構(gòu)：parentLeftChilddataRightChildparent數(shù)據(jù)結(jié)構(gòu)與STL3）三叉鏈表 三叉鏈表結(jié)點(diǎn)的C+的類型描述： template struct Node public:T data;Node* parent

37、; Node* lchild; Node* rchild; ;94數(shù)據(jù)結(jié)構(gòu)與STL4. 線索鏈表N個結(jié)點(diǎn)的二叉鏈表一共有_指針域？其中有_指針域是NULL?我們能不能充分利用這些NULL的指針域，用來保存一些有用的信息？95數(shù)據(jù)結(jié)構(gòu)與STL2NN+14. 中序線索鏈表96ACGBErootDFFGDEBCAlchilddatarchild 結(jié)點(diǎn)結(jié)構(gòu)：ltagrtag數(shù)據(jù)結(jié)構(gòu)與STLltag；/1 表示左孩子 2表示前驅(qū)rtag; /1 表示右孩子 2表示后繼中序遍歷序列:DBFEAGC線索二叉樹template struct Node T data; Node * lch, *rch; int

38、 ltag；/1 表示左孩子 2表示前驅(qū) int rtag; /1 表示右孩子 2表示后繼97數(shù)據(jù)結(jié)構(gòu)與STL第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏輯結(jié)構(gòu)4. 二叉樹的存儲結(jié)構(gòu)5. 樹、森林、二叉樹的轉(zhuǎn)換6. Huffman樹985. 樹、森林、二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與STL5.5 樹、森林、二叉樹的轉(zhuǎn)換樹的孩子兄弟表示法99ABCDEFGABFDECGroot數(shù)據(jù)結(jié)構(gòu)與STL5.5 樹、森林、二叉樹的轉(zhuǎn)換二叉鏈表表示法100ABCEDFGABFDECGroot數(shù)據(jù)結(jié)構(gòu)與STL物理結(jié)構(gòu)101ABFDECGrootABFDECGroot物理結(jié)構(gòu)相同，只是解

39、釋不同而已。數(shù)據(jù)結(jié)構(gòu)與STL邏輯結(jié)構(gòu)102ABCDEFGABCEDFG樹和二叉樹的邏輯結(jié)構(gòu)有一一對應(yīng)的關(guān)系。BCDEFGA數(shù)據(jù)結(jié)構(gòu)與STL1. 樹轉(zhuǎn)換成二叉樹103樹與二叉樹的對應(yīng)關(guān)系當(dāng)以二叉鏈表為存儲結(jié)構(gòu)時(shí)，給定一顆樹，可以找到唯一的一顆二叉樹與之對應(yīng)。任何一顆與樹對應(yīng)的二叉樹，其右子樹必空。ABCEDABCDEABCDEABCEDABCDE樹轉(zhuǎn)換成二叉樹轉(zhuǎn)換原則 第一個右兄弟結(jié)點(diǎn) 右孩子 第一個孩子結(jié)點(diǎn) 左孩子104數(shù)據(jù)結(jié)構(gòu)與STLDECBAIHJKFGLMDECBAIHJKFGLM樹轉(zhuǎn)換為二叉樹的方法： （1）加線：樹中所有相同雙親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)之間加一條連線； （2）去線：對樹中的每個

40、結(jié)點(diǎn)，只保留它與第一個孩子結(jié)點(diǎn)之間的連線，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)之間的連線； （3）調(diào)整：整理所有保留的和添加的連線，使每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)連線位于左孩子指針位置，使每個結(jié)點(diǎn)的兄弟結(jié)點(diǎn)連線位于右孩子指針位置。樹轉(zhuǎn)換成二叉樹特點(diǎn) 樹的前序遍歷 二叉樹的前序遍歷 樹的后序遍歷 二叉樹的中序遍歷106數(shù)據(jù)結(jié)構(gòu)與STL前序:ABCDE后序：BDCEA前序:ABCDE中序：BDCEAABCDEFGIHABDCEIFGH練習(xí)二叉樹還原為樹的方法 （1）若某結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來； （2）刪除原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線； （3

41、）整理所有保留的和添加的連線，使每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)連線順序位于下方孩子結(jié)點(diǎn)位置。2. 森林轉(zhuǎn)換成二叉樹森林：是若干棵樹的集合若干棵樹森林，每一棵樹二叉樹 森林二叉樹轉(zhuǎn)換原則 1）將森林中的每棵樹轉(zhuǎn)換成二叉樹 2）從第二棵樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子。109數(shù)據(jù)結(jié)構(gòu)與STL森林轉(zhuǎn)換為二叉樹方法從第二棵二叉樹開始，依次將當(dāng)前二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，直至所有二叉樹都連接起來。森林轉(zhuǎn)換成二叉樹111DECBAIHJKFGDGECBFAIHJK數(shù)據(jù)結(jié)構(gòu)與STL3. 二叉樹轉(zhuǎn)換成森林轉(zhuǎn)換原則 1）根結(jié)點(diǎn)的右孩子 第二棵樹的根結(jié)點(diǎn) 根結(jié)點(diǎn)右孩子的

42、右孩子第三棵樹的根結(jié)點(diǎn) 2）根結(jié)點(diǎn)的左孩子 按照結(jié)點(diǎn)的左孩子是該結(jié)點(diǎn)的第一個孩子，結(jié)點(diǎn)右孩子是該結(jié)點(diǎn)的右兄弟轉(zhuǎn)換。112數(shù)據(jù)結(jié)構(gòu)與STL二叉樹轉(zhuǎn)換成森林113DECBAIHJKFGDGECBFAIHJK數(shù)據(jù)結(jié)構(gòu)與STL4. 森林的遍歷森林有兩種遍歷方式 1）前序遍歷 前序遍歷森林中的每一棵樹 2）后序遍歷 后序遍歷森林中的每一棵樹114數(shù)據(jù)結(jié)構(gòu)與STL森林的遍歷前序序列：后序序列：115DECBAIHJKFGABECD FG HIJKEBCDA GF IKJH數(shù)據(jù)結(jié)構(gòu)與STL第五章 樹和二叉樹學(xué)習(xí)內(nèi)容：1. 樹的邏輯結(jié)構(gòu)2. 樹的存儲結(jié)構(gòu)3. 二叉樹的邏輯結(jié)構(gòu)4. 二叉樹的存儲結(jié)構(gòu)5. 樹、森

43、林、二叉樹的轉(zhuǎn)換6. 哈夫曼樹1166. Huffman樹數(shù)據(jù)結(jié)構(gòu)與STL5.6 Huffman樹1. 相關(guān)概念 1）葉子結(jié)點(diǎn)的權(quán)值 對葉子結(jié)點(diǎn)賦予一個有意義的數(shù)量值。 2）二叉樹的帶權(quán)路徑長度 設(shè)二叉樹有n個帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。 11727549例如：WPL= 72+52+23+43+92 =60數(shù)據(jù)結(jié)構(gòu)與STL 3）Huffman樹給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹，其中帶權(quán)路徑長度最小的二叉樹稱為Huffman樹，也叫做最優(yōu)二叉樹。118數(shù)據(jù)結(jié)構(gòu)與STLWPL1= 22+43+53+32 = 37WPL2=

44、23+43+52+31 = 31WPL3= 22+32+42+52 =28 WPL4= 23+33+42+51 =28三棵具有相同權(quán)值葉子結(jié)點(diǎn)的二叉樹3452圖a3452圖b圖c圖d已知：一組權(quán)值給定的葉子結(jié)點(diǎn)w1,w2 , , wn，如何構(gòu)造一棵Huffman樹？119提示 ： 只要讓權(quán)值最大的葉子結(jié)點(diǎn)離根最近，權(quán)值最小的葉子結(jié)點(diǎn)離根最遠(yuǎn)，就能使帶權(quán)路徑長度最小。數(shù)據(jù)結(jié)構(gòu)與STL2. Huffman樹構(gòu)造算法構(gòu)造Huffman樹（從下向上構(gòu)造） 已知：權(quán)值表 w1, w2, , wn1）選擇有效權(quán)值中最小的兩個，構(gòu)成最小二叉樹，標(biāo)記這兩個權(quán)值已用。2）將這兩個權(quán)值相加，之和并入權(quán)值表;返回1

45、。 結(jié)束條件如果權(quán)值表沒有沒用過的權(quán)值。120數(shù)據(jù)結(jié)構(gòu)與STL例如：已知權(quán)值 W= 5, 6, 2, 9, 7 1219562725769767139257第一步第二步第三步數(shù)據(jù)結(jié)構(gòu)與STL例如：已知權(quán)值 W= 5, 6, 2, 9, 7 1226713第四步925716925716671329第五步：數(shù)據(jù)結(jié)構(gòu)與STL注意 : 結(jié)點(diǎn)有規(guī)律的放置問題(全部左小右大或全部左大右小)3. Huffman編碼編碼給每一個字符標(biāo)記一個單獨(dú)的代碼。編碼分類等長編碼：如ASCII碼等不等長編碼：如Huffman編碼123數(shù)據(jù)結(jié)構(gòu)與STL例如，假設(shè)要傳送的電文為 ABACCDA，電文中只有A,B,C,D四種字

46、符。00 01 00 10 10 11 00，碼長14。(表a,等長碼)0 110 0 10 10 111 0，碼長13。(表b)思想（不等長編碼） 使用頻率高的字符，編碼長度短； 使用頻率低的字符，編碼長度長； 利用不等長編碼，可以使報(bào)文總長度較短，這也是文件壓縮技術(shù)的核心。124數(shù)據(jù)結(jié)構(gòu)與STL不等長編碼的關(guān)鍵：解碼時(shí)的唯一性 比如：A:0 B:1 C:10 編碼：AABAABC00100110 解碼：AA?125 讓任何短碼都不是其它長碼的前綴B:10C:11編碼：AABAABC 解碼：AABAABC數(shù)據(jù)結(jié)構(gòu)與STL3. Huffman編碼Huffman編碼的基本思想出現(xiàn)概率大的符號-短

47、碼出現(xiàn)概率小的符號-長碼是一種變長編碼Huffman碼-最優(yōu)碼對于給定符號集及其概率模型，找不到其它整數(shù)碼能比Huffman碼有更短的平均字長。（最優(yōu)的含義）整數(shù)碼指每個符號所對應(yīng)的碼字的位數(shù)都是整數(shù)126Huffman編碼是最優(yōu)前綴編碼.約定 左分支：0 右分支：1葉結(jié)點(diǎn)編碼 由從根到葉子的路徑 上分支標(biāo)號構(gòu)成12792571667132900001111000111100101數(shù)據(jù)結(jié)構(gòu)與STL兩種編碼方式 1）字符編碼比如：A的編碼是1110,則使用4個字符1 1 10存儲在文件中。 2）bit編碼比如：A的編碼是1110，則使用4個bit存儲。 提示：二進(jìn)制文件存儲的最小單位是字節(jié)，所以

48、必須使用位運(yùn)算法，每當(dāng)湊夠8個bit時(shí)，存儲一次。128數(shù)據(jù)結(jié)構(gòu)與STL4. Huffman編碼的解碼解碼過程1)從左到右讀取編碼串2)從根結(jié)點(diǎn)開始,如果是0,則選擇左支;如果是1,則選擇右支;直到葉結(jié)點(diǎn)。 反復(fù)上述過程,直到翻譯完畢。129數(shù)據(jù)結(jié)構(gòu)與STL0001001110110111101CDCEBBEB練習(xí): 假設(shè)用于通訊的電文僅由8個字母c1,c2,c3,c4,c5,c6,c7,c8組成，各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試為這8個字母設(shè)計(jì)Huffman編碼，并給出該電文的總碼數(shù)。52536103645, 25, 3, 6, 10, 11, 36,

49、 45, 25, 6, 10, 11, 36, 71111, 25, 10, 11, 36, 71711, 25, 11, 36 25, 36,1739, 25, 3639, 6110001000000111111c1c2c3c4c5c6c7c872239編碼：c1:0100c2:10c3:0000c4:0101c5:001c6:011c7:11c8:0001WPL=5*4+25*2+3*4+6*4+10*3+11*3+36*2+4*4=257電文的總碼長 =5*4+25*2+3*4+6*4+10*3+11*3+36*2+4*4=2575. Huffman樹的存儲結(jié)構(gòu)

50、Huffman樹的特點(diǎn) 只有度為2的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，所以具有n個葉子結(jié)點(diǎn)的Huffman樹的結(jié)點(diǎn)總數(shù) 。順序存儲結(jié)構(gòu) 設(shè)置一個的huffTree2*n-1數(shù)組，132數(shù)據(jù)結(jié)構(gòu)與STLweightlchildrchildparent結(jié)點(diǎn)結(jié)構(gòu)2*n-1Huffman樹的C+描述struct HNode int weight; int lchild, rchild, parent;HNode huffTree2*n-1;133數(shù)據(jù)結(jié)構(gòu)與STL925716671329例如:已知權(quán)值 W= 5, 6, 2, 9, 7 134初始狀態(tài)01234weight lchild rchild parent5678

51、數(shù)據(jù)結(jié)構(gòu)與STL結(jié)束狀態(tài)2-1-155-1-156-1-167-1-169-1-17701713238165482967-12-1-1-15-1-1-16-1-1-17-1-1-19-1-1-101234weight lchild rchild parent56786. Huffman 編碼的相關(guān)代碼huffman編碼表C+描述：strcut HCode char data; char code100; ; /字符及其編碼結(jié)構(gòu) HCode HCodeTableN; /文本碼表Huffman 編碼的C+類class Huffmanprivate: HNode* huffTree; /Huffma

52、n樹 HCode* HCodeTable; /Huffman編碼表public: void CreateHTree(int a, int n); /創(chuàng)建huffman樹 void CreateCodeTable(char b, int n); /創(chuàng)建編碼表 void Encode(char *s, char *d); /編碼 void Decode(char *s, char *d); /解碼 Huffman();創(chuàng)建huffman樹代碼算法過程：Huffman樹采用順序存儲-數(shù)組；數(shù)組的前n個結(jié)點(diǎn)存儲葉子結(jié)點(diǎn)，然后是分支結(jié)點(diǎn)，最后是根結(jié)點(diǎn)；首先初始化葉子結(jié)點(diǎn)元素循環(huán)實(shí)現(xiàn)；以循環(huán)結(jié)構(gòu)，實(shí)現(xiàn)分支

53、結(jié)點(diǎn)的合成，合成規(guī)則按照huffman樹構(gòu)成規(guī)則進(jìn)行。關(guān)鍵點(diǎn)：如何選擇最小和次小結(jié)點(diǎn)合成。137創(chuàng)建huffman樹代碼void Huffman:CreateHTree(int a, int n) /根據(jù)權(quán)重?cái)?shù)組a1-n 初始化Huffman樹huffTree = new HNode 2*n-1; for (int i = 0; i n; i+) huffTreei.weight = ai; huffTreei.LChild = -1; huffTreei.RChild = -1; huffTreei.parent = -1; 創(chuàng)建huffman樹代碼 int li, ri; for (int i = n; i 2*n-1; i+) /開始建Huffman樹 /從0i-1中選出兩個權(quán)值最小的結(jié)點(diǎn)， SelectMin(huffTree, i, li, ri); huffTreeli.parent = huffTreeri.parent = i; huffTreei.weight = huffTreeli.weight + huffTreeri.weight; huffTreei.LChil