課件5樹和二叉樹

1、數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹1. 掌握二叉樹的基本概念、性質(zhì)和存儲結(jié)構(gòu)2. 掌握二叉樹的前、中、后序遍歷方法3. 了解線索化二叉樹的思想4. 了解：霍夫曼樹的實現(xiàn)方法、構(gòu)造霍夫曼編碼的方法5. 掌握：森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法教學(xué)目標(biāo)數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.1 樹的定義和基本術(shù)語ACBGFEHIJDMKLA樹是樹是n n個結(jié)點的有限集個結(jié)點的有限集T1T2T3數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點(沒有前驅(qū))即終端結(jié)點(沒有后繼)指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))結(jié)點各子樹從左至右有序，不能互換（左為第一）結(jié)點各子

2、樹可互換位置。ACBGFEHIJDMKL基本術(shù)語數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹即上層的那個結(jié)點即上層的那個結(jié)點(直接前驅(qū)直接前驅(qū))即下層結(jié)點的子樹的根即下層結(jié)點的子樹的根(直接后繼直接后繼)同一雙親下的同層結(jié)點（孩子之間互稱兄弟）同一雙親下的同層結(jié)點（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點（但并非同一雙親）即雙親位于同一層的結(jié)點（但并非同一雙親）即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即該結(jié)點下層子樹中的任一結(jié)點即該結(jié)點下層子樹中的任一結(jié)點雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫ACBGFEHIJDMKL基本術(shù)語數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹即樹的數(shù)據(jù)元素結(jié)點掛接的子樹數(shù)

3、結(jié)點結(jié)點結(jié)點的度結(jié)點的度結(jié)點的層次結(jié)點的層次終端結(jié)點終端結(jié)點分支結(jié)點分支結(jié)點樹的度樹的度樹的深度樹的深度(或高度或高度)從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）即度為0的結(jié)點，即葉子即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）所有結(jié)點度中的最大值指所有結(jié)點中最大的層數(shù)ACBGFEHIJDMKL層次1234基本術(shù)語數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.2 二叉樹普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)為何要重點研究每結(jié)點最多只有兩個 “叉” 的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強； 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹二叉樹基本特點：結(jié)點的度小于等于2有序樹（子樹有序，不能

4、顛倒）數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？ 練習(xí)數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹性質(zhì)1: 在二叉樹的第i層上至多有個結(jié)點二叉樹的性質(zhì)提問：第i層上至少有 個結(jié)點？性質(zhì)2: 深度為k的二叉樹至多有個結(jié)點提問：深度為k時至少有 個結(jié)點？1k數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹1891011124526731891011124526731 nB1212nnB11212nnn012nnn性質(zhì)3: 對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)n0必定為n21 （即n0=n2+1）數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹189101112131415452673滿二叉樹：k（特點：每層都“充滿”了結(jié)點）18910

5、1112452673特殊形態(tài)的二叉樹完全二叉樹：深度為k 的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k 的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)只有最后一層葉子不滿，且全部集中在左邊數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前前n-1n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。滿二叉樹是完全二叉樹的一個特例。189101112131415452673189101112452673滿二叉樹和完全二叉樹的區(qū)別數(shù)據(jù)結(jié)構(gòu)5 樹和

6、二叉樹一棵完全二叉樹有5000個結(jié)點，可以計算出其葉結(jié)點的個數(shù)是（ ）。 練習(xí)2500數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹性質(zhì)4: 具有n個結(jié)點的完全二叉樹的深度必為log2n1189101112452673k層層nk-1層層121k12 k12121kkn數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹性質(zhì)5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i1；其雙親的編號必為i/2。數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹二叉樹的順序存儲實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹a b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7

7、 8 9 10abcdefg特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹二叉樹的順序存儲數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹DATAPARENTLCHILDRCHILDlchilddatarchildlchilddatarchildparent二叉樹的鏈?zhǔn)酱鎯?shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ABCDEFG AB C D E F G二叉鏈表數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹分析：必有2n個鏈域。除根結(jié)點外，每個結(jié)點有且僅有一個雙親，所以只會有n1個結(jié)點的鏈域存放指針，指向非空子女結(jié)點。空指針數(shù)目2n(n-1)=n+1有 個練習(xí) AB C D E F Gn+1數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹三叉鏈表ABCDEFG A

