Huffman Tree in C-526互联

//
//  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;
}