C语言构造哈夫曼树、哈夫曼编码

╰半夏微凉° 2022-02-16 08:18 205阅读 0赞

四个叶子节点\{1，3，5，5\}，构造Huffman树，并进行Huffman编码  
**设编码时：左分支为‘0’，右分支为‘1’**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXVALUE 10000 // 节点最大权值
    #define MAXLEAF 30 // 哈夫曼树叶子节点最大个数
    #define MAXNODE MAXLEAF * 2 - 1 // Huffman树中节点总数
    typedef struct { 
        int weight; // 节点权值
        int parent; // 无双亲节点时为-1，否则为双亲节点下标
        int lchild; // 无左孩子时为-1，否则为左孩子下标
        int rchild; // 无右孩子时为-1，否则为右孩子下标
    } HNode, HuffmanTree[MAXNODE];
    
    typedef struct CodeNode // 编码表的存储结构
    { 
        int weight; // 存放要表示的符号
        char *code; // 存放相应符号编码
    } CodeNode, HuffamanCode[MAXLEAF];
    
    /* * @description: 构造Huffman树 * @param w[]：传递n个叶子节点权值 * n：叶子节点个数 */
    void CreateHuffmanTree(HuffmanTree HTree, int w[], int n)
    { 
        /* * min1: 集合中最小权值 * min1: 集合中次小权值 * index1：最小权值节点下标 * index2：次小权值节点下标 */
    
        int i, j, min1, min2, index1, index2;
        // 树中节点初始化
        for (i = 0; i < 2 * n - 1; i++) { 
            HTree[i].weight = 0;
            HTree[i].parent = -1;
            HTree[i].lchild = -1;
            HTree[i].rchild = -1;
        }
    
        for (i = 0; i < n; i++)
            HTree[i].weight = w[i];
        printf("Huffman树初态\nindex | weight | parent | lchild | rchild\n");
        for (i = 0; i < 2 * n - 1; i++) { 
            printf("%3d%9d%9d%9d%9d\n", i, HTree[i].weight, HTree[i].parent,
                   HTree[i].lchild, HTree[i].rchild);
        }
        /* * 设n0(叶子节点)、n1(分支为1)、n2(分支为2)分别为二叉树中度为0、1、2的节点个数， * n为总节点个数，则 n = n0 + n1 + n2； * 设二叉树分支数为B，则 B = n + 1, B = n1 + 2 * n2； * 联立上述三个方程--->n0 = n2 + 1; * * Huffman树中只有度为0、2的节点： * n = n0 + n1 + n2 = n0 + n2； * n0 = n2 + 1； * Huffman树中：n = 2 * n0 - 1. */
        // 构造除n个叶子节点外的其余 n - 1 个双亲节点
        for (i = 0; i < n - 1; i++) { 
            min1 = min2 = MAXVALUE;
            index1 = index2 = 0;
    
            for (j = 0; j < n + i; j++) { 
                // 若节点权值比min1小且该节点无双亲节点，则更新最小节点
                if (HTree[j].weight < min1 && HTree[j].parent == -1) { 
                    min2 = min1;
                    index2 = index1; // 更新次小节点
                    index1 = j;
                    min1 = HTree[j].weight;
                }
                // 若 min1 < 节点权值 < min2, 且该节点无双亲节点，则更新次小节点
                else if (HTree[j].weight < min2 && HTree[j].parent == -1) { 
                    index2 = j;
                    min2 = HTree[j].weight;
                }
            }
    
            HTree[index1].parent = n + i;
            HTree[index2].parent = n + i;
            HTree[n + i].weight = HTree[index1].weight + HTree[index2].weight;
            HTree[n + i].lchild = index1;
            HTree[n + i].rchild = index2;
        }
    }
    
    /* * 从叶子节点-->根节点逆向搜索，若当前节点是其双亲左孩子，置‘0’，否则置‘1’ * @param：HTree：构造好的Huffman树 * HCode：Huffman树叶子节点编码 * n：叶子节点个数 */
    void HuffmanCoding(HuffmanTree HTree, HuffamanCode HCode, int n)
    { 
        char *cd;
        int i, child, parent, start;
    
        // n个叶子节点的Huffman树，叶子节点最长路径为 n-1，加上'\0'，共n个空间
        cd = (char *)malloc(n * sizeof(char));
        cd[n - 1] = '\0';
    
        // 求n个叶子节点的Huffman编码
        for (i = 0; i < n; i++) { 
            start = n - 1;
            child = i;                // child：当前节点下标
            parent = HTree[i].parent; // parent：当前节点双亲节点下标
    
            // 若未搜寻至根节点，则一直循环
            while (parent != -1) { 
                start--;
                if (HTree[parent].lchild == child)
                    cd[start] = '0'; // 左孩子，置‘0’
                else
                    cd[start] = '1'; // 右孩子，置‘1’
    
                child = parent; // 旧双亲节点作为新孩子节点
                parent = HTree[parent].parent; // 旧双亲节点的双亲节点作为新双亲节点
            }
    
            HCode[i].code = (char *)malloc((n - start) * sizeof(char));
            HCode[i].weight = HTree[i].weight;
            strcpy(HCode[i].code, &cd[start]);
        }
        free(cd);
    }
    
    int main(void)
    { 
        int w[] = { 1, 3, 5, 5}, n = 4;
        HuffmanTree ht;
        HuffamanCode hc;
    
        CreateHuffmanTree(ht, w, n);
        printf("Huffman树终态\nindex | weight | parent | lchild | rchild\n");
        for (int i = 0; i < 2 * n - 1; i++) { 
            printf("%3d%9d%9d%9d%9d\n", i, ht[i].weight, ht[i].parent, ht[i].lchild,
                   ht[i].rchild);
        }
    
        HuffmanCoding(ht, hc, n);
        printf("Huffman编码\n节点值 编码\n");
        for (int i = 0; i < n; i++) { 
            printf("%4d\t%s\n", hc[i].weight, hc[i].code);
        }
    
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220216/2fdc0d0c89c5421eacdecd88cd427135.png