8、 B C D E F Glchild data parent rchild數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.3 二叉樹的遍歷遍歷定義遍歷定義指按某條搜索路線遍訪每個結(jié)點且指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）。不重復(fù)（又稱周游）。遍歷用途遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。切運算的基礎(chǔ)和核心。 數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD遍歷規(guī)則先左后右數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹先序遍歷：先序遍歷：中序遍歷：中序遍歷：后序遍歷：后序遍

9、歷： A B CD E口訣：DLR先序遍歷，即先根再左再右LDR中序遍歷，即先左再根再右LRD后序遍歷，即先左再右再根數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹若二叉樹中各結(jié)點的值均不相同，則：由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。 重要結(jié)論數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹練習(xí)已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG 和 DECBHGFA，請畫出這棵二叉樹。由后序遍歷特征，根結(jié)點必在后序序列尾部（A）；由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹子孫（BDCE），其右部必全部是右子樹子孫（FHG）；

10、繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹中序遍歷后序遍歷（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.4 二叉樹的二叉鏈表實現(xiàn)結(jié)點定義結(jié)點定義數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹Status PreOrderTraverse(BiTree T) if(T=NULL) return OK; /結(jié)束 else coutdata; PreOrderTraverse(T-lchild); /遞歸左子樹 PreOrderTraverse(T-rchild); /遞歸右

11、子樹 先序遍歷遞歸算法結(jié)束條件遞歸過程遞歸算法遞歸算法 = = 遞歸結(jié)束條件遞歸結(jié)束條件 + + 遞歸過程遞歸過程數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹Status PreOrderTraverse(BiTree T) if(T=NULL) return OK; else coutdata; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T

12、 L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：先序序列：ABDC數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹創(chuàng)建二叉樹創(chuàng)建二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹獲取結(jié)點數(shù)獲取結(jié)點數(shù)數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹獲取高度獲取高度數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹查找結(jié)點查找結(jié)點數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹獲取雙親結(jié)點獲取雙親結(jié)點數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪

13、問先序遍歷第2次經(jīng)過時訪問中序遍歷第3次經(jīng)過時訪問后序遍歷遍歷算法的非遞歸實現(xiàn)分析數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹使用一個棧s存放路徑。開始時棧為空，p指向樹根結(jié)點T1、如果指向根結(jié)點的指針p非空，則訪問根結(jié)點；然后p進棧；p指向它的左孩子2、如果指向根結(jié)點的指針p為空，有兩種情況若從左子樹返回，說明左子樹遍歷結(jié)束，應(yīng)該將指針指向其雙親結(jié)點的右孩子進行遍歷，即指向棧頂結(jié)點的右子樹若從右子樹返回，說明已將以其雙親結(jié)點為根的子樹遍歷結(jié)束，則應(yīng)該將指針指向其雙親結(jié)點的右兄弟進行遍歷，即指向棧頂結(jié)點的右子樹3、當(dāng)指針為空且棧為空時，遍歷結(jié)束先序遍歷算法的非遞歸算法數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ADBCE棧棧s訪問序列訪

14、問序列 p不空時不空時 Visit (p); Push ( S, p ); p = p-lc; p空時空時 Pop ( S, p ) p = p-rc;AABBCCDDEE先序遍歷算法的非遞歸算法示例數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹使用棧存放經(jīng)過的路徑，開始時棧為空，p指向樹根結(jié)點T1、如果指向根結(jié)點的指針p非空；p進棧；p指向它的左孩子2、如果指向根結(jié)點的指針p為空，有兩種情況若從左子樹返回，說明左子樹遍歷結(jié)束，應(yīng)該將指針指向其雙親結(jié)點，訪問雙親結(jié)點，并對雙親結(jié)點的右孩子進行遍歷，即訪問棧頂結(jié)點后指向棧頂結(jié)點的右子樹若從右子樹返回，說明已將以其雙親結(jié)點為根的子樹遍歷結(jié)束，則應(yīng)該將指針指向其未訪問過的祖

