第五章樹(shù)和二叉樹(shù)PPT課件

1、第五章 樹(shù)和二叉樹(shù)5.1 樹(shù)和二叉樹(shù)的概念5.2 樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義5.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)5.5 樹(shù)和森林5.6 哈夫曼樹(shù)及其應(yīng)用 樹(shù)是一類(lèi)重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)的定義u 樹(shù)的定義樹(shù)(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)；或?yàn)榉强諛?shù)，對(duì)于非空樹(shù)T： (1) 有且僅有一個(gè)特定的稱(chēng)為根(Root)的結(jié)點(diǎn); (2) 除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1, T2, , Tm, 其中每一個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)（SubTree）。5.1 樹(shù)

2、和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義ABKLEFHMIJDGC嵌套集合表示法A B E K L F C G D H M I J凹入表示法廣義表表示法：(A( B(E(K,L),F), C(G), D(H(M),I,J) )5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義u樹(shù)的基本術(shù)語(yǔ)l結(jié)點(diǎn)結(jié)點(diǎn)(node)樹(shù)中的一個(gè)獨(dú)立單元，包括數(shù)據(jù)元素及若干指向其子樹(shù)的分支l結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹(shù)數(shù)l樹(shù)的度樹(shù)的度一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)l葉子葉子(leaf)度為0的結(jié)點(diǎn)l非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)-度不為0的結(jié)

3、點(diǎn)（分支結(jié)點(diǎn)）l孩子孩子(child)結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子l雙親雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親l兄弟兄弟(sibling)同一雙親的孩子l祖先祖先從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)l子孫子孫以某結(jié)點(diǎn)為根的樹(shù)中任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義ABCDEFGHIJKLMl堂兄弟堂兄弟其雙親在同一層次的結(jié)點(diǎn)稱(chēng)為堂兄弟l結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層l樹(shù)的深度樹(shù)的深度(depth)樹(shù)中結(jié)點(diǎn)的最大層次數(shù)l有序樹(shù)有序樹(shù)樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左到右是有序的（不能互換）l無(wú)序樹(shù)無(wú)序樹(shù)結(jié)點(diǎn)各子樹(shù)可互換位

4、置l森林森林(forest)m(m0)棵互不相交的樹(shù)的集合5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義ABCDEFGHIJKLMABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義u二叉樹(shù)定義二叉樹(shù)(Binary Tree) 是n(n0)個(gè)結(jié)點(diǎn)所構(gòu)成的集合，它或?yàn)榭諛?shù)(n = 0)；或?yàn)榉强諛?shù)，對(duì)于非空樹(shù)T

5、：(1) 有且僅有一個(gè)稱(chēng)之為根的結(jié)點(diǎn)；(2) 除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集T1和T2，分別稱(chēng)為T(mén)的左子樹(shù)和右子樹(shù)，且T1和T2本身又都是二叉樹(shù)。二叉樹(shù)基本特點(diǎn)：結(jié)點(diǎn)的度小于等于2有序樹(shù)（子樹(shù)有序，不能顛倒）二叉樹(shù)的五種不同形態(tài)5.1 樹(shù)和二叉樹(shù)的定義樹(shù)和二叉樹(shù)的定義u樹(shù)的抽象數(shù)據(jù)類(lèi)型定義ADT Tree 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱(chēng)為空樹(shù)； 若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H，H是如下二元關(guān)系：(1)在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；(2)在D-root 剩下的數(shù)據(jù)元素，可分為m(m0)個(gè)互不相

6、交的有限集T1,T2,Tm個(gè)劃分，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree)基本操作P： InitTree(&T); / 構(gòu)造空樹(shù)T DestoryTree(&T); / 銷(xiāo)毀樹(shù)T CreateTree(&T,definition); / 按definition構(gòu)造樹(shù)T樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義5.2 樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義ClearTree(&T); / 將樹(shù)T清為空樹(shù)TreeEmpty(T); / 若樹(shù)T為空，則返回true, 否則false;TreeDepth(T); /獲得樹(shù)T的深度Root(T);

