哈夫曼树

结构定义

 typedef struct huffman_node {
    int weight; //权重
    int parent, lchild, rchild; //三叉链表
 } HF_NODE;

函数定义

#include <climits>
#include <cstdio>
#include <cstring>
#include <iostream>
// 存储结构
// typedef struct huffman_node {
//     int weight; //权重
//     int parent, lchild, rchild; //三叉链表
// } HF_NODE;
// 寻找两个最小的权重i之前的,因为i之前的节点是构造之后的节点
void select(HF_NODE *huffman_tree, int index, int &s1, int &s2) {
    // 初始化 s1 和 s2 为最小值
    s1 = s2 = -1;
    int min1 = INT_MAX, min2 = INT_MAX;
    // 遍历所有节点，找到两个最小的权重
    for (int i = 0; i < index; ++i) {
        if (huffman_tree[i].parent == -1) {
            // 只考虑未处理的节点
            if (huffman_tree[i].weight < min1) {
                min2 = min1;
                s2 = s1;
                min1 = huffman_tree[i].weight;
                s1 = i;
            } else if (huffman_tree[i].weight < min2) {
                min2 = huffman_tree[i].weight;
                s2 = i;
            }
        }
    }
}
// 初始化 huffman_tree
void init_huffman_tree(HF_NODE *huffman_tree, int *weight, int n) {
    // 初始化 每个节点的权重、父节点、左右孩子节点为 -1
    for (int i = 0; i < n * 2 - 1; ++i) {
        huffman_tree[i].parent = -1;
        huffman_tree[i].lchild = -1;
        huffman_tree[i].rchild = -1;
    }
    // 初始化 每个节点的权重
    for (int i = 0; i < n; ++i) {
        huffman_tree[i].weight = weight[i];
    }
    // 从 n 开始，依次合并节点
    for (int i = n; i < n * 2 - 1; ++i) {
        // 找到两个最小的权重节点
        int s1, s2;
        select(huffman_tree, i, s1, s2);
        // 构造新节点
        huffman_tree[i].weight = huffman_tree[s1].weight + huffman_tree[s2].weight;
        huffman_tree[i].lchild = s1;
        huffman_tree[i].rchild = s2;
        huffman_tree[s1].parent = i;
        huffman_tree[s2].parent = i;
    }
    // for (int i = 0; i < n * 2 - 1; ++i) {
    //     printf("node %d: weight = %d, parent = %d, lchild = %d, rchild = %d\n", i, huffman_tree[i].weight,
    //            huffman_tree[i].parent, huffman_tree[i].lchild, huffman_tree[i].rchild);
    // }
}
// 编码 codes为编码结果
void huffman_encoding(HF_NODE *huffman_tree, char *codes[], int n) {
    // 从叶子节点开始，向上寻找父节点，记录路径，直到根节点
    for (int i = 0; i < n; i++) {
        char res[n];
        memset(res, ' ', n);
        int strart = n - 1;
        int pos = i;
        int parent = huffman_tree[pos].parent;
        while (parent != -1) {
            if (huffman_tree[parent].lchild == pos) {
                res[--strart] = '0';
            } else {
                res[--strart] = '1';
            }
            pos = parent;
            parent = huffman_tree[pos].parent;
        }
        // 去除 前导空格
        int l;
        int f = 0;
        while (res[f] == ' ') f++;
        for ( l = 0; l < n; l++) {
            res[l] = res[f++];
        }
        res[l] = '\0';
        codes[i] = (char *) malloc(n * sizeof(char));
        strcpy(codes[i], res);
    }
}
// 解码 a为 编码后的字符串，words为对应的符号
void huffman_decoding(HF_NODE *huffman_tree, char A[], char words[], int n) {
    int root = n*2-2;
    int p = root;
    int len = strlen(A);
    for (int i = 0; i < len; i++) {
        if (A[i] == '0') {
            p = huffman_tree[p].lchild;
        } else {
            p = huffman_tree[p].rchild;
        }
        if (huffman_tree[p].lchild == -1 && huffman_tree[p].rchild == -1) {
            printf("%c", words[p]);
            p = root;
        }
    }
}

测试代码

int main() {
    // 字符及其对应的权重
    char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int weights[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(chars) / sizeof(chars[0]);

    // 创建Huffman树
    HF_NODE *huffman_tree = (HF_NODE *)malloc((2 * n - 1) * sizeof(HF_NODE));
    init_huffman_tree(huffman_tree, weights, n);

    // 存储Huffman编码
    char **codes = (char **)malloc(n * sizeof(char *));
    huffman_encoding(huffman_tree, codes, n);

    // 打印Huffman编码
    for (int i = 0; i < n; i++) {
        printf("%d Character: %c, Huffman Code: %s, Weight:%d \n" , i,chars[i], codes[i], weights[i]);
    }
    // 解码Huffman编码字符串
    char encoded_str[] = "110011001100";
    printf("Encoded string: %s\n", encoded_str);
    printf("Decoded string: ");
    huffman_decoding(huffman_tree, encoded_str,chars, n);
    printf("\n");

    // 释放内存
    for (int i = 0; i < n; i++) {
        free(codes[i]);
    }
    free(codes);
    free(huffman_tree);
    return 0;
}