15、先結(jié)點進行訪問，并指向其結(jié)點的右子樹，即訪問棧頂結(jié)點后指向棧頂結(jié)點的右子樹3、當(dāng)指針為空且棧為空時，遍歷結(jié)束中序序遍歷算法的非遞歸算法數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ADBCE p不空時不空時 Push ( S, p ); p = p-lc; p空時空時 Pop ( S, p ) Visit (p); p = p-rc;棧棧s訪問序列訪問序列AABBCC DD EE中序序遍歷算法的非遞歸算法示例數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹使用棧存放經(jīng)過的結(jié)點及結(jié)點標(biāo)志，開始時棧為空，p指向樹根結(jié)點T1、如果指向根結(jié)點的指針p非空，先將標(biāo)志tag0；再將p及tag進棧；p指向它的左孩子2、如果指向根結(jié)點的指針p為空，有兩種情況

16、若tag0，則改變tag1；再把tag和彈出的結(jié)點重新入棧；然后將指針指向該結(jié)點的右子樹若tag1，則訪問彈出的結(jié)點，并將彈出的結(jié)點指針置空3、當(dāng)指針為空且棧為空時，遍歷結(jié)束后序序遍歷算法的非遞歸算法數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ADBCE棧棧s訪問序列訪問序列A0B0B1C0C1D0D1E0E1 p不為空不為空 SNode.tag = 0; Push ( S, SNode ); SNode.p = SNode.p-lc;p為空且為空且tag0 Pop ( S, SNode ); SNode.tag = 1; Push ( S, SNode); SNode.p = SNode.p-rc; p為空且為空

17、且tag1 Pop ( S, SNode ); Visit (SNode.p ); SNode.p = NULL; CE DBA1A后序序遍歷算法的非遞歸算法示例數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹AFEDCBG時間效率: /每個結(jié)點只訪問一次空間效率:O(n) /棧占用的最大輔助空間非遞歸遍歷算法的分析數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？可以用它來存放當(dāng)前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。思考線索化二叉樹有n+1個 AB C D E F G數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得

18、若將遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個結(jié)點開始就能很快“順藤摸瓜”而遍歷整個樹例如中序遍歷結(jié)果：B D C E A F H G，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子5.5 線索二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹1）若結(jié)點有左子樹，則lchild指向其左孩子； 否則， lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則rchild指向其右孩子； 否則， rchild指向其直接后繼(即線索) 。為了避免混淆，增加兩個標(biāo)志域lchildLTagdataRTag rchild線索化二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹LTag :若 LTag=0,

19、 lchild域指向左孩子； 若 LTag=1, lchild域指向其前驅(qū)。RTag :若 RTag=0, rchild域指向右孩子； 若 RTag=1, rchild域指向其后繼。 lchildLTagdataRTag rchild線索化二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ABCDE A B D C ET先序序列：先序序列：ABCDE0000111111 lchild LTag data RTag rchild先序線索二叉樹LTag=0, lchild域指向左孩子LTag=1, lchild域指向其前驅(qū)RTag=0, rchild域指向右孩子RTag=1, rchild域指向其后繼 數(shù)據(jù)結(jié)構(gòu)5 樹和

20、二叉樹ABCDE A B D C ET中序序列：中序序列：BCAED0000111111 lchild LTag data RTag rchild中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹 lchild LTag data RTag rchildABCDE A B D C ET后序序列：后序序列：CBEDA0000111111后序線索二叉樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹線索線索：指向結(jié)點前驅(qū)和后繼的指針：指向結(jié)點前驅(qū)和后繼的指針線索鏈表線索鏈表：加上線索二叉鏈表：加上線索二叉鏈表線索二叉樹線索二叉樹：加上線索的二叉樹（圖形式樣）：加上線索的二叉樹（圖形式樣）線索化線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二