7、/獲得樹(shù)T的根Value(T, cur_e); /獲得樹(shù)T中cur_e結(jié)點(diǎn)的值A(chǔ)ssign(T, cur_e,value); / 把結(jié)點(diǎn)cur_e賦值為valueParent(T, cur_e); /獲得cur_e的雙親結(jié)點(diǎn)LeftChild(T,cur_e); /獲得cur_e的最左孩子結(jié)點(diǎn)RightSibling(T,cur_e); /獲得cur_e的右兄弟結(jié)點(diǎn)InsertChild(&T, p, i, c); / 插入c為樹(shù)T中p結(jié)點(diǎn)的第i棵子樹(shù)DeleteChild(&T, p, i); / 刪除樹(shù)T中p結(jié)點(diǎn)的第i棵子樹(shù)TraverseTree(T); / 按某種次序?qū)?/p>

8、樹(shù)T的每個(gè)結(jié)點(diǎn)訪問(wèn)一次 ADT Tree5.2 樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義u二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義ADT BinaryTree 數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D=,則R= ,稱(chēng)BinaryTree為空二叉樹(shù);若D ,則R=H,H是如下二元關(guān)系:(1) 在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root,它在關(guān)系H下 無(wú)前驅(qū)。(2)若D-root ,則存在D-root=Dl,Dr,且DlDr =;(3)若Dl ,則Dl中存在唯一的元素xl,H,且存在 Dl上的關(guān)系HlH; 若Dr ,則Dr中存在唯一的元素xr,H,且存在 Dr上的關(guān)系HrH;

9、H=, ,Hl, Hr;(4) (Dl, Hl)是一棵符合本定義的二叉樹(shù),稱(chēng)為根的左子樹(shù), (Dr, Hr )是一棵符合本定義的二叉樹(shù),稱(chēng)為根的右子樹(shù)。5.2 樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義注意:表示元素與集合的從屬關(guān)系； 代表一個(gè)集合是另外一個(gè)集合的子集。 H、 Hl、 Hr都是關(guān)系的集合?；静僮鱌：InitBiTree( &T ); / 構(gòu)造空二叉樹(shù)TDestroyBiTree( &T );/銷(xiāo)毀二叉樹(shù)TCreateBiTree(&T, definition)；/按definition構(gòu)造二叉樹(shù)TPreOrderTraverse( T )

10、; /先序遍歷T。InOrderTraverse( T ); /中序遍歷T。PostOrderTraverse( T ); /后序遍歷T。 ADT BinaryTree;5.2 樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義二叉樹(shù)的性質(zhì)l性質(zhì)1：(1)i i-1在二叉樹(shù)的第i層上至多有2 個(gè)結(jié)點(diǎn)l性質(zhì)2：深度為k的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)(k1)12 kl性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明: 設(shè)1度結(jié)點(diǎn)數(shù)為n1, 總結(jié)點(diǎn)數(shù)為n, 分支數(shù)為B則 n = n0 + n1 + n2; n = B + 1;/ 結(jié)點(diǎn)數(shù)比分支數(shù)多1又 B

11、= n1 + 2n2 n = n1 + 2n2 + 1 = n0 + n1 + n2 n0 = n2 + 15.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)幾種特殊形式的二叉樹(shù)滿二叉樹(shù)定義：滿二叉樹(shù)。1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為k一棵深度為k且有2特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹(shù)定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為完全二叉樹(shù)。特點(diǎn) 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)(最深的兩層) 對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為i，則其左分支下子孫的最大層次必為i或i+1（左邊不比右邊?。﹍性質(zhì)4：1nlog叉樹(shù)

12、的深度為具有n個(gè)結(jié)點(diǎn)的完全二25.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)不大于不大于x的最大整數(shù)的最大整數(shù) x123114589121367101415滿二叉樹(shù)123114589126710完全二叉樹(shù)1234567123456非完全二叉樹(shù)非完全二叉樹(shù)5.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)l 性質(zhì)5：如果一棵完全二叉樹(shù)有n個(gè)結(jié)點(diǎn)，且結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有： (1) 如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i

