第五章樹和二叉樹(完整版)
【正文】 \n”,pdata)。 qrchild＝ prchild。 struct node *lchild,*rchild。 b=NULL。 // 插入該結(jié)點 }while(x!=1)。 } else { q=p。 // 被刪結(jié)點的右子樹作為 r的右子樹 rrchild=prchild。 } } 2022/8/17 24 一棵 m 階的 B樹滿足下列條件： 每個結(jié)點 至多有 m個 孩子； 根結(jié)點至少有兩個孩子（唯一例外的是只包含一個根 結(jié)點的 B樹）； 除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有 ? m/2? 個 孩子； 有 n+1個孩子的非葉結(jié)點恰好包含 n個關(guān)鍵字 (A0 , K1 , A1 , K2 , A2 , … K n, An)。 (2) 重復(fù)以下步驟 , 直到 F中僅剩下一棵樹為止： ① 在 F中選取兩棵根結(jié)點的權(quán)值最小的二叉樹 , 做為左、右子樹構(gòu)造一棵新的二叉樹。 2022/8/17 39 化整為 { 2, 7, 4, 5 }，以它們?yōu)楦魅~結(jié)點上的權(quán)值，建立赫夫曼樹。 int lchild,rchild,parent。 tree[i].lchild=0。 } for (i=n+1。j++) if (tree[j].parent == 0) if (tree[j].weightsmall1) { small2=small1。 tree[i].lchild=p1。 2022/8/17 43 赫夫曼編碼的存儲結(jié)構(gòu) 序號 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。 if (tree[p].lchild = = c) []=?0?。 scanf(“%d”,amp。 } if (tree[i].lchild!=0) printf(“\nERROR\n”)。 while (b!=endflag) { if (b==0) i=tree[i].lchild。 c=p。 for (i=1。 tree[i].weight=tree[p1].weight+ tree[p2].weight。 p2=p1。i++) { p1=0。 tree[i].weight=0。 hufmtree tree[m+1]。 A : 0 T : 10 C : 110 S : 111 它的總 編碼長度： 7*1+5*2+( 2+4 )*3 = 35。 ② 在 F中刪去這兩棵二叉樹。 三、 B樹 2022/8/17 25 357 045 112 236 392 490 560 631 670 008 040 052 110 135 142 212 237 240 279 378 381 388 393 396 400 435 471 492 502 553 2022/8/17 26 在 B樹中包含 j個關(guān)鍵字， j+1個指針的 結(jié)點，一般表示形式為： A0 , K1 , A1 , K2 , A2 , … K j , Aj 2022/8/17 2
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1