21、叉：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程樹的過程線索化二叉樹的幾個術(shù)語數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ABCGEIDHFroot懸空？懸空？懸空？該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G為避免懸空態(tài)，應(yīng)增設(shè)一個頭結(jié)點數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root0數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹畫出與二叉樹對應(yīng)的中序線索二叉樹 2825405560330854因為中序遍歷序列是：55 40 25 60

22、 28 08 33 54對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL練習(xí)數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.5 霍夫曼樹及其應(yīng)用路 徑路徑長度帶權(quán)路徑長度:樹的帶權(quán)路徑長度：WPL = wklk k=1nAFEDCBG:由一結(jié)點到另一結(jié)點間的分支所構(gòu)成:路徑上的分支數(shù)目結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積2235數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹霍霍 夫夫 曼曼 樹樹：

23、帶權(quán)路徑長度最小的樹帶權(quán)路徑長度最小的樹數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹。在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和。在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即霍夫曼樹?；舴蚵鼧涞臉?gòu)造過程數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼樹的構(gòu)造過程數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹在遠程通訊中，要將待傳字符轉(zhuǎn)換成二進制的字符串，在遠程通訊中，要將待傳字符轉(zhuǎn)換成二進

24、制的字符串，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？A00B01C10D11ABACCDA000110010101100A0B00C1D01000011010霍夫曼樹應(yīng)用實例霍夫曼編碼出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹關(guān)鍵：關(guān)鍵：要設(shè)計長度不等的編碼，則必須使任一字符的要設(shè)計長度不等的編碼，則必須使任一字符的編碼都不是另一個字符的編碼的編碼都不是另一個字符的編碼的前綴前綴前綴編碼前綴編碼0000AAAA ABA BB重碼ABACCDAA0B00C1D01000011010霍夫曼樹應(yīng)用實例霍夫曼編碼數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹

25、ACBD000111采用二叉樹設(shè)計前綴編碼左分支用“0”右分支用“1”A0B110C10D111 0110010101110 ABACCDA數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹分解接收字符串：遇分解接收字符串：遇“0 0”向左，遇向左，遇“1 1”向右；一旦到達葉子結(jié)向右；一旦到達葉子結(jié)點，則譯出一個字符，反復(fù)由根出發(fā)，直到譯碼完成。點，則譯出一個字符，反復(fù)由根出發(fā)，直到譯碼完成。 0110010101110ACBD000111ABACCDA特點：每一碼都不是另一碼的前綴，絕不會錯譯! 稱為前綴碼霍夫曼編碼的譯碼過程數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹假設(shè)通信的電文僅由8個字母組成，字符在電文中出現(xiàn)的頻率分別為（7、19

26、、2、6、32、3、21、10），試為這8個字母設(shè)計Huffman編碼集合集合F 7、19、2、6、32、3、21、10 523集合集合F 7、19、6、32、21、10 、517710116603228401921100集合集合F 7、19、32、21、10、11集合集合F 19、32、21、11、17集合集合F 19、32、21、28集合集合F 32、28、40集合集合F 40、60集合集合F 1000001101100110101101111101111數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹 霍夫曼編碼是不等長編碼 霍夫曼編碼是前綴編碼，即任一字符的編碼都不是另一字符編碼的前綴 霍夫曼編碼樹中沒有度為1

27、的結(jié)點。若葉子結(jié)點的個數(shù)為n，則霍夫曼編碼樹的結(jié)點總數(shù)為 2n-1 發(fā)送過程：根據(jù)由霍夫曼樹得到的編碼表送出字符數(shù)據(jù) 接收過程：按左0、右1的規(guī)定，從根結(jié)點走到一個葉結(jié)點，完成一個字符的譯碼。反復(fù)此過程，直到接收數(shù)據(jù)結(jié)束霍夫曼編碼的幾點結(jié)論數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹5.6 樹和森林ACBGFEHIJDMKL數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹若樹非空，則先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹RABDCFGEIHR（ADE）（B）（CFGHI）樹的先根遍歷RADEBCFGHI5.6 樹和森林樹的先根遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹若樹非空，則先依次后根遍歷根的每棵子樹，然后訪問樹的根結(jié)點RABDCFGEIH（A

