使用C语言详解霍夫曼树数据结构

什么是霍夫曼树

霍夫曼树是一种带权路径长度最短的树，也称为最优二叉树，它是优化编码的核心算法。

在霍夫曼树中，每个叶子节点对应一个字符，该节点的权值为该字符出现的次数。当然，字符可以是任何数据类型。生成霍夫曼树后，在对每个字符进行编码时，字符在霍夫曼树中的路径即为其编码。（一般规定，一条从根到叶子的路径上只出现0或1，从根到某个叶子节点的路径就是该叶子节点对应字符的哈夫曼编码。）

如何生成霍夫曼树

生成霍夫曼树的过程是：首先，把所有的节点按权值从小到大排序，选出权值最小的两个节点组成一棵新的二叉树，它们成为新二叉树的左右子树，新二叉树的根节点的权值是它的左右子树权值之和。在原来的节点序列中，把这两个最小权值的节点删除，并把新生成的根节点加入节点序列。重复上述过程，直到序列中只剩下一个节点为止，这个节点即为霍夫曼树的根节点。

下面是示例代码：

typedef struct _HuffmanTreeNode
{
    int weight;                 // 权重（节点存储的值）
    struct _HuffmanTreeNode *lchild, *rchild;   // 左右子树
}HuffmanTreeNode;

HuffmanTreeNode* CreateHuffmanTree(int weight[], int n)
{
    // 初始化n个叶子结点
    HuffmanTreeNode **nodeList = (HuffmanTreeNode**)malloc(sizeof(HuffmanTreeNode*) * n);
    for (int i = 0; i < n; i++) 
    {
        nodeList[i] = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode));
        nodeList[i]->weight = weight[i];
        nodeList[i]->lchild = nodeList[i]->rchild = NULL;
    }

    // 生成哈夫曼树
    while(n > 1)
    {
        int min1 = 0, min2 = 1;
        if(nodeList[min1]->weight > nodeList[min2]->weight)
        {
            int tmp = min1;
            min1 = min2;
            min2 = tmp;
        }
        for(int i = 2; i < n; i++)
        {
            if(nodeList[i]->weight < nodeList[min1]->weight)
            {
                min2 = min1;
                min1 = i;
            }
            else if(nodeList[i]->weight < nodeList[min2]->weight)
            {
                min2 = i;
            }
        }

        // 组成新的二叉树
        HuffmanTreeNode *newNode = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode));
        newNode->weight = nodeList[min1]->weight + nodeList[min2]->weight;
        newNode->lchild = nodeList[min1];
        newNode->rchild = nodeList[min2];
        nodeList[min1] = newNode;//将两个子节点合并到一个新节点
        nodeList[min2] = nodeList[n-1];//注意将n-1赋值，因为有一个原叶子节点已经被合并
        n--;
    }
    return nodeList[0];
}

如何通过霍夫曼树来编码

霍夫曼编码存在优美的数学性质：任意一个字符的编码都不是另一个字符编码的前缀，所以解码时不会发生歧义。

下面是示例代码：

void GetHuffmanCode(HuffmanTreeNode* root, char* code, char** codes, int depth)
{
    static int count = 0;               // 存储编码字符串的长度
    if(root == NULL)                    // 树到了根节点
        return ;
    if(root->lchild == NULL && root->rchild == NULL)
    {
        code[count] = '\0';
        codes[root->weight] = (char*)malloc(sizeof(char)*count);
        strcpy(codes[root->weight], code);
        return ;
    }
    count++;
    code[count-1] = '0';//左子树编码为0
    GetHuffmanCode(root->lchild, code, codes, depth + 1);
    code[count-1] = '1';//右子树编码为1
    GetHuffmanCode(root->rchild, code, codes, depth + 1);
    count--;
}

示例

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

typedef struct _HuffmanTreeNode
{
    int weight;                 // 权重（节点存储的值）
    struct _HuffmanTreeNode *lchild, *rchild;   // 左右子树
}HuffmanTreeNode;

HuffmanTreeNode* CreateHuffmanTree(int weight[], int n)
{
    // 初始化n个叶子结点
    HuffmanTreeNode **nodeList = (HuffmanTreeNode**)malloc(sizeof(HuffmanTreeNode*) * n);
    for (int i = 0; i < n; i++) 
    {
        nodeList[i] = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode));
        nodeList[i]->weight = weight[i];
        nodeList[i]->lchild = nodeList[i]->rchild = NULL;
    }

    // 生成哈夫曼树
    while(n > 1)
    {
        int min1 = 0, min2 = 1;
        if(nodeList[min1]->weight > nodeList[min2]->weight)
        {
            int tmp = min1;
            min1 = min2;
            min2 = tmp;
        }
        for(int i = 2; i < n; i++)
        {
            if(nodeList[i]->weight < nodeList[min1]->weight)
            {
                min2 = min1;
                min1 = i;
            }
            else if(nodeList[i]->weight < nodeList[min2]->weight)
            {
                min2 = i;
            }
        }
        // 组成新的二叉树
        HuffmanTreeNode *newNode = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode));
        newNode->weight = nodeList[min1]->weight + nodeList[min2]->weight;
        newNode->lchild = nodeList[min1];
        newNode->rchild = nodeList[min2];
        nodeList[min1] = newNode;//将两个子节点合并到一个新节点
        nodeList[min2] = nodeList[n-1];//注意将n-1赋值，因为有一个原叶子节点已经被合并
        n--;
    }
    return nodeList[0];
}

void GetHuffmanCode(HuffmanTreeNode* root, char* code, char** codes, int depth)
{
    static int count = 0;               // 存储编码字符串的长度
    if(root == NULL)                    // 树到了根节点
        return ;
    if(root->lchild == NULL && root->rchild == NULL)
    {
        code[count] = '\0';
        codes[root->weight] = (char*)malloc(sizeof(char)*count);
        strcpy(codes[root->weight], code);
        return ;
    }
    count++;
    code[count-1] = '0';//左子树编码为0
    GetHuffmanCode(root->lchild, code, codes, depth + 1);
    code[count-1] = '1';//右子树编码为1
    GetHuffmanCode(root->rchild, code, codes, depth + 1);
    count--;
}

void PrintCode(char** codes,int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d %s\n",i,codes[i]);
    }
}

int main()
{
    int weight[] = {5, 6, 8, 7, 15 ,10};
    char* codes[6] = {0};
    char code[100];
    HuffmanTreeNode *root = CreateHuffmanTree(weight, 6);
    GetHuffmanCode(root, code, codes, 0);
    PrintCode(codes,6);
    return 0;
}

以上代码的输出结果为：

0 011
1 010
2 111
3 110
4 00
5 101

其中第i行表示值为i的节点对应的编码为code[i]。

总结

霍夫曼树不仅可以用于编码和压缩，还可以应用于诸如数据存储、加密和网络通信等领域，掌握霍夫曼树对于算法理解和应用编程都有很大的帮助。