3

周波数が互いに異なる場合にハフマン木を作成する方法は理解していますが、同じ周波数がほとんどない場合、このハフマン木をどのように描画すればよいでしょうか。

ハフマン木の簡単な説明はここにあります

私が作成しようとしているハフマン木のデータ:

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

Cここで、レターとレター用の 2 つの最低周波数から始めます。D

   .
  / \
 C   D

しかし、次のステップは何でしょうか？A同じ周波数を持っているBので、どちらを選択しますか? そのうちの 1 つを選択すると、2 つ目を選択したときに構造はどのように見えるでしょうか?

選択するBと、次のようになります（間違っていない限り）

     .
    / \
   B   .
      / \
     C   D

このステップの後はどうですか？

これらはJavaとCでもコーディングできます。実装する前に、これらがどのように機能するかを理解しようとしています。

編集

私のツリーは次のようになります。

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

また、オンラインから例を取得しました

ここに画像の説明を入力

4

3 に答える 3

3

あなたの問題に対する段階的な答え。

だからあなたはから始めます

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

最も低いもの (C+D) を 2 つ選び、それらを結合します (それらの合計は 20 です。

  20
 / \
C   D

あなたは今持っています

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

これで、別の最低 2 つの (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
于 2012-08-14T11:29:40.033 に答える
2

等しい周波数のコードがいくつかあります。

|     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
于 2012-08-14T11:03:37.667 に答える
1

どちらを選択しても問題ありません。少し異なるエンコーディングが得られますが、確率は同じです。場合によっては、ツリーを構築する方法が他にもありますが、それは問題ではありません。

間違えたので画像を編集しましたが、2番目の回答で正しい回答を確認してください。

于 2012-08-14T10:45:22.677 に答える