作者 SONGya168 (一路發 圍巾) 看板 Grad-ProbAsk
標題 Re: [問題]huffmam...
時間 Wed Feb 4 18:34:30 2009
───────────────────────────────────────
※ 引述《bernachom (Terry)》之銘言：
: 有一個目題我一直覺得怪怪...
: Given a set of messages and their weights in the following,construct the
: huffman decoding tree that yields the minimum weight.
: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10
: 4 18 11 48 22 32 69 7 2 30
: 這是我畫錯的圖...而且還沒有掛完...
: 94
: / \
: 42 52
: / \ / \
: 18 24 22 30
: / \
: 11 13
: / \
: 6 7
: / \
: 2 4
: 請教一下，是我哪裡畫出問題了呢?
: 謝謝
M1 4 #
M2 18 M2 18
M3 11 M3 11 13
M4 48 M4 48 / \
M5 22 6 M5 22 6 7
M6 32 / \ M6 32 / \
M7 69 2 4 M7 69 2 4
M8 7 M8 7 #
M9 2 # M10 30
M10 30 6 #
(3) (4) 40
24 / \
M2 18 / \ M2 18 # 18 22 24
M3 11 # 11 13 M4 48 / \
M4 48 / \ M5 22 # 11 13
M5 22 6 7 M6 32 / \
M6 32 / \ M7 69 6 7
M7 69 2 4 M10 30 / \
M10 30 24 2 4
13 #
72
/ \
40 54 32 40 54
(5) / \ / \ (6) / \ / \
18 22 24 30 18 22 24 30
M4 48 / \ M4 48 / \
M6 32 11 13 M6 32 # 11 13
M7 69 / \ M7 69 / \
M10 30 # 6 7 40 # 6 7
24 # / \ 54 / \
40 2 4 2 4
(7) 72 102
/ \ / \
32 40 48 54
/ \ / \
M4 48 # 18 22 24 30
M7 69 / \
54 # 11 13
72 / \
6 7
/ \
2 4
(8) 243
/ \
141 \
/ \ \
69 72 102
/ \ / \
32 40 48 54
M7 69 # / \ / \
72 # 18 22 24 30
102 / \
11 13
/ \
6 7
/ \
2 4
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.10.184
※ 編輯: SONGya168 來自: 61.216.10.184 (02/04 18:35)
推 bernachom:好精彩...我來看看... 02/04 18:38
推 bernachom:請教一下，如果小的值在左邊，大的值在右邊 02/04 18:42
→ bernachom:照這種順序掛下來，樹會唯一嗎??謝謝您 02/04 18:42
推 soarclovia:huffman tree好像是唯一的 可是我常常都掛出不唯一..>< 02/04 18:59
→ SONGya168:恩 是唯一的 畢竟是最小加權(左邊鍵值一定小於右邊鍵值 02/04 19:15
留言列表
