建立适当的树

Question

所以，我有那个用于编码字符串的霍夫曼树。我已经定义了函数 plant，但我不确定我的树是否只向一侧倾斜太多。这是我的代码：

data HuffTree
    = Leaf Char
    | HuffTree |*| HuffTree     
    deriving (Eq, Show)

|*| 是一个中缀构造函数。

plant :: [(Char,Int)] -> HuffTree
plant [(x,y)] = (Leaf x)
plant ((x,y):xs) = plant xs |*| (Leaf x)

对我来说，它看起来是片面的，因此它实际上并不意味着编码思想，因为它不是真正的二叉树。我怎样才能把它变成一个普通的二叉树呢？

Answer 1

您没有正确构建霍夫曼树。这个过程应该是这样的：

将所有源码元转为单元素霍夫曼树
将每个源符号与其频率配对成一个 tree/frequency 对的大列表。
如果只剩下一对 tree/frequency 对，那棵树就是你的霍夫曼树。
否则删除频率最低的两个 trees/frequency 对，组合树并添加频率以形成新的 tree/frequency 对，并将其添加回列表。
转到 3.

所以我将其更改为 plant :: [(HuffTree,Int)] -> HuffTree。在第二种情况下，我会对元素进行排序，去掉前两个元素，将它们组合起来，然后递归调用 plant 。您可能还想切换到 (Int,HuffTree) 对，以便可以使用默认的排序实现。您还需要将 Ord 添加到 HuffTree 派生子句中。

建立适当的树

Building proper tree

tree

binary-tree

haskell

huffman-code

algebraic-data-types