13、+1n，則其右孩子是2i+15.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)123114589126710完全二叉樹(shù)注意注意:雙親節(jié)點(diǎn)雙親節(jié)點(diǎn)序號(hào)序號(hào)為為x，如果存在，左孩子節(jié)點(diǎn)序號(hào)，如果存在，左孩子節(jié)點(diǎn)序號(hào)2x，右孩子節(jié)點(diǎn)序號(hào)為，右孩子節(jié)點(diǎn)序號(hào)為2x+1u二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)l順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中 浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 115.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)l鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈

14、表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;lchild data rchild ABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域 AB C D E F G5.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)n n0 0 = n = n2 2 + 1 + 1練習(xí)：證明結(jié)論 三叉鏈表typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriT

15、Node,*TriTree;lchild data parent rchildABCDEFG A B C D E F G5.3 二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)遍歷二叉樹(shù)和線索二叉樹(shù)遍歷定義指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)(又稱(chēng)周游)。u遍歷二叉樹(shù) 遍歷二叉樹(shù)的方法 :l先序遍歷:先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹(shù)、右子樹(shù)l中序遍歷:先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)l后序遍歷:先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)DLRDLR、LDR、LRDDRL、RDL、RLD5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ADBCD L RAD L RD L RBD

16、CD L R先序遍歷序列：A B D C先序遍歷:5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)說(shuō)出先序順序？ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f前綴表示中綴表示后綴表示5.4 遍歷二叉樹(shù)和線

17、索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)若二叉樹(shù)中各結(jié)點(diǎn)的值均不相同，則：u已知前序序列和中序序列，二叉樹(shù)可以唯一確定；u已知后序序列和中序序列，二叉樹(shù)可以唯一確定；u已知前序序列和后序序列，二叉樹(shù)不一定能唯一確定。 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)例:已知一棵二叉樹(shù)的 中序序列： BDCEAFHG 后序序列： DECBHGFA 請(qǐng)畫(huà)出這棵二叉樹(shù)。（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)注意：后序序列的最后一個(gè)一定是根，子樹(shù)也一樣注意：后序序列的最后一個(gè)一定是根，子樹(shù)也一樣 確定根

18、后，可以依據(jù)確定根后，可以依據(jù)中序序列中序序列確定左右子樹(shù)確定左右子樹(shù)l算法 遞歸算法void PreOrder(BiTree T) if (T!=NULL) coutdata; PreOrder(T-lchild); PreOrder(T-rchild); 先序遍歷void InOrder(BiTree T) if (T!=NULL) InOrder(Tlchild); coutdata; InOrder(T-rchild); 中序遍歷void PostOrder(BiTree T) if (T!=NULL) PostOrder(T-lchild); PostOrder(T-rchild);

19、 coutdata; 后序遍歷5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)void PreOrder(BiTree T) if (T!=NULL) cout data; PreOrder(T-lchild); PreOrder(T-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBPrint (B);pre(T L);BTAPrint (A);pre(T L);ATDPrint (D);pre(T L);DTCPrint (C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空

20、返回pre(T R);先序序列:A B D C5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 中序非遞歸算法void InOrder(BiTree T) int i=0; BiTree p, sM; / i和sM構(gòu)成一個(gè)棧，M為某常數(shù) p = T; / 根結(jié)點(diǎn) do while ( p != NULL ) / 沿左子樹(shù)找到第一個(gè)空結(jié)點(diǎn)，并記錄下訪問(wèn)過(guò)的結(jié)點(diǎn) si+ = p; / 入棧 push(s,p) p=p-lchild; if (i0) / 棧不空 p = s-i; / 出棧 pop(s,p) coutdata; / 訪問(wèn)該結(jié)點(diǎn) p=p-rchild; / 找該結(jié)點(diǎn)的右子樹(shù)的根 w

21、hile( i0 | p != NULL ); / 棧不空 或 還有末處理的結(jié)點(diǎn)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 非遞歸算法執(zhí)行過(guò)程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問(wèn)：C(4)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)pABCDEFGiP-A訪問(wèn)：C B(5)ABCDEFGiP-AP-D訪問(wèn)：C Bp(6)ABCDEFGiP-AP-DP-E訪問(wèn)：C Bp(7)ABCDEFGiP-AP-D訪問(wèn)：C B Ep(8)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉

22、樹(shù)和線索二叉樹(shù)ABCDEFGiP-AP-DP-G訪問(wèn)：C B EP=NULL(9)ABCDEFGiP-A訪問(wèn)：C B E G Dp(11)ABCDEFGiP-AP-F訪問(wèn)：C B E G Dp(12)ABCDEFGiP-AP-D訪問(wèn)：C B E Gp(10)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGiP-A訪問(wèn)：C B E G D Fp=NULL(13)ABCDEFGi訪問(wèn)：C B E G D F Ap(14)ABCDEFGi訪問(wèn)：C B E G D F Ap=NULL(15)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)l 遍歷算法應(yīng)用按先序遍歷序列建立二叉樹(shù)的

