8609 哈夫曼树

### 思路
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. **生成哈夫曼编码**：从叶子节点到根节点逆向生成编码，存储在编码数组中。