戀戀星情

 作者  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