给定权值为[1,2,3,4,5,6,7,8,9],构建一颗哈夫曼树,并且利用先序遍历打印。
时间: 2024-06-18 16:06:10 浏览: 19
哈夫曼树是一种特殊的二叉树,它的每个叶子节点都对应一个权值,同时满足:权值较大的节点离根较近,权值较小的节点离根较远。构建哈夫曼树的过程可以使用贪心算法。
对于给定的权值,构建哈夫曼树的过程如下:
1. 将权值按照从小到大的顺序排序,得到序列[1,2,3,4,5,6,7,8,9]。
2. 取出两个权值最小的节点,将它们作为左右子节点构建一棵新的二叉树,根节点的权值为左右子节点权值之和。
3. 将这棵新的二叉树插入到序列中,保持序列的有序性。
4. 重复步骤2和步骤3,直到序列中只剩下一个节点为止,这个节点就是哈夫曼树的根节点。
构建好哈夫曼树之后,可以使用先序遍历的方式打印出所有节点的权值。先序遍历的顺序是:先遍历根节点,然后遍历左子树,最后遍历右子树。
以下是C语言代码实现以上算法:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int weight;
struct Node *left;
struct Node *right;
} Node;
Node* create_node(int weight) {
Node *node = (Node*)malloc(sizeof(Node));
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
Node* create_huffman_tree(int weights[], int n) {
Node **nodes = (Node**)malloc(sizeof(Node*) * n);
for (int i = 0; i < n; i++) {
nodes[i] = create_node(weights[i]);
}
while (n > 1) {
Node *left = nodes;
Node *right = nodes;
Node *parent = create_node(left->weight + right->weight);
parent->left = left;
parent->right = right;
int i, j;
for (i = 2, j = 1; i < n; i++, j++) {
if (nodes[i]->weight < parent->weight) {
nodes[j] = nodes[i];
} else {
break;
}
}
nodes[j-1] = parent;
for (; i < n; i++, j++) {
nodes[j] = nodes[i];
}
n--;
}
Node *root = nodes;
free(nodes);
return root;
}
void print_preorder(Node *node) {
if (node == NULL) {
return;
}
printf("%d ", node->weight);
print_preorder(node->left);
print_preorder(node->right);
}
int main() {
int weights[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(weights) / sizeof(weights);
Node *root = create_huffman_tree(weights, n);
print_preorder(root);
return 0;
}
```