23、二叉鏈表，已知先序序列為： A B C # # D E # G # # F # # #ABCDEFG A B C D E F G void CreateBiTree( BiTree &T) cin ch; if (ch=#) T=NULL; else T= new BiTNode; T-data=ch; CreateBiTree(T-lchild); CreateBiTree (T-rchild); 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)注：如不給出空節(jié)點(diǎn)，則不能確定二叉樹(shù)計(jì)算二叉樹(shù)的深度。(1) 如果是空樹(shù)，則深度為0；(2) 否則，遞歸計(jì)算左子樹(shù)的深度記為m， 遞歸計(jì)

24、算右子樹(shù)的深度記為n， 二叉樹(shù)的深度則為m與n的較大者加1。 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)int Depth( BiTree T ) int m,n; if (T=NULL) return 0; / 如果是空樹(shù)，則深度為0 else m=Depth(T-lchild); /遞歸計(jì)算左子樹(shù)的深度記為m n =Depth(T-rchild); /遞歸計(jì)算右子樹(shù)的深度記為nif ( m n ) return m+1; /二叉樹(shù)的深度則為m與n的較大者加1else return n+1; 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)計(jì)算二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)。(1)如果是空

25、樹(shù)，則結(jié)點(diǎn)個(gè)數(shù)為0；(2)非空，結(jié)點(diǎn)個(gè)數(shù)為:左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)+1int NodeCount(BiTree T) if (!T) return 0; return NodeCount(T-lchild)+NodeCount(T-rchild)+1; 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)。(1)如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0；(2)如果是葉子結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為1；(3)否則，為左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)。int LeadCount(BiTree T) if( !T ) return 0; /如果是空樹(shù)返回0 if ( !

26、T-lchild & !T-rchild ) return 1; /葉子結(jié)點(diǎn)返回1 return LeafCount(T-lchild) + LeafCount(T-rchild);5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)u 線索二叉樹(shù)l定義：前驅(qū)與后繼：在二叉樹(shù)的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱(chēng)為前驅(qū)與后繼。線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針?lè)Q為線索。線索二叉樹(shù)：加上線索的二叉鏈表表示的二叉樹(shù)叫線索二叉樹(shù)。線索化：對(duì)二叉樹(shù)按某種遍歷次序使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫線索化。5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)u 線索二叉樹(shù)l實(shí)現(xiàn)1增加兩個(gè)指針域，一個(gè)指

27、向前驅(qū)，一個(gè)指向后續(xù)5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)lchild pre data next rchild特點(diǎn)：特點(diǎn)： 每個(gè)節(jié)點(diǎn)增加存儲(chǔ)空間占用量為每個(gè)節(jié)點(diǎn)增加存儲(chǔ)空間占用量為2 2* *sizeofsizeof(pre),(pre),一般為一般為8 8個(gè)字節(jié)個(gè)字節(jié) 算法設(shè)計(jì)容易算法設(shè)計(jì)容易u(yù) 線索二叉樹(shù)l實(shí)現(xiàn)2在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈域在線索二叉樹(shù)的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域 ltag: 若 ltag =0, lchild 域指向左孩子；若 ltag=1, lchild域指向其前驅(qū) rtag: 若 rtag =0, rchild 域指向右孩子；若 rtag=1