28、DE）（B）（CFGHI） R樹的后根遍歷（DEA）（B）（FGHI）C）R（DEA）（B）（GHIFC）R樹的后根遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹若樹非空，則從樹的根結(jié)點起按層從左到右依次訪問各結(jié)點RABDCFGEIHR （ABC）（DEF）（GHI）樹的層次遍歷RABCDEFGHI樹的層次遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹練習(xí)：寫出下面這棵樹的先根、后根和層次遍歷ABJDCFGEIH數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹A AB BD DC CF FG GE EI IH H若森林非空，則可以按照下述規(guī)則遍歷：若森林非空，則可以按照下述規(guī)則遍歷：a a、訪問森林中第一棵樹的根結(jié)點、訪問森林中第一棵樹的根結(jié)點b b、先序遍

29、歷第一棵樹中根結(jié)點的子樹森林、先序遍歷第一棵樹中根結(jié)點的子樹森林c c、先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林、先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林森林的先序遍歷森林的先序遍歷A A（DEDE）（）（BCFGHIBCFGHI）A DE BCFGHIA DE BCFGHI森林的先序遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹A AB BD DC CF FG GE EI IH H若森林非空，則可以按照下述規(guī)則遍歷：若森林非空，則可以按照下述規(guī)則遍歷：a a、中序遍歷第一棵樹中根結(jié)點的子樹森林、中序遍歷第一棵樹中根結(jié)點的子樹森林b b、訪問森林中第一棵樹的根結(jié)點、訪問森林中第一棵樹的根結(jié)點c c、中序遍歷除

30、去第一棵樹之后剩余的樹構(gòu)成的森林、中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林森林的中序遍歷森林的中序遍歷（DEDE ）A A （BCFGHIBCFGHI）DE A DE A （B B （FGHIFGHI C C）DE A B GHIF CDE A B GHIF C森林的中序遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹A AB BD DC CF FG GE EI IH H若森林非空，則可以按照下述規(guī)則遍歷：若森林非空，則可以按照下述規(guī)則遍歷：a a、對第一棵樹從根結(jié)點起按層從左到右依次訪問結(jié)點、對第一棵樹從根結(jié)點起按層從左到右依次訪問結(jié)點b b、按層訪問森林中除去第一棵樹之后剩余的樹構(gòu)成的森林、按層訪問森林中除去

31、第一棵樹之后剩余的樹構(gòu)成的森林森林的層次遍歷森林的層次遍歷ADE B CFGHIADE B CFGHI森林的層次遍歷數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹練習(xí)：寫出下面森林的先序、后序和層次遍歷BJDCFGEIH數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹RABDCFGEIHRABDCFGEIH（1）加線：在各兄弟間加一連線）加線：在各兄弟間加一連線（2）去線：對任何結(jié)點，除了其最左子樹）去線：對任何結(jié)點，除了其最左子樹之外，去掉該結(jié)點與其他子樹之間的連線之外，去掉該結(jié)點與其他子樹之間的連線（3）調(diào)整二叉樹的層次）調(diào)整二叉樹的層次樹和二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹（1）將森林中的每一棵樹轉(zhuǎn)換成二叉樹（2）將每棵二叉樹按左孩子右兄弟的規(guī)則連接成一棵二叉樹ABDCFGEIHABDCFGEIH森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ABJDCFGEIH練習(xí)：寫出下面這兩棵樹轉(zhuǎn)換為二叉樹和森林E EC CD DB BF FA AG GH HJ JI I數(shù)據(jù)結(jié)構(gòu)5 樹和二叉樹ABDCFGEIHABDCFGEIH森林的先序遍歷森林的先序遍歷：A DE BCFGHI森林的中序遍歷森林的中序遍歷：DE A B GHIF C二叉樹的先序遍歷二叉樹的先序遍歷：A DE BCFGHI二叉樹的中序遍歷二叉樹的中序遍歷