哈夫曼树的构造及代码注释

哈夫曼树的构造是一种用于数据压缩的算法。其基本思想是将出现频率较高的字符进行编码，使得编码后的数据长度更短，从而实现数据压缩的目的。

以下是哈夫曼树的构造代码注释：

// 定义哈夫曼树结点
struct HuffmanNode {
int weight; // 结点权重
int parent; // 父结点在数组中的下标
int leftChild, rightChild; // 左右孩子在数组中的下标
};

// 定义比较哈夫曼树结点权重的函数
bool cmp(HuffmanNode a, HuffmanNode b) {
return a.weight > b.weight;
}

// 构造哈夫曼树
void buildHuffmanTree(HuffmanNode huffmanTree[], int n) {
int i, j;
// 初始化哈夫曼树结点
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].parent = -1;
huffmanTree[i].leftChild = -1;
huffmanTree[i].rightChild = -1;
}
// 输入每个结点的权重
for (i = 0; i < n; i++) {
cin >> huffmanTree[i].weight;
}
// 构造哈夫曼树
for (i = n; i < 2 * n - 1; i++) {
// 在剩余结点中找到权重最小的两个结点
int min1, min2;
min1 = min2 = INT_MAX;
for (j = 0; j < i; j++) {
if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
min2 = min1;
min1 = huffmanTree[j].weight;
} else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
}
}
// 将这两个结点合并为一个新结点，并添加到哈夫曼树中
huffmanTree[i].weight = min1 + min2;
for (j = 0; j < i; j++) {
if (huffmanTree[j].weight == min1 && huffmanTree[j].parent == -1) {
huffmanTree[j].parent = i;
huffmanTree[i].leftChild = j;
} else if (huffmanTree[j].weight == min2 && huffmanTree[j].parent == -1) {
huffmanTree[j].parent = i;
huffmanTree[i].rightChild = j;
}
}
}
}

笑话：为什么大象会跑得很快？因为小老鼠追得紧啊！