C/C++哈夫曼树-最优二叉树

概述

哈夫曼树又称为最优二叉树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点的通路，路径上的分支数目称之为路径长度。

树的路径长度是树根到每个叶子之间的路径长度之和。结点的带权路径长度为该结点到树根之间的路径长度与该结点权值的乘积。

树的带权路径长度为树的所有结点的带权路径之和。

故树的带权路径长度最小的二叉树称最优二叉树或哈夫曼树。

哈夫曼树的用途

在数据通信、数据压缩问题中，采用由二进制字符0、1组成的二进制串。为提供通信效率，因为希望尽可能的缩短串的总长度。因为每个字符出现的频率不同，如果在编码时考虑字符的出现频率，使频率高的字符尽可能采用短的编码，频率高的字符采用稍长的编码，来构造一种不等长编码来提高空间利用率及通信效率。如果要设计长度不等的编码，还必须要考虑任何一个字符的编码都不是另一个字符的编码的前缀。这种编码称之为哈夫曼编码。这正是最优二叉树的核心思想，即权值越大的结点离根越近，越应先访问到。

构造最优二叉树

根据给定的权值，构造出n个独立的根结点的树，这n颗结点构成森林F。

在森林F中删除并选取两颗权值最小的结点作为左右子树构造出一颗新的二叉树，且将这颗二叉树的根结点权值置为两颗结点权值之和，并放入森林F中。

重复以上步骤，直到森林F中只含一颗树为止，这颗树便是哈夫曼树，这种生成算法便是典型的贪心法。

实现

struct HuffmanTreeNode
{
    int weight=0;
    int parent=0,lchild=0,rchild=0;
};
typedef char** HuffmanCode;

构造哈夫曼树：给定权值结点列表，每次从森林F中删除并选取两颗权值最小的结点作为左右子树构造出一颗新的二叉树，且将这颗二叉树的根结点权值置为两颗结点权值之和，并调整父子结点关系。

    void CreateHuffmanTree(int *leaves, int leaf_count)
    {
        if (leaf_count <= 1)
        {
            return;
        }

        int n = leaf_count * 2 - 1; // 叶子节点可推出总节点数
        length=n;
        if (elems != nullptr)
        {
            delete (elems);
        }
        // 0号元素作为哨岗（可以学习这个思想，但是要知其所以然。不能照本宣书）故开辟n+1
        elems = new HuffmanTreeNode[n + 1];
        // 前n个单元为叶子节点

        for (size_t i = 1; i <= leaf_count; i++)
        {
            elems[i].weight = leaves[i - 1];
        }
        // 创建逻辑
        int nodeIndex1 = -1;
        int nodeIndex2 = -1;
        for (size_t i = leaf_count + 1; i <= n; i++)
        {
            // end:i-1 从叶子节点以及已经创建出的非叶节点中选出目前无双亲且权值最小的节点
            Select(1, i - 1, nodeIndex1, nodeIndex2);
            elems[nodeIndex1].parent = i; // 指定i  i就是此次生成的非叶节点。
            elems[nodeIndex2].parent = i;
            // 哈夫曼树没有明确规定每次选出的两个节点谁是左谁是右。
            // 不同的规定 构造出的树可能不同。所以我就规定以小在左，大在右。
            elems[i].lchild = nodeIndex1;
            elems[i].rchild = nodeIndex2;
            elems[i].weight = elems[nodeIndex1].weight + elems[nodeIndex2].weight;
        }
    }

从森林中选出权值最小的两颗树

void Select(int start, int end, int &nodeIndex1, int &nodeIndex2)
    {
        int min1 = 0, min2 = 0;
        for (size_t i = start; i <= end; i++)
        {
            if (elems[i].parent == 0)
            {
                if (min1==0||elems[min1].weight > elems[i].weight)
                {
                    min1 = i;
                }
            }
        }

        for (size_t i = start; i <= end; i++)
        {
            if (elems[i].parent == 0 && i != min1)
            {
                if (min2==0||elems[min2].weight > elems[i].weight)
                {
                    min2 = i;
                }
            }
        }
        if (min1 > min2)
        {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }
        nodeIndex1 = min1;
        nodeIndex2 = min2;
    }

哈夫曼编码：哈夫曼编码是最优前缀编码，已知叶子结点在数组中范围为[1,n],遍历树，给树中每个结点左分支上标记0，右分支标记1。这样从树根到叶子结点，输出路径上的0、1标记，最后得到的就是这个字符的哈夫曼编码。

