数组实现的哈夫曼树创建算法的全代码
时间: 2023-08-06 13:10:09 浏览: 44
这里是使用数组实现的哈夫曼树创建算法的完整代码:
```c++
#include <iostream>
#include <climits>
using namespace std;
// 定义一个节点结构体
struct Node {
int weight; // 权值
int parent; // 父节点
int left; // 左子节点
int right; // 右子节点
};
// 创建哈夫曼树的函数
void createHuffmanTree(Node *tree, int *weights, int n) {
// 初始化森林,每个节点作为一棵只包含自己的树
for (int i = 0; i < n; i++) {
tree[i].weight = weights[i];
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
}
// 合并森林中的树,直到森林中只剩下一棵树
for (int i = 0; i < n - 1; i++) {
int min1 = INT_MAX, min2 = INT_MAX; // 记录森林中权值最小的两棵树
int min1Index = -1, min2Index = -1;
// 在森林中找到权值最小的两棵树
for (int j = 0; j < n + i; j++) {
if (tree[j].parent == -1) { // 只考虑还没有被合并的树
if (tree[j].weight < min1) {
min2 = min1;
min2Index = min1Index;
min1 = tree[j].weight;
min1Index = j;
} else if (tree[j].weight < min2) {
min2 = tree[j].weight;
min2Index = j;
}
}
}
// 合并权值最小的两棵树
tree[min1Index].parent = n + i;
tree[min2Index].parent = n + i;
tree[n + i].weight = tree[min1Index].weight + tree[min2Index].weight;
tree[n + i].left = min1Index;
tree[n + i].right = min2Index;
}
}
int main() {
int weights[] = { 5, 2, 4, 7, 1, 3, 6 };
int n = sizeof(weights) / sizeof(weights[0]);
Node *tree = new Node[2 * n - 1];
// 创建哈夫曼树
createHuffmanTree(tree, weights, n);
// 输出哈夫曼树中每个节点的信息
for (int i = 0; i < 2 * n - 1; i++) {
cout << "Node " << i << ": weight=" << tree[i].weight << ", parent=" << tree[i].parent
<< ", left=" << tree[i].left << ", right=" << tree[i].right << endl;
}
delete [] tree;
return 0;
}
```
在这个例子中,我们使用一个整型数组来表示待编码字符串中每个字符的出现频率。我们首先创建一个大小为2*n-1的节点数组,其中n是字符的个数。然后调用createHuffmanTree函数来创建哈夫曼树。最后,我们输出哈夫曼树中每个节点的信息。