【正文】 small2=small1。 tree[i].lchild=0。 2022/8/17 39 化整為 { 2, 7, 4, 5 }，以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立赫夫曼樹(shù)。 } } 2022/8/17 24 一棵 m 階的 B樹(shù)滿(mǎn)足下列條件： 每個(gè)結(jié)點(diǎn) 至多有 m個(gè) 孩子； 根結(jié)點(diǎn)至少有兩個(gè)孩子（唯一例外的是只包含一個(gè)根 結(jié)點(diǎn)的 B樹(shù)）； 除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有 ? m/2? 個(gè) 孩子； 有 n+1個(gè)孩子的非葉結(jié)點(diǎn)恰好包含 n個(gè)關(guān)鍵字 (A0 , K1 , A1 , K2 , A2 , … K n, An)。 } else { q=p。 b=NULL。 qrchild＝ prchild。 中序線索二叉樹(shù)中，查找指定結(jié)點(diǎn) *p的中序后繼結(jié)點(diǎn) 2022/8/17 7 p R1 R2 Rk 最左下結(jié)點(diǎn) 2022/8/17 8 中序線索二叉樹(shù)中求中序后繼結(jié)點(diǎn)的算法 bithptr *INORDERNEXT(bithptr *p) { bithptr *q。 struct node *lchild,*rchild。 lchild ltag rtag data rchild 標(biāo)志位如果為 0，表示指針指向孩子結(jié)點(diǎn)，為 1表示指針為線索 2022/8/17 4 0 A 0 0 B 0 0 E 1 1 C 1 1 D 1 1 F 0 0 G 0 1 H 1 1 I 1 NULL NULL t 2022/8/17 5 中序線索化算法 INTHREAD(bithptr *p,bithptr *pre) // p為當(dāng)前結(jié)點(diǎn)， pre為 p的前驅(qū)結(jié)點(diǎn)，開(kāi)始調(diào)用時(shí) p為根結(jié)點(diǎn)指針， pre為 NULL { if (p!=NULL) { INTHREAD(plchild,pre)。 while (qltag==0) q＝ qlchild。 if ((s!=NULL)amp。 // 讀入一個(gè)整數(shù) s=(bitree *)malloc(sizeof(bitree))。 else if (plchild==NULL) // 被刪結(jié)點(diǎn)無(wú)左子樹(shù) { if (q==NULL) t=prchild。樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。比等長(zhǎng)編碼的情形要短。 } for (i=1。 p1=j。i=n。 else i=tree[i].rchild。 i=m。 codetype code[n+1]。j=i1。i++) { tree[i].parent=0。 因各字符出現(xiàn)的概率為 { 2/18, 7/18, 4/18, 5/18 }。 else return (SEARCH(brchild))。 p=plchild。 bitree *s。 qrtag＝ prtag。 若 *p 的右子樹(shù)非空，則 *p 的中序后繼必是 其右子樹(shù)中第一個(gè)遍歷到的結(jié)點(diǎn)，也就是從 *p的右孩子開(kāi)始，沿左指針鏈往下查找，直 到找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)為止。 datatype data。 // 左子樹(shù)線索化 // 若當(dāng)前結(jié)點(diǎn)的左子樹(shù)為空，則建立指向其前驅(qū)結(jié)點(diǎn)的前驅(qū)線索 if (plchild = = NULL) { pltag＝ 1。 return(q)。amp。 // 產(chǎn)生一個(gè)樹(shù)結(jié)點(diǎn) sdata=x。 else if (qlchild==p) qlchild=prchild。 2022/8/17 32 帶權(quán)路徑長(zhǎng)度 ( Weighted Path Length, WPL ) 樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)的各葉結(jié)點(diǎn)所帶的權(quán)值 與該結(jié)點(diǎn)到根的路徑長(zhǎng)度的乘積的和。 總編碼長(zhǎng)度正好等于 赫 夫曼樹(shù)的帶權(quán)路徑長(zhǎng) 度 WPL。