用C语言打码构造一棵哈夫曼树,求其权路径长度值,已知权值为2,3,4,11
时间: 2024-09-26 16:03:13 浏览: 11
在C语言中,构建哈夫曼树并计算权路径长度(也称为赫夫曼编码或前缀编码)通常涉及到两个步骤:创建哈夫曼树并通过它生成编码。给定一组权值,我们首先需要对这些权值进行排序,然后应用赫夫曼编码算法。
以下是一个简化版的哈夫曼树构建过程,这里只适用于四个权值(2, 3, 4, 11)。实际操作中,我们会使用优先队列(如二叉堆)来高效地进行合并操作:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int weight;
struct Node *left;
struct Node *right;
} Node;
Node* newNode(int weight) {
Node *node = (Node*)malloc(sizeof(Node));
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
void mergeTrees(Node** root1, Node** root2) {
if(*root1 == NULL) {
*root1 = *root2;
} else if(*root2 == NULL) {
return;
} else if(*root1->weight > *root2->weight) {
(*root1)->right = mergeTrees(&(*root1)->right, root2);
} else {
(*root1)->left = mergeTrees(root1, &(*root2)->left);
}
return *root1;
}
Node* buildHuffmanTree(int weights[], int n) {
Node **heap = (Node**)malloc(sizeof(Node*) * n);
for(int i=0; i<n; i++) {
heap[i] = newNode(weights[i]);
}
while(n > 1) {
n--;
Node* leftRoot = heap[0];
heap[0] = heap[n];
heap[n] = mergeTrees(heap, heap + n);
// 更新堆
for(int i=n/2; i>=0; i--) {
heapify(heap + i);
}
}
return heap[0];
}
// 赫夫曼编码辅助函数
int getCodeLength(Node* node, int codeLen) {
if(node->left == NULL && node->right == NULL)
return codeLen;
else if(node->left == NULL)
return getCodeLength(node->right, codeLen + 1);
else if(node->right == NULL)
return getCodeLength(node->left, codeLen + 1);
else
return min(getCodeLength(node->left, codeLen + 1), getCodeLength(node->right, codeLen + 1)) + 1;
}
int getHuffmanCode(Node* root, int code[]) {
if(root->left == NULL && root->right == NULL)
return code[root->weight];
if(root->left == NULL) {
code[root->weight] = getCode(root->right, code + 1);
} else if(root->right == NULL) {
code[root->weight] = getCode(root->left, code + 1);
} else {
code[root->weight] = getCode(root->left, code) ^ getCode(root->right, code);
getHuffmanCode(root->right, code);
getHuffmanCode(root->left, code);
}
return code[root->weight];
}
int main() {
int weights[] = {2, 3, 4, 11};
int n = sizeof(weights) / sizeof(weights[0]);
Node* root = buildHuffmanTree(weights, n);
int code[50] = {0}; // 初始化足够大的数组存储编码
int codeLength = getCodeLength(root, 0);
printf("Huffman Code: ");
getHuffmanCode(root, code);
for(int i=0; i<codeLength; i++) {
printf("%d ", code[i]); // 输出编码
}
return 0;
}
```
这个程序首先构建哈夫曼树,然后通过递归获取每个节点的最小路径长度(即赫夫曼编码)。请注意,这里的`weights[]`数组包含了所有的权值,包括11。