第五章樹和二叉樹-文庫(kù)吧在線文庫(kù)
【正文】 c 010 01 110 d 011 001 1110 e 100 10 10 2022/8/17 35 a d c e b 2022/8/17 36 赫夫曼算法 (1) 由給定的 n個(gè)權(quán)值 {w1, w2, …, wn}，構(gòu)造具有 n棵二叉樹的森林 F = {T1, T2, …, Tn}，其中每一棵二叉樹 Ti只有一個(gè)帶有權(quán)值 wi的根結(jié)點(diǎn)，其左、右子樹均為空。 因各字符出現(xiàn)的概率為 { 2/18, 7/18, 4/18, 5/18 }。 赫夫曼編碼樹 2022/8/17 40 赫夫曼樹的存儲(chǔ)結(jié)構(gòu) define n 7 define m 2*n1 typedef struct { int weight。i++) { tree[i].parent=0。 tree[i].weight=f。j=i1。 tree[p2].parent=i。 codetype code[n+1]。 while (p!=0) { 。 i=m。b)。 else i=tree[i].rchild。 p=tree[p].parent。i=n。 } } 2022/8/17 42 赫夫曼編碼的存儲(chǔ)結(jié)構(gòu) typedef struct { char bits[n+1]。 p1=j。 p2=0。 } for (i=1。 2022/8/17 41 赫夫曼樹的構(gòu)造算法 HUFFMAN(hufmtree tree[]) { int i,j,p1,p2。比等長(zhǎng)編碼的情形要短。 ③ 把新的二叉樹加入 F。樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。 else qrchild=plchild。 else if (plchild==NULL) // 被刪結(jié)點(diǎn)無(wú)左子樹 { if (q==NULL) t=prchild。 // p指向待比較的結(jié)點(diǎn) q=NULL。 // 讀入一個(gè)整數(shù) s=(bitree *)malloc(sizeof(bitree))。 else if ( sdata == bdata ) return。 if ((s!=NULL)amp。 } } 2022/8/17 12 線索二叉樹的結(jié)點(diǎn)插入算法 INSERTRIGHT(bithptr *p,bithptr *q) { bithptr *s。 while (qltag==0) q＝ qlchild。 } else prtag＝ 0。 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)，開始調(diào)用時(shí) p為根結(jié)點(diǎn)指針， pre為 NULL { if (p!=NULL) { INTHREAD(plchild,pre)。若增加指針 域來(lái)存放前驅(qū)和后繼結(jié)點(diǎn)信息，將大大降低存儲(chǔ) 空間的利用率（密度）。 struct node *lchild,*rchild。amp。 中序線索二叉樹中，查找指定結(jié)點(diǎn) *p的中序后繼結(jié)點(diǎn) 2022/8/17 7 p R1 R2 Rk 最左下結(jié)點(diǎn) 2022/8/17 8 中序線索二叉樹中求中序后繼結(jié)點(diǎn)的算法 bithptr *INORDERNEXT(bithptr *p) { bithptr *q。 do { printf(“\t%d
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1