C#求解哈夫曼树，实例代码

什么是哈夫曼树？

哈夫曼树是一种二叉树，它的权值在叶子节点处，而非根节点处。它是一种带权路径长度最短的树，被广泛应用在文件压缩和编码中。

求解哈夫曼树的过程

求解哈夫曼树的过程分为三步：

1. 构建森林：将每一个权值看做一个点，将所有点作为森林的初始状态。

2. 构建哈夫曼树：对于森林中的每一对最小权值节点，合并它们并将合并后的点重新放回森林。

3. 重复步骤2，直到森林中只剩下一颗哈夫曼树为止。

实现代码

下面给出用C#实现求解哈夫曼树的代码示例：

public class Node
{
    public int Value { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

public static Node Huffman(int[] weight)
{
    var nodes = new List<Node>();
    foreach (var w in weight)
    {
        nodes.Add(new Node { Value = w });
    }

    while (nodes.Count > 1)
    {
        var orderedNodes = nodes.OrderBy(n => n.Value).ToList();

        if (orderedNodes.Count >= 2)
        {
            var taken = orderedNodes.Take(2).ToList();
            var first = taken[0];
            var second = taken[1];

            var sum = new Node { Value = first.Value + second.Value, Left = first, Right = second };
            nodes.Remove(first);
            nodes.Remove(second);
            nodes.Add(sum);
        }
    }

    return nodes.FirstOrDefault();
}

示例说明

示例1

假设有如下权值数组：

var weight = new[] { 2, 3, 4, 6, 8, 10 };

经过上述求解哈夫曼树的代码计算，得到的哈夫曼树如下：

        33
       /  \
     14    19
    / \    / \
   6   8  10  9

示例2

假设有如下权值数组：

var weight = new[] { 9, 12, 6, 3, 5, 15 };

经过上述求解哈夫曼树的代码计算，得到的哈夫曼树如下：

         50
       /    \
     21      29
    /  \    /  \
   9   12  6    23
         / \   / \
        3   5 15  8