28、, rchild域指向其后繼5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)lchild ltag data rtag rchild注注: :加上兩個(gè)標(biāo)志后，實(shí)現(xiàn)空指加上兩個(gè)標(biāo)志后，實(shí)現(xiàn)空指針域的充分利用，輔助二叉樹(shù)針域的充分利用，輔助二叉樹(shù)遍歷，標(biāo)志占用空間最小為遍歷，標(biāo)志占用空間最小為0 0結(jié)點(diǎn)定義：typedef struct BiThrNode TElemType data; int ltag, rtag; struct BiThrNode *lchild, *rchild; BiThrNode, *BiThrTree;lchild ltag data rtag rchildlta

29、g: 若 ltag=0, lchild域指向左孩子； 若 ltag=1, lchild域指向其前驅(qū)。rtag: 若 rtag=0, rchild域指向右孩子； 若 rtag=1, rchild域指向其后繼。 5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ABCDE A B D C ET先序序列：ABCDE先序線索二叉樹(shù)00001111 11ABCDENULL5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)先序線索化：先序線索化： 指針指針 線索線索線索化ABCDE A B D C ET中序序列：BCAED中序線索二叉樹(shù)0000111111ABCDENULLNULL5.4 遍歷二叉樹(shù)和

30、線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)中序中序線索化：線索化： 指針指針 線索線索線索化ABCDE A B D C ET后序序列：CBEDA后序線索二叉樹(shù)0000111111ABCDENULL5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)后后序線索化：序線索化： 指針指針 線索線索線索化ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù) 0 1頭結(jié)點(diǎn)：ltag=0, lchild指向根結(jié)點(diǎn)rtag=1, rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn) A B

31、 D C ET中序序列：BCAED中序線索二叉樹(shù)00001111115.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)加頭結(jié)點(diǎn)在中序線索二叉樹(shù)中找結(jié)點(diǎn)后繼的方法：（1）若rtag=1, 則rchild域直接指向其后繼（2）若rtag=0, 則結(jié)點(diǎn)的后繼應(yīng)是其右子樹(shù)的左鏈尾(ltag=1)的結(jié)點(diǎn)（即中序遍歷右子樹(shù)的第一個(gè)節(jié)點(diǎn)）在中序線索二叉樹(shù)中找結(jié)點(diǎn)前驅(qū)的方法：（1）若ltag=1, 則lchild域直接指向其前驅(qū)（2）若ltag=0, 則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子樹(shù)的右鏈尾(rtag=1)的結(jié)點(diǎn)（即中序遍歷左子樹(shù)的最后一個(gè)節(jié)點(diǎn)）ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1

32、 t中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù) 0 15.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)查找后繼和前驅(qū)l 算法 遍歷中序線索二叉樹(shù)void InOrderTraverse_Thr(BiThrTree T) BiThrNode *p; p=T-lchild; while ( p!= T ) while( p-ltag=0 ) p = p-lchild; cout data; while( (p-rtag =1)&(p-rchild!=T) p=p-rchild; cout data; p=p-rchild; 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1

33、T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù) 0 15.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)中序的訪問(wèn)規(guī)則：一旦訪問(wèn)了一個(gè)節(jié)點(diǎn)，則下一次訪問(wèn)一定是右子樹(shù)中序的訪問(wèn)規(guī)則：一旦訪問(wèn)了一個(gè)節(jié)點(diǎn)，則下一次訪問(wèn)一定是右子樹(shù)不用棧和遞歸，實(shí)現(xiàn)了二叉樹(shù)遍歷不用棧和遞歸，實(shí)現(xiàn)了二叉樹(shù)遍歷 按中序線索化二叉樹(shù)(遞歸算法)ABCDE輸出: B C A E D A B D C Ethrt 0 11111110000pre：上次訪問(wèn)節(jié)點(diǎn)的指針；p：本次訪問(wèn)節(jié)點(diǎn)的指針；/遞歸方式線索化一個(gè)子遞歸方式線索化一個(gè)子樹(shù)樹(shù)void InThreading( BiThrTree p ) if ( p ) InThr

