#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int weight;
    struct Node *left, *right;
} Node;

// 比较函数用于 qsort
int compare(const void* a, const void* b) {
    return (*(Node**)a)->weight - (*(Node**)b)->weight;
}

// 创建新节点
Node* createNode(int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->weight = weight;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 构建哈夫曼树
Node* createHuffmanTree(int* weights, int size) {
    Node** nodes = malloc(size * sizeof(Node*));
    for (int i = 0; i < size; i++) {
        nodes[i] = createNode(weights[i]);
    }
    while (size > 1) { 
        qsort(nodes, size, sizeof(Node*), compare);// 排序节点数组 
        // 创建父节点
        Node* parent = createNode(nodes[0]->weight + nodes[1]->weight);
        parent->left = nodes[0];
        parent->right = nodes[1];
        
        // 替换前两个最小节点
        nodes[0] = parent;
        for (int i = 1; i < size - 1; i++) {
            nodes[i] = nodes[i + 1];
        }
        size--;
    }
    Node* root = nodes[0];
    free(nodes);
    return root;
}

// 递归生成哈夫曼编码
void encode(Node* node, char* code, int depth) {
    if (node->left == NULL && node->right == NULL) {
        code[depth] = '\0';//终止字符串
        printf("权重: %d, 编码: %s\n", node->weight, code); 
        return;
    }
    code[depth] = '0';
    encode(node->left, code, depth + 1);
    code[depth] = '1';
    encode(node->right, code, depth + 1);
}

// 解码函数
void decode(Node* root, const char* encoded) {
    Node* current = root;
    while (*encoded) {
        if (*encoded == '0') {
            current = current->left;
        } else {
            current = current->right;
        } 
        // 到达叶子节点，打印权重并返回根节点
        if (current->left == NULL && current->right == NULL) {
            printf("解码权重: %d\n", current->weight);
            current = root; // 回到根节点
        }
        encoded++;// 移动到下一个字符
    }
}
// 释放内存
void freeTree(Node* node) {
    if (node) {
        freeTree(node->left);
        freeTree(node->right);
        free(node);
    }
}

int main() {
    int weights[] = {2, 3, 7, 9, 18, 25};
    int size = sizeof(weights) / sizeof(weights[0]);
    Node* root = createHuffmanTree(weights, size);
    char code[100]; // 假设编码长度不会超过100
    printf("编码:\n");
    encode(root, code, 0); 
 
    const char* encoded = "0010101111"; 
    printf("解码-0010101111:\n");
    decode(root, encoded); 

    freeTree(root);
    return 0;
}