void HuffmanTreeCode(HuffmanCode codes)
    {
        // codes [0,leaf_Count-1] 
        int leaf_Count=length;
        int start,father;
        //从叶子节点向上追溯到根，逆向找出这个叶子节点的编码。
        char* code=(char*)malloc(sizeof(char)*leaf_Count);//code最大为n-1
        //因为每一个叶子节点 都需一个非叶节点。且路径分支等于叶子节点到根节点路径上的非叶节点个数。根据等式可得all-leafCount=2*n-1-n=n-1。
        code[leaf_Count-1]='\0';//最后一个空间作为结束符。
        //叶子节点索引[1,n]
        for (size_t i = 1; i <=leaf_Count; i++)
        {
            start=leaf_Count-1;
            
            for (size_t j = i,father=elems[j].parent; father!=0; j=father,father=elems[father].parent)
            {
                if (elems[father].lchild==j)
                {
                    code[--start]='0';
                }
                else
                {
                    code[--start]='1';
                }
            }
            //编码数据占用 leafCount-2-start+1  编码数据的最后一位索引为leafcount-2
            //再存储一位结束符，索引为leafcount-1 即占用leafcount-start  
            codes[i-1]=(char*)malloc((leaf_Count-start)*sizeof(char));
            strcpy(codes[i-1],code+start);
        }
    }

哈夫曼编码提高了数据通信的效率，在数据通信中，一方使用哈夫曼编码，那必然另一方需要特定规则进行译码读出字符串。 这个过程叫做译码。

译码：因为任何一个字符的编码都不是另一个字符的编码的前缀。所以译码的过程很简单，遍历哈夫曼编码，从根节点开始，遇到0表示分支为当前结点的左分支，反之为当前结点的右分支，直到遇到叶子节点就完成了一次字符的译码。

    char* Decoding(const char *charElems,const char *code)
    {
        int i;
        int root=length;
        int node=root;
        int leafCount=GetLeafCount();
        int arrayMallocCount=leafCount+1;
        char* decodingString=(char*)malloc(sizeof(char)*(arrayMallocCount));
        int charCount=0;
        for (i = 0; *code; i++,code++)
        {
            if (*code=='0')
            {
                node=elems[node].lchild;
            }
            else
            {
                node=elems[node].rchild;
            }
            if (elems[node].lchild==0&&elems[node].rchild==0)
            {
                if (i>=(arrayMallocCount-1))
                {
                    arrayMallocCount+=leafCount;
                    decodingString=(char*)realloc(decodingString,sizeof(char)*(arrayMallocCount));
                }
                
                decodingString[charCount]=charElems[node-1];
                charCount++;
                node=root;
            }
        }
        decodingString[charCount]='\0';
        return decodingString;
    }

测试

#include "stdio.h"
#include <iostream>
#include <cstring>
using   namespace   std;
#include "HuffmanTree.h"
void OutputHuffmanCodes(const HuffmanCode codes,int length);
void OutputDecodingStr(char *deserialize_String);
int main()
{
    HuffmanTree* huffmanTree=new HuffmanTree();
    // int leaves[]={1,2,3,4,5,6,7};
    int leaves[]={1,2,3};
    int len=3;
    huffmanTree->CreateHuffmanTree(leaves,len);
    huffmanTree->PreorderTraverseByRecursion(2*len-1,false);//{1,2,3}验证正确
    HuffmanCode codes=(HuffmanCode)malloc(sizeof(char*)*len);
    huffmanTree->HuffmanTreeCode(codes);
    OutputHuffmanCodes(codes,len);//{1,2,3}验证正确 //10 11 0
    const char *charElems="abc";
    char *codeSerialize=(char*)((((string)"10")+"11"+"0"+"0"+"11"+"10"+"11").c_str());
    char *deserialize_String=huffmanTree->Decoding(charElems,codeSerialize);
    OutputDecodingStr(deserialize_String);
    system("pause");
    return 1;
}
void OutputHuffmanCodes(const HuffmanCode codes,int length)
{
    for (size_t i = 0; i < length; i++)
    {
        printf("%s \n",codes[i]);
    }
    
}
void OutputDecodingStr(char *deserialize_String)
{
    printf("%s \n",deserialize_String);
}

结果：