构造哈夫曼树

### 哈夫曼树的构造方法 哈夫曼树是一种最优二叉树，在数据压缩领域有广泛应用。其核心思想是通过不断合并权值最小的两个节点，最终形成一棵具有最小带权路径长度的树。 #### 构造过程描述 1. 初始状态由 $ n $ 个独立的节点组成，每个节点的权值分别为给定的一组数值[^1]。 2. 找到当前集合中权值最小的两个节点，并将其合并成一个新的节点，新节点的权值等于这两个节点权值之和。 3. 将新的节点加入集合，移除原来的两个节点，使得集合中的节点总数减一[^1]。 4. 重复第 2 和第 3 步骤，直至集合中仅剩下一个节点，此时该节点即为哈夫曼树的根节点[^1]。 以下是基于 C 语言实现的一个简单版本： ```c #include <stdio.h> #define MAX_TREE_SIZE 100 #define inf 99999 typedef struct { int weight; int parent, lchild, rchild; } HTNode; void Select(HTNode *HT, int x, int &s1, int &s2) { int i, min1 = inf, min2 = inf; s1 = s2 = 0; for (i = 1; i <= x; ++i) { // 寻找第一个最小值 if (HT[i].weight < min1 && HT[i].parent == 0) { min1 = HT[i].weight; s1 = i; } } for (i = 1; i <= x; ++i) { // 寻找第二个最小值 if (HT[i].weight < min2 && HT[i].parent == 0 && i != s1) { min2 = HT[i].weight; s2 = i; } } } void CreateHuffmanTree(HTNode *HT, int n) { int m = 2 * n - 1; int s1, s2; for (int i = 1; i <= m; ++i) { HT[i].parent = HT[i].lchild = HT[i].rchild = 0; if (i <= n) scanf("%d", &(HT[i].weight)); // 输入叶子节点权重 else HT[i].weight = 0; } for (int i = n + 1; i <= m; ++i) { Select(HT, i - 1, s1, s2); HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } } ``` 此代码实现了哈夫曼树的构建逻辑，其中 `Select` 函数用于找到当前未被使用的两个最小权值节点[^2]，而 `CreateHuffmanTree` 是整个构建的核心函数。 ### 注意事项 - 在实际应用中，可能需要根据具体需求调整输入方式以及存储结构。 - 上述代码假设所有节点的初始权值已知并按顺序排列好。