3

我了解当频率彼此不同时如何创建霍夫曼树，但是如果频率很少相同，我将如何绘制这个霍夫曼树：

在这里可以找到 Huffmann 树的简单解释

我正在尝试创建的霍夫曼树的数据：

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

现在我从两个最低频率开始，分别是 LetterC和D

   .
  / \
 C   D

但是下一步会是什么？因为我们有A相同B的频率，所以我们选择哪一个？如果我们选择其中一个，那么在选择第二个时，结构将如何看起来？

如果我选择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) 并加入他们（他们的总和是 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
于 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

您选择哪种并不重要，您会得到一些不同的编码，但概率相同。在某些情况下有更多可能的方式来构建树，但这并不重要。

我编辑了图像，因为我犯了一个错误，但请查看我的第二个答案以获得正确的答案。

于 2012-08-14T10:45:22.677 回答