如何生成這個霍夫曼樹（類似於二叉樹）

Question

我瞭解如何創建哈夫曼樹，當頻率彼此不同時，但如果少數頻率相同，我將如何繪製該哈夫曼樹：

的哈夫曼樹的簡單解釋是發現here

的哈夫曼樹的數據，我想創建：

Letter Frequency 
A  15% 
B  15% 
C  10% 
D  10% 
E  30% 
F  20% 

現在，我開始與這對信兩個最低頻率和D

. 
/\ 
C D 

但是下一步會是什麼？因爲我們有A和B具有相同的頻率，所以我們選擇哪一個？如果我們選擇其中之一，那麼當選擇第二個時，結構將如何顯示？

如果讓我選擇B那麼它會是這樣的（除非我是錯的）

 . 
    /\ 
    B . 
    /\ 
    C D 

那這一步之後???

這些可以使用Java和C進行編碼，我試圖在實現它們之前先弄清楚它們是如何工作的。

編輯

我的樹是這個樣子：

  ___________|_________________ 
     /\       | 
    /\       | 
     F E       | 
    /\        | 
    / \        | 
    B  A       /\ 
            /\ 
            C D 

也得到了從網上

Answer 1

步驟一步回答你的問題。

所以，你開始

A = 15% 
B = 15% 
C = 10% * 
D = 10% * 
E = 30% 
F = 20% 

你挑兩個最低（C + d），並加入他們（它們的總和爲20

20 
/\ 
C D 

你現在有

A = 15% * 
B = 15% * 
C+D = 20% 
E = 30% 
F = 20% 

現在你加入另外兩個最低（A，B），其總和爲30.

 20  30 
    /\ /\ 
    C D A B 

你現在有

A+B = 30% 
C+D = 20% * 
E = 30% 
F = 20% * 

最低的是（C + d，F），讓你加入他們的行列

40 
/\  
    F 20  30 
    /\ /\ 
    C D A B 


A+B = 30% * 
C+D+F = 40% 
E = 30% * 

下一步，和以前一樣：

A+B+E = 60% * 
C+D+F = 40% * 


     100 
    / \ 
    40  60 
/\ /\ 
    F 20 E 30 
    /\  /\ 
    C D  A B 

Answer 2

它並不真正無論您選擇爲例，你會得到一些不同的編碼，但是具有相同的概率。在某些情況下，有更多可能的方式來構建樹，但這並不重要。

我已經編輯了圖像，因爲我犯了一個錯誤，但請檢查我的第二個答案是否正確。

Answer 3

你將會得到一些代碼來處理任何平等的分歧。

|  letter  | A | B | C | D | E | F | 
|-----------------|-----|-----|-----|-----|-----|-----| 
|  freq  | 10 | 20 | 30 | 5 | 25 | 10 | 
|-----------------|-----|-----|-----|-----|-----|-----| 

按最大

|-----------------|-----|-----|-----|-----|-----|-----| 
|  letter  | C | E | B | F | A | D | 
|-----------------|-----|-----|-----|-----|-----|-----| 
|  freq  | 30 | 25 | 20 | 10 | 10 | 5 | 
|-----------------|-----|-----|-----|-----|-----|-----| 

tree creating

freq   30 10  5  10  20  25 
symbol   C  A  D  F  B  E 
         |  | 
         |--|--| 
         ||-| 
         |15| = 5 + 10 

2 step

freq   30 10  5  10  20  25 
symbol   C  A  D  F  B  E 
        |  |  | 
        |  |  | 
        | |--||  | 
        |-|15||  | 
         ||-|  | 
         |   | 
         | |--| | 
         |----|25|-| = 10 + 15 
          |--| 

3 step

freq   30 10  5  10  20  25 
sym   C  A  D  F  B  E 
      |  |  |  |  |  | 
      |  |  |  |  |  | 
      |  | |--||  |  |  | 
      |  |-|15||  |  |  | 
      |  ||-|  |  |  | 
      |  |   |  |  | 
      |  | |--| |  | |--| | 
      |  |----|25|-|  |-|45|-| 
      |    ||-|   ||-| 
      | |--|  |    | 
      |----|55|------|    | 
        |-||     | 
        | |------------| | 
        |---| Root (100) |----| 
         |------------| 

編碼：

C = 00 
    A = 0100 
    D = 0101 
    F = 011 
    B = 10 
    E = 11