C#实现哈夫曼树构建详解：原理与核心代码

结果或目标

我们的目标是输入一组节点的权值列表（例如 List<int>），输出一个完整的哈夫曼树结构。该结构需满足以下特征：
1. 所有叶子节点对应输入的初始权值。
2. 非叶子节点是左右子节点权值之和。
3. 任何节点都指向其左孩子、右孩子和父节点的位置索引，且无环。

准备条件

要实现这一目标，首先需要定义基本的数据结构。哈夫曼树通常不使用指针链接，而是使用一个大的数组来顺序存储所有节点。因为对于包含 n 个叶子节点的哈夫曼树，总共会有 2n-1 个节点（包括内部的合成节点）。

第1步：定义节点结构 Node

为了便于管理和序列化，我们定义一个 Node 类。它需要记录当前节点的权重，以及其在数组中的索引位置，分别用于左孩子、右孩子和父节点。如果某个方向不存在节点，则索引设为 -1。

public class Node
{
    public int Weight { get; set; }   // 节点权值
    public int LChild { get; set; }   // 左孩子在数组中的索引
    public int RChild { get; set; }   // 右孩子在数组中的索引
    public int Parent { get; set; }   // 父节点在数组中的索引

    // 默认构造函数，初始化状态为独立节点
    public Node()
    {
        Weight = 0;
        LChild = -1;
        RChild = -1;
        Parent = -1;
    }

    // 全参构造函数，适用于已知属性的场景
    public Node(int weight, int lChild, int rChild, int parent)
    {
        this.Weight = weight;
        this.LChild = lChild;
        this.RChild = rChild;
        this.Parent = parent;
    }
}

真实操作顺序：构建哈夫曼树

第2步：初始化存储空间

创建一个名为 HuffmanTree 的类，内部维护一个 Node 类型的数组 data。数组长度固定为 2 * n - 1，其中前 n 个位置用于存放原始叶子节点，后 n-1 个位置将用于存放构建过程中产生的新节点。

class HuffmanTree
{
    private Node[] data;
    public int LeafNum { get; set; }

    // 索引器，方便访问具体节点
    public Node this[int index] 
    {
        get { return data[index]; }
        set { data[index] = value; }
    }

    public HuffmanTree(int n)
    {
        data = new Node[2 * n - 1];
        for (int i = 0; i < 2 * n - 1; i++)
        {
            data[i] = new Node();
        }
        LeafNum = n;
    }
}

第3步：加载叶子节点权值

接收一个整数列表作为输入，将其依次赋值给数组的前 n 个节点的 Weight 属性。此时，这些节点的 Parent 默认为 -1，表示它们尚未被挂载到任何父节点下，这正是后续算法筛选的关键条件。

第4步：循环合并非叶子节点

这是核心逻辑。我们需要执行 n-1 次合并操作，每次操作生成一个新的内部节点。
1. **查找最小值**：在未挂载（Parent == -1）的节点中，找出权值最小的两个节点。可以通过遍历数组前半部分加上已生成的新节点部分来实现。
2. **更新索引**：找到最小（min1）和第二小（min2）的节点索引（tmp1, tmp2）。
3. **建立父子关系**：

• 将这两个节点的 Parent 指向下一个可用空间索引（即 LeafNum + i）。
• 将新节点（位于 LeafNum + i）的 LChild 设为 tmp1，RChild 设为 tmp2。
• 计算新节点的 Weight 为两个子节点权值之和。

    public void Create(List<int> list)
    {
        // 1. 填充叶子节点
        for (int i = 0; i < list.Count; i++)
        {
            data[i].Weight = list[i];
        }

        // 2. 进行 n-1 次合并
        for (int i = 0; i < LeafNum - 1; i++)
        {
            int min1 = int.MaxValue;
            int min2 = int.MaxValue;
            int tmp1 = 0, tmp2 = 0;

            // 在当前所有未挂接的节点中找权值最小的两个
            // 范围：从索引 0 到 (LeafNum + i - 1)
            for (int j = 0; j < LeafNum + i; j++)
            {
                if (data[j].Parent == -1)
                {
                    if (data[j].Weight < min1)
                    {
                        min2 = min1;
                        tmp2 = tmp1;
                        min1 = data[j].Weight;
                        tmp1 = j;
                    }
                    else if (data[j].Weight < min2)
                    {
                        min2 = data[j].Weight;
                        tmp2 = j;
                    }
                }
            }

            // 3. 创建新节点并建立连接
            int newNodeIndex = LeafNum + i;
            data[tmp1].Parent = newNodeIndex;
            data[tmp2].Parent = newNodeIndex;
            
            data[newNodeIndex].Weight = data[tmp1].Weight + data[tmp2].Weight;
            data[newNodeIndex].LChild = tmp1;
            data[newNodeIndex].RChild = tmp2;
        }
    }
}

完成判断与验证

当循环结束，数组最后一个元素（索引 2n-2）即为根节点。我们可以通过检查根节点的 Parent 是否为 -1 来初步判断构建是否成功。此外，任意非根节点的 Parent 都应指向更高的层级索引，形成倒置的树状拓扑。

简要总结

C#构建哈夫曼树的核心在于利用数组模拟指针逻辑。通过不断查找权值最小的两个无父节点并进行合并，最终形成一棵带权路径长度最短的二叉树。上述代码提供了一个标准的面向对象的实现框架，可直接集成到排序、压缩等应用场景中。以上就是C#求解哈夫曼树原理与实例代码的详细内容，更多关于C#数据结构算法的资料请关注本站其它相关文章！