### 思路
1. **选择最小权值节点**:在哈夫曼树构建过程中,选择两个权值最小且父节点为0的节点。
2. **构建哈夫曼树**:根据权值构建哈夫曼树,确保左子树权值小于右子树权值。
3. **生成哈夫曼编码**:从叶子节点到根节点逆向生成每个字符的哈夫曼编码。
### 伪代码
1. **选择最小权值节点**:
- 遍历节点,找到两个权值最小且父节点为0的节点。
2. **构建哈夫曼树**:
- 初始化哈夫曼树节点。
- 输入��值。
- 迭代构建哈夫曼树,选择两个最小权值节点,更新父节点和子节点信息。
3. **生成哈夫曼编码**:
- 从叶子节点到根节点逆向生成编码,存储在编码数组中。
### C++代码
#include "stdio.h"
#include "string.h"
#include <iostream>
using namespace std;typedef struct {unsigned int weight;unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;typedef char **HuffmanCode;void select(HuffmanTree &HT, int n, int &s1, int &s2) {int min1 = 0xFFFFFFFF, min2 = 0xFFFFFFFF; // Use large initial valuess1 = s2 = 0;for (int i = 1; i <= n; ++i) {if (HT[i].parent == 0) {if (HT[i].weight < min1) {min2 = min1;s2 = s1;min1 = HT[i].weight;s1 = i;} else if (HT[i].weight < min2) {min2 = HT[i].weight;s2 = i;}}}
}void createHuffmanTree(HuffmanTree &HT, int n) {int i, m, s1, s2;if (n <= 1) return;m = 2 * n - 1;HT = new HTNode[m + 1]; // 0号单元未用for (i = 1; i <= m; i++) { // 初始化HT数组HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (i = 1; i <= n; i++)cin >> HT[i].weight;for (i = n + 1; i <= m; i++) { // 建哈夫曼树select(HT, i - 1, s1, s2);HT[s1].parent = i;HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}
}void createHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {char *cd = new char[n]; // 分配求编码的工作空间cd[n - 1] = '\0'; // 编码结束符。int i, c, f, start;for (i = 1; i <= n; ++i) {start = n - 1;c = i, f = HT[i].parent;while (f) { // 从叶子到根逆向求编码--start;if (HT[f].lchild == c) cd[start] = '0';else cd[start] = '1';c = f, f = HT[f].parent;}HC[i] = new char[n - start]; // 为第i个字符编码分配空间strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC}delete[] cd;
}int main() {int i, n;HuffmanTree HT;HuffmanCode HC;scanf("%d", &n); // 权值个数HC = new char*[n + 1]; // 0空间未用createHuffmanTree(HT, n);createHuffmanCode(HT, HC, n);for (i = 1; i <= n; i++)printf("%s\n", HC[i]); // 输出哈夫曼编码for (i = 1; i <= n; i++)delete[] HC[i];delete[] HC;delete[] HT;return 0;
}
### 总结
1. **选择最小权值节点**:通过遍历找到两个��值最小且父节点为0的节点。
2. **构建哈夫曼树**:��始化节点,输入权值,迭代构建哈夫曼树。
3. **生成哈夫曼编码**:从叶子节点到根节点逆向生成编码,存储在编码数组中。