34、eading( p-lchild ); if ( !p-lchild ) /左孩子為空 p-lagt=1; p-lchild = pre; if ( !pre-rchild) /右孩子為空 pre-tag=1; pre-rchild = p; pre = p; InThreading( p-rchild); t5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 按中序線索化二叉樹(shù)(遞歸算法)ABCDE輸出: B C A E D A B D C Ethrt 0 11111110000pre：上次訪問(wèn)節(jié)點(diǎn)的指針； /將T線索化為一個(gè)帶頭結(jié)點(diǎn)的二叉樹(shù)thrtStatus InOrderThread

35、ing( BiThrTree &thrt, BiThrTree T ) if ( !(thrt=new BiThrNode) / 建頭結(jié)點(diǎn)return OVERFLOW; thrt-ltag = 0; thrt-rtag = 1; thrt-rchild = thrt; if( !T ) /T為空 thrt-lchild = thrt; else thrt-lchild = T; pre = thrt; InThreading(T); pre-rchild = thrt; pre-rtag = 1; thrt-rchild = pre; return OK;t5.4 遍歷二叉樹(shù)和線索二

36、叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 按中序線索化二叉樹(shù)(非遞歸算法)BiThrTree InOrderThread(BiThrTree bt) /思路：在中序遍歷過(guò)程中線索化 BiThrTree p,pre,sM,t; int i=0; t=new BiThrNode; t-ltag=0; t-rtag=1; t-rchild=t; if (bt=NULL) t-lchild=t; else t-lchild=bt; pre=t; p=bt; / pre用作指向前驅(qū)結(jié)點(diǎn) do while( p!=NULL) si+=p; p=p-lchild; if( i0 ) p=s-i; / cout data;

37、 if( p-lchild=NULL) p-ltag=1; p-lchild=pre; if(pre-rchild = NULL) pre-rtag=1; pre-rchild=p; pre=p; p=p-rchild; while( i0 | p!=NULL); pre-rchild=t; pre-rtag=1; t-rchild=pre; /最后設(shè)置頭結(jié)點(diǎn)和最后訪問(wèn)節(jié)點(diǎn) return(t);5.4 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)u樹(shù)的存儲(chǔ)結(jié)構(gòu)l雙親表示法實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域： 數(shù)據(jù)域:存放結(jié)點(diǎn)本身信息 雙親域:指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：

38、找雙親容易，找孩子難typedef struct node ElemType data; int parent; / 雙親位置 PTNode; / 結(jié)點(diǎn)結(jié)構(gòu)typedef struct PTNode nodesM; int n; PTree; / 樹(shù)結(jié)構(gòu)5.5 樹(shù)和森林樹(shù)和森林abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)樹(shù)的雙親表示法5.5 樹(shù)和森林樹(shù)和森林l孩子表示法多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根 結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹(shù)的度D 結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度

39、d孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)信息用單鏈表存儲(chǔ)，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表data child1 child2 . childDdata degree child1 child2 . childd5.5 樹(shù)和森林樹(shù)和森林孩子結(jié)點(diǎn)：typedef struct node int child; /該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點(diǎn) *ChildPtr;結(jié)點(diǎn)信息：typedef struct tnode ElemType data; /數(shù)據(jù)域 ChildPtr fc; /指向第一個(gè)孩子結(jié)點(diǎn) CTBox;樹(shù)： typedef struct C

40、TBox nodesM;int n, r; / 結(jié)點(diǎn)數(shù)和根的位置 CTree;5.5 樹(shù)和森林樹(shù)和森林abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點(diǎn)樹(shù)的孩子鏈表表示法5.5 樹(shù)和森林樹(shù)和森林 帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi樹(shù)的帶雙親的孩子鏈表表示法5.5 樹(shù)和森林樹(shù)和森林l孩子兄弟表示法（二叉樹(shù)表示法）實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)特點(diǎn)操作容易破壞

