【PTA数据结构 | C语言版】创建哈夫曼树

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，根据给定的权重值序列，构建哈夫曼树，并计算带权路径长度。

输入格式：
输入首先给出一个不超 20 的正整数 n，随后一行给出 n 个权重值。其中权重值都是不超过 100 的正整数。

输出格式：
在一行中输出哈夫曼树的带权路径长度。

输入样例：
5
1 2 3 4 5

输出样例：
33

代码

#include <stdio.h>
#include <stdlib.h>typedef struct HuffmanNode {int weight;struct HuffmanNode *left, *right;
} HuffmanNode;typedef struct {HuffmanNode **array;int size;int capacity;
} MinHeap;// 创建新节点
HuffmanNode* newNode(int weight) {HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));node->weight = weight;node->left = node->right = NULL;return node;
}// 创建最小堆
MinHeap* createMinHeap(int capacity) {MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));return minHeap;
}// 交换两个节点
void swapHuffmanNode(HuffmanNode** a, HuffmanNode** b) {HuffmanNode* t = *a;*a = *b;*b = t;
}// 最小堆化
void minHeapify(MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->weight < minHeap->array[smallest]->weight)smallest = left;if (right < minHeap->size && minHeap->array[right]->weight < minHeap->array[smallest]->weight)smallest = right;if (smallest != idx) {swapHuffmanNode(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 判断堆的大小是否为1
int isSizeOne(MinHeap* minHeap) {return minHeap->size == 1;
}// 提取最小值
HuffmanNode* extractMin(MinHeap* minHeap) {HuffmanNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入新节点
void insertMinHeap(MinHeap* minHeap, HuffmanNode* node) {++minHeap->size;int i = minHeap->size - 1;while (i && node->weight < minHeap->array[(i - 1) / 2]->weight) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = node;
}// 构建最小堆
void buildMinHeap(MinHeap* minHeap) {int n = minHeap->size - 1;int i;for (i = (n - 1) / 2; i >= 0; --i)minHeapify(minHeap, i);
}// 判断是否是叶子节点
int isLeaf(HuffmanNode* root) {return !(root->left) && !(root->right);
}// 创建并构建最小堆
MinHeap* createAndBuildMinHeap(int weights[], int size) {MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(weights[i]);minHeap->size = size;buildMinHeap(minHeap);return minHeap;
}// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int weights[], int size) {HuffmanNode *left, *right, *top;MinHeap* minHeap = createAndBuildMinHeap(weights, size);while (!isSizeOne(minHeap)) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode(left->weight + right->weight);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 计算带权路径长度
int calculateWPL(HuffmanNode* root, int depth) {if (root == NULL) return 0;if (isLeaf(root)) return root->weight * depth;return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}int main() {int n;scanf("%d", &n);int weights[20];for (int i = 0; i < n; i++) {scanf("%d", &weights[i]);}HuffmanNode* root = buildHuffmanTree(weights, n);int wpl = calculateWPL(root, 0);printf("%d\n", wpl);return 0;
}