//
// main.c
// HuffmanTree
//
// Created by steve xiaohu zhao on 2023/10/18.
//
#include <stdio.h>
#include <stdlib.h>
// 定义一个 Huffman Tree 的节点
struct HTNode {
// 表示权值
int weight;
// 定义一个左节点和右节点指针
struct HTNode *left, *right;
};
// 为节点起个别名
typedef struct HTNode *HuffmanTree;
// 创建哈夫曼树(用堆来实现)
HuffmanTree CreateHuffmanTree(MinHeap H) {
// 假设 H->Size 个权值已经保存在 H->Elements[]->Weight 里面
int i;
HuffmanTree T;
// 将 H->Elements[] 按权值调整为最小堆
BuildMinHeap(H);
// 做 H->Size - 1 次合并
for (int i = 1; i < H->Size; i++) {
// 建立新节点
T = malloc(sizeof(struct HTNode));
// 从最小堆中删除一个节点,作为新 T 的左子节点
T->left = DeleteMin(H);
// 从做小堆中删除一个节点,作为新 T 的右子节点
T->right = DeleteMin(H);
// 计算新的权值
T->weight = T->left->weight + T->right->weight;
// 将新 T 插入最小堆
Insert(H, T);
}
T = DeleteMin(H);
return T;
// 整体复杂度为:O(N*logN)
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
return 0;
}
标签:struct,weight,int,Tree,HuffmanTree,Huffman,节点,HTNode
From: https://www.cnblogs.com/zxhoo/p/17772332.html