java - 如何生成哈夫曼树(类似于二叉树)

Question

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

找到了霍夫曼树的简单解释 here

我要创建的哈夫曼树的数据:

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

现在我从字母 C 和 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