1、第五章 樹與二叉樹,樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu) 5.1 樹的定義 定義 定義：樹(tree)是n(n0)個結(jié)點(diǎn)的有限集T，其中： 有且僅有一個特定的結(jié)點(diǎn)，稱為樹的根(root) 當(dāng)n1時，其余結(jié)點(diǎn)可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree) 特點(diǎn)： 樹中至少有一個結(jié)點(diǎn)根 樹中各子樹是互不相交的集合,根,子樹,基本術(shù)語 結(jié)點(diǎn)(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支 結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹數(shù) 葉子(leaf)度為0的結(jié)點(diǎn) 孩子(child)結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩

2、子 雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的 兄弟(sibling)同一雙親的孩子 樹的度一棵樹中最大的結(jié)點(diǎn)度數(shù) 結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層 深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù) 森林(forest)m(m0)棵互不相交的樹的集合,結(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為兄弟,樹的度：3,結(jié)點(diǎn)A的層次：1 結(jié)點(diǎn)M的層次：4,樹的深度：4,結(jié)點(diǎn)F，G為堂兄弟 結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先,5

3、.2 二叉樹 定義 定義：二叉樹是n(n0)個結(jié)點(diǎn)的有限集，它或為空樹(n=0)，或由一個根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成 特點(diǎn) 每個結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn)) 二叉樹的子樹有左、右之分，且其次序不能任意顛倒 基本形態(tài),二叉樹性質(zhì) 性質(zhì)1：,證明：用歸納法證明之 i=1時，只有一個根結(jié)點(diǎn)， 是對的 假設(shè)對所有j(1ji)命題成立，即第j層上至多有 個結(jié)點(diǎn) 那么，第i-1層至多有 個結(jié)點(diǎn) 又二叉樹每個結(jié)點(diǎn)的度至多為2 第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即 故命題得證,性質(zhì)2：深度為k的二叉樹至多有 個結(jié)點(diǎn)(k1),證明：由性質(zhì)1，可得深度為k 的二叉

4、樹最大結(jié)點(diǎn)數(shù)是,性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1,證明：n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù) 因為：二叉樹中所有結(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個 分支進(jìn)入 設(shè)B為分支總數(shù)，則n=B+1 又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,幾種特殊形式的二叉樹 滿二叉樹 定義：,特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) 完全二叉樹 定義：深度為k，有n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹

5、中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時，稱為 特點(diǎn) 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) 對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1 性質(zhì) 性質(zhì)4：,性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1in)，有： (1) 如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點(diǎn)i無左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點(diǎn)i無右孩子；如果2i+1n，則其右孩子是2i+1,5.3 二叉樹的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號，依次存放二叉樹中的數(shù)據(jù)元素

6、 特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲位置中 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹,鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; Bnode,*Btree;,在n個結(jié)點(diǎn)的二叉鏈表中，有n+1個空指針域,typedef struct node datatype data; struct node *lchild, *rchild, *parent; JD;,三叉鏈表,二叉鏈表的生成,方法: 1 輸入根結(jié)點(diǎn); 2 若左子樹不空，輸入左子樹; 3 若右子樹不空，輸入右子樹,Btree createb

7、tree(Btree bt,int k) datatype b; Btree t; Bnode *p; printf(“Please input node b: ”); scanf (“%d” , ,5.4 樹和二叉樹的遍歷 樹的遍歷 遍歷按一定規(guī)律走遍樹的各個頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個線性排列 常用方法 先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn) 按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，第n層的結(jié)點(diǎn),先序遍歷：,后序遍歷：,層次遍歷：,A,B,E

8、,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,二叉樹的遍歷 方法 先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹 中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn) 按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn),D L R,先序遍歷序列：A B D C,先序遍歷:,L D R,中序遍歷序列：B D A C,中序遍歷:,L R D,后序遍歷序列： D B C A,后序遍歷:,先序遍歷：,中序遍歷：,后序遍歷：,

9、層次遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,算法 遞歸算法,void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); ,void inorder(JD *bt) if(bt!=NULL) inorder(bt-lchild); printf(%dt,bt-data); inorder(bt-rchild); ,voi

