C语言实现哈夫曼树构建 - 代码示例及详解

#include <stdio.h>\n#include <stdlib.h>\n\n// 哈夫曼树节点结构体\ntypedef struct TreeNode {\n int weight; // 权重\n struct TreeNode* left; // 左子树指针\n struct TreeNode* right; // 右子树指针\n} TreeNode;\n\n// 构建哈夫曼树\nTreeNode* buildHuffmanTree(int weights[], int n) {\n TreeNode** nodes = (TreeNode**)malloc(n * sizeof(TreeNode*));\n for (int i = 0; i < n; i++) {\n nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));\n nodes[i]->weight = weights[i];\n nodes[i]->left = NULL;\n nodes[i]->right = NULL;\n }\n\n while (n > 1) {\n // 找到权重最小的两个节点\n int min1 = 0, min2 = 1;\n if (nodes[min1]->weight > nodes[min2]->weight) {\n int temp = min1;\n min1 = min2;\n min2 = temp;\n }\n for (int i = 2; i < n; i++) {\n if (nodes[i]->weight < nodes[min1]->weight) {\n min2 = min1;\n min1 = i;\n } else if (nodes[i]->weight < nodes[min2]->weight) {\n min2 = i;\n }\n }\n\n // 创建新节点，将两个最小的节点作为子节点\n TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));\n newNode->weight = nodes[min1]->weight + nodes[min2]->weight;\n newNode->left = nodes[min1];\n newNode->right = nodes[min2];\n\n // 从节点数组中移除两个最小的节点，将新节点加入数组\n nodes[min1] = newNode;\n nodes[min2] = nodes[n-1];\n n--;\n }\n\n TreeNode* root = nodes[0];\n free(nodes);\n return root;\n}\n\n// 打印哈夫曼树\nvoid printHuffmanTree(TreeNode* root) {\n if (root == NULL) {\n return;\n }\n\n printf("%d\n", root->weight);\n printHuffmanTree(root->left);\n printHuffmanTree(root->right);\n}\n\nint main() {\n int weights[] = {5, 9, 12, 13, 16, 45};\n int n = sizeof(weights) / sizeof(weights[0]);\n\n TreeNode* root = buildHuffmanTree(weights, n);\n printHuffmanTree(root);\n\n return 0;\n}\n\n// 构建的哈夫曼树的权重信息\n// 100\n// 45\n// 55\n// 9\n// 12\n// 23\n// 13\n