数据结构实验哈夫曼树

### 数据结构实验：哈夫曼树

#### 构造哈夫曼树的方法
为了构建哈夫曼树，首先需要理解其基本原理。给定一组节点及其权重，通过不断选取两个具有最小权重的节点并创建一个新的内部节点作为它们的父亲节点来逐步建立这棵树。新父节点的权重等于这两个子节点权重之和。重复此操作直到只剩下一个根节点为止。

对于具体实现，在编程环境中可以定义一个类`Node`表示树中的每一个结点，并设置属性用于存储字符、频率以及指向左孩子和右孩子的指针[^1]。

class Node {
    char data;
    int freq;
    Node left, right;

    public Node(char data, int freq) {
        this.data = data;
        this.freq = freq;
        left = null;
        right = null;
    }
}

#### 计算带权路径长度 (WPL)

在构造完成后，可以通过遍历整棵哈夫曼树来计算加权外部路径长度(WPL)，即所有叶子节点到根的距离乘以其相应概率(或频次)后的总和。通常来说，最优前缀码对应于使WPL达到最小值的那种二叉树形态[^2]。

#### 生成哈夫曼编码

一旦建立了哈夫曼树，则可以从上至下沿着每条分支分配'0'或'1'(取决于约定的方向),从而得到各个符号对应的唯一编码串。这里提供了一个简单的递归函数用来打印出各字符与其相应的哈夫曼编码：

public void printHfmCode(Node node, String code){
    if(node.left != null)
        printHfmCode(node.left,code + "0");
    if(node.right != null)
        printHfmCode(node.right,code + "1");
    if(node.left == null && node.right == null)
        System.out.println(node.data + " 的哈夫曼编码为：" + code);
}

上述代码片段展示了如何基于已建好的哈夫曼树输出每个字母所关联的最佳压缩形式[^3]。

#### 完整流程实例化说明

假设现在有一组字符{'A', 'B', 'C', 'D'} 和 对应出现次数 {7, 5, 2, 4}, 那么按照前述步骤就可以一步步建立起属于这些数据集特性的哈夫曼树，并最终获得如下所示的结果:

| 字符 | 出现次数 | 编码 |
| --- | ------ | ---- |
| A | 7 | 0 |
| B | 5 | 10 |
| C | 2 | 110 |
| D | 4 | 111 |

以上表格仅作为一个简化版的例子展示整个过程可能产生的输出之一[^4]。