霍夫曼树（Huffman Tree）

一、简介

        给定N个权值为N的叶子节点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也成为霍夫曼树。霍夫曼树是带权路径长度最短的树，权值最大的节点离根较近。

二、霍夫曼树的构造

        根据霍夫曼树的特性可以得知，权值越大的叶子节点越靠近根节点。构造霍夫曼树的算法称为霍夫曼算法。

        如果输入权值为（w1,w2,w3,…,wn）的n个节点，要求输出相对应的霍夫曼树，那怎么办呢？过程如下：

• 将(w1,w2,w1,…,wn)看作n棵树的森林，每个树仅有一个节点；
• 在森林中选择权值最小的两棵树进行合并，得到新的树。这两个数分别是新的树的左右子树。新的树的根节点权重为左右子树根节点权重之和；
• 将之前的根节点权值最小的两棵树从森林里删除，把新的树加入森林；
• 重复第2、3两步，直到森林里只有一棵树。

        例如将以5，15，20，30，10为权的W构造成霍夫曼树，过程如图1所示。

三、霍夫曼树的应用

        霍夫曼树用于通讯及数据传送中对信息的二进制编码。

四、代码实现

#include 
using namespace std;
//哈夫曼的存储结构
typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode, *HuffmamTree;
//选两个权值最小的结点
void Select(HuffmamTree &HT, int n, int &s1, int &s2){
    int min;
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent==0)
        {
            min=i;
            break;
        }
    }
    for(int j=1; j<=n; j++)
    {
        if(HT[j].parent==0)
        {
            if(HT[j].weight
            {
                min=j;
            }
        }
    }
    s1=min;
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent==0&&i!=s1)
        {
            min=i;
            break;
        }
    }
    for(int j=1; j<=n; j++)
    {
        if(HT[j].parent==0&&j!=s1)
        {
            if(HT[j].weight
            {
                min=j;
            }
        }
    }
    s2=min;
}
//输出哈夫曼树状态表
void Show(HuffmamTree HT,int m){
    cout<<"==============================="<
    for (int i = 1; i <= m; ++i) {
        cout<".   "<"   "<"   "<"   "<
        cout<<"-------------------------"<
    }
}
//创建哈夫曼树
void CreateHuffmanTree(HuffmamTree &HT,int n){
    //初始化构造n个结点的哈夫曼树
    if(n<=1)
    {
    	return;
    }
    int m=n*2-1;
    HT=new HTNode[m+1];
    for(int i=0; i <= m; i++)
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
        HT[i].weight=0;
    }
    for(int j=1; j<=n; j++)
    {
        cout<<"请输入第"<"个结点的权值:";
        cin>>HT[j].weight;
    }
    //输出哈夫曼树初态表
    cout<<"HT的初态："<
    Show(HT,m);
    //创建哈夫曼树
    int s1,s2;
    for(int i=n+1; i<=m; i++)
    {
        Select(HT,i-1,s1,s2);//从HT[k](1 <= k <= i-1)中获得两个权值最小的结点的位置
        HT[s1].parent=i;//将s1 s2位置的结点的双亲域改为i
        HT[s2].parent=i;
        HT[i].lchild=s1;//s1 s2分别作为结点i的左右子树
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight + HT[s2].weight;//i结点的权值等于左右子树权值之和
    }
    //输出哈夫曼树终态表
    cout<<"HT的终态："<
    Show(HT, m);
}
int main()
{
    HuffmamTree HT;
    int n;
    cout<<"请输入叶子节点个数:";
    cin>>n;
    CreateHuffmanTree(HT,n);
    return 0;
}

---

参考文献：

构造哈夫曼树代码实现（C++）_果酱包的博客-CSDN博客_哈夫曼树代码实现哈夫曼树又称作最优二叉树，是带权路径长度最小的二叉树。一、算法步骤：构造哈夫曼树算法的实现可以分成两大部分。①初始化:首先动态申请2n个单元;然后循环2n-1次，从1号单元开始，依次将1至m所有单元中的双亲、左孩子、右孩子的下标都初始化为0;最后再循环n次，输人前n个单中叶子结点的权值。②创建树:循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；删除是指将结点s1和s2的双亲改为非0；合并就是将s1和s2的权值和作为.https://blog.csdn.net/qq_46601680/article/details/120973027感谢阅读！