41、了樹(shù)的層typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;abcdefhgi a b c d e f g h i5.5 樹(shù)和森林樹(shù)和森林樹(shù)與二叉樹(shù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù) A B C D E A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋5.5 樹(shù)和森林樹(shù)和森林理解成樹(shù)理解成二叉樹(shù)存儲(chǔ)結(jié)構(gòu)樹(shù)和二叉樹(shù)的相互轉(zhuǎn)換 樹(shù)轉(zhuǎn)換成二叉樹(shù)后，可以利用二叉樹(shù)的某些性質(zhì)進(jìn)行算法設(shè)計(jì)。5.5 樹(shù)和森林樹(shù)和森林l 將樹(shù)轉(zhuǎn)換成二叉樹(shù) 加線：在兄弟之間加一連線

42、抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系 旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空5.5 樹(shù)和森林樹(shù)和森林l 將二叉樹(shù)轉(zhuǎn)換成樹(shù) 加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來(lái) 抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線 調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI5.5 樹(shù)和森林樹(shù)和森林l森林轉(zhuǎn)換成二叉樹(shù)

43、將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù) 將每棵樹(shù)的根結(jié)點(diǎn)用線相連 以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.5 樹(shù)和森林樹(shù)和森林l 二叉樹(shù)轉(zhuǎn)換成森林 抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù) 還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.5 樹(shù)和森林樹(shù)和森林u樹(shù)的遍歷l遍歷按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所

44、有結(jié)點(diǎn)的一個(gè)線性排列l(wèi)常用方法 先根（序）遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù) 后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)5.5 樹(shù)和森林樹(shù)和森林ABCDEFGHIJKLMNO先根(序)遍歷：ABE F I GCDHJ KL NOM樹(shù)的遍歷:5.5 樹(shù)和森林樹(shù)和森林先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)相當(dāng)于與二叉樹(shù)的什么訪問(wèn)？相當(dāng)于與二叉樹(shù)的什么訪問(wèn)？ABCDEFGHIJKLMNO后根(序)遍歷：E I F G B C J K N O L M H D A樹(shù)的遍歷:5.5 樹(shù)和森林樹(shù)和森林先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)相當(dāng)于與二叉樹(shù)的什么訪問(wèn)？相當(dāng)于

45、與二叉樹(shù)的什么訪問(wèn)？u森林的遍歷l 先序遍歷森林: 若森林非空;(1)訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);(2)先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林;(3)先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林;5.5 樹(shù)和森林樹(shù)和森林注：子樹(shù)森林就是一棵樹(shù)去掉根節(jié)點(diǎn)后形成的森林先序遍歷森林：ABCDE F GHI J相當(dāng)于先序遍歷森林對(duì)應(yīng)的二叉樹(shù)中序遍歷森林：BCDA F E H J I G5.5 樹(shù)和森林樹(shù)和森林u森林的遍歷l 中序遍歷森林: 若森林非空;(1)中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林;(2)訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn);(3)中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林;注：相當(dāng)于中序遍歷森林對(duì)應(yīng)的二叉

46、樹(shù)對(duì)于森林來(lái)說(shuō)，由于沒(méi)有根節(jié)點(diǎn)，因此利用森林對(duì)應(yīng)的二叉樹(shù)確定遍歷順序名字更合適哈夫曼樹(shù)及其應(yīng)用u哈夫曼樹(shù)(Huffman)帶權(quán)路徑長(zhǎng)度最短的樹(shù)l定義路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑路徑長(zhǎng)度：路徑上的分支數(shù)樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中：記作：kknkkklwlwwpl1Huffman樹(shù)：設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹(shù)叫哈夫曼樹(shù)5.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5

47、，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL15.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用，4nl構(gòu)造Huffman樹(shù)的方法Huffman算法n 構(gòu)造Huffman樹(shù)步驟 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令其權(quán)值為wj 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和 在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森

48、林中 重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)5.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611185.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422914871529581005.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用n Huffman算法實(shí)現(xiàn) 一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn) 采用順序存儲(chǔ)結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組 結(jié)點(diǎn)類(lèi)型定義typedef struct int weig