第五章樹和二叉樹(文件)
【正文】 ) 重復(fù)以下步驟 , 直到 F中僅剩下一棵樹為止： ① 在 F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹 , 做為左、右子樹構(gòu)造一棵新的二叉樹。 2022/8/17 37 赫夫曼樹的構(gòu)造過程 2022/8/17 38 赫夫曼編碼 主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。 2022/8/17 39 化整為 { 2, 7, 4, 5 }，以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立赫夫曼樹。 總編碼長度正好等于 赫 夫曼樹的帶權(quán)路徑長 度 WPL。 int lchild,rchild,parent。 int small1,small2,f。 tree[i].lchild=0。i=n。 } for (i=n+1。 small1=MAXVAL。j++) if (tree[j].parent == 0) if (tree[j].weightsmall1) { small2=small1。 } else if (tree[j].weightsmall2) { small2=tree[j].weight。 tree[i].lchild=p1。 int start。 2022/8/17 43 赫夫曼編碼的存儲(chǔ)結(jié)構(gòu) 序號(hào) bits ch start 1 1 1 1 1 a 2 2 0 b 5 3 1 1 0 c 3 4 1 1 1 0 d 2 5 1 0 e 4 2022/8/17 44 赫夫曼編碼算法 (根據(jù)已構(gòu)成的赫夫曼樹，求出編碼 ) HUFFMANCODE(codetype code[], hufmtree tree[]) { int i,j,c,p。i++) { =n+1。 if (tree[p].lchild = = c) []=?0?。 } code[i]=cd。 scanf(“%d”,amp。 if (tree[i].lchild==0) { putchar(code[i].ch)。 } if (tree[i].lchild!=0) printf(“\nERROR\n”)。 } scanf(“%d”,amp。 while (b!=endflag) { if (b==0) i=tree[i].lchild。 int endflag=1。 c=p。 p=tree[i].parent。 for (i=1。 } codetype。 tree[i].weight=tree[p1].weight+ tree[p2].weight。 } tree[p1].parent=i。 p2=p1。 for (j=1。i++) { p1=0。f)。 tree[i].weight=0。i=m。 hufmtree tree[m+1]。解碼時(shí)不會(huì) 混淆。 A : 0 T : 10 C : 110 S : 111 它的總 編碼長度： 7*1+5*2+( 2+4 )*3 = 35。 若給每個(gè)字符以等長編碼 A : 00 T : 10 C : 01 S : 11 則總編碼長度為 ( 2+7+4+5 ) * 2 = 36. 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。 ② 在 F中刪去這兩棵二叉樹。在赫夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。 三、 B樹 2022/8/17 25 357 045 112 236 392 490 560 631 670 008
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1