10、d postorder(JD *bt) if(bt!=NULL) postorder(bt-lchild); postorder(bt-rchild); printf(%dt,bt-data); ,void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,非遞歸算法,Ch5_4.c Ch5_40.C,后序遍歷非遞歸算法,定義： 前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的

11、結(jié)點(diǎn)互稱為 線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針稱為 線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫 線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫 實(shí)現(xiàn) 在有n個結(jié)點(diǎn)的二叉鏈表中必定有n+1個空鏈域 在線索二叉樹的結(jié)點(diǎn)中增加兩個標(biāo)志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驅(qū) rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 結(jié)點(diǎn)定義：,typedef struct node int data; int lt, rt; struct node *lc, *rc; JD;,5.5 線索二叉樹,0,0,0,0,1,1,1,1,

12、1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,頭結(jié)點(diǎn)： lt=0, lc指向根結(jié)點(diǎn) rt=1, rc指向遍歷序列中最后一個結(jié)點(diǎn) 遍歷序列中第一個結(jié)點(diǎn)的lc域和最后 一個結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn),算法 按中序線索化二叉樹,Ch5_20.c,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL)

13、si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=

14、t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,JD *zxxsh(JD *bt) JD *p,*p

15、r,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-

16、rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出:B,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NUL

17、L) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,輸出:B,i,P-C,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-l

18、c; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,P-C,輸出:B,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t

19、; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C,JD *zxxsh(JD *bt)

20、 JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr

21、-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr

22、; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL)

23、 si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A,P-D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-

24、lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B

25、 C A,P-D,P-E,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc;

26、while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A,P-D,P-E,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,

27、p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A E,P-D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t;

28、 else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A E,P-D,JD *zxxsh(JD *bt) JD *p,*pr,

29、*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc

30、=pr; return(t); ,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A E D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr

31、-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,i,輸出: B C A E D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL)

32、si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,Ch5_20.c,輸出: B C A E D,算法 按中序線索化二叉樹 遍歷中序線索二叉樹,Ch5_20.c,在中序線索二叉樹中找結(jié)點(diǎn)后繼的方法： （1）若rt=1, 則rc域直接指向其后繼 （2）若

33、rt=0, 則結(jié)點(diǎn)的后繼應(yīng)是其右子樹的左鏈尾（lt=1)的結(jié)點(diǎn),在中序線索二叉樹中找結(jié)點(diǎn)前驅(qū)的方法： （1）若lt=1, 則lc域直接指向其前驅(qū) （2）若lt=0, 則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子樹的右鏈尾（rt=1)的結(jié)點(diǎn),遍歷算法應(yīng)用 按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ,求二叉樹深度算法,Ch5_5.c ch5_6.c,Ch5_1.c,統(tǒng)計二叉樹中葉子結(jié)點(diǎn)個數(shù)算法,5.6 二叉樹的應(yīng)用 哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹 定義 路徑：從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成這兩個結(jié)點(diǎn)間的 路徑長度：路徑上的分支數(shù) 樹的路徑長度：從樹根到每

34、一個結(jié)點(diǎn)的路徑長度之和 樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點(diǎn)的路徑長度之和,Huffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點(diǎn)的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫,例 有4個結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點(diǎn)的二叉樹,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,構(gòu)造Huffman樹的方法Huffman算法 構(gòu)造Huffman樹步驟 根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令起權(quán)值為wj 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子

35、樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和 在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹,例 w=5, 29, 7, 8, 14, 23, 3, 11,Huffman算法實(shí)現(xiàn),Ch5_8.c,一棵有n個葉子結(jié)點(diǎn)的Huffman樹有2n-1個結(jié)點(diǎn) 采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組 結(jié)點(diǎn)類型定義,typedef struct int data; int pa,lc,rc; JD;,#define M 50 #define MAX 100 void huffman(int n,int w,JD t) int i,j,k,x1,x2,m1,m2; for(i=1;i(2*n);i+) ti.pa=ti.lc=ti.rc=0; if(i=n) ti.data=wi; else ti.data=0; for(i=1;in;i+) m1=m2=MAX; x1=x2=0; for(j=1;j(n+i);j+) if(tj.datam1) ,Ch5_8.c,Huffman樹應(yīng)用 最佳判定樹,Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼 思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短 編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其