🌺哈夫曼树的基本概念

Q：什么是哈夫曼树

A：哈夫曼树又称最优树，是一类带权路径长度最短的树。在正式了解哈夫曼树之前，我们需要了解一些概念。

1）路径

Q：什么是路径

A：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

2）路径长度

Q：什么是路径长度

A：路径上的分支数目称作路径长度。如图根结点到结点B的路径长度为2

3）权

Q：什么是权

A：若将树中结点赋给一个带有某种含义的数值，则该数值称为该结点的权。如图A的权是7

4）结点的带权路径长度

Q：什么是结点的带权路径长度

A：从该结点到树根之间的路径长度与结点上权的乘积

5）树的带权路径长度

Q：什么是树的带权路径长度

A：树中所有叶子结点的带权路径长度之和，通常记作 WPL。如图WPL=7*1+5*2+2*3+4*3=35

6）哈夫曼树

Q：什么是树的带权路径长度

A：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。

Q：哈夫曼树中具有不同权值的叶子结点的分布有什么特点呢？

A：从上面的例子中，可以直观的发现，在哈夫曼树中，权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称为哈夫曼算法。

🌺哈夫曼树的构造算法

🍁哈夫曼树的构造过程

Q：假设有4个叶子结点，权重依次是7，5，2，4，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？

第一步：将这4个结点分别作为4棵仅含有一个结点的二叉树，形成一个森林

第二步：选择当前权值最小的两个结点C和D，根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和

第三步：选择当前权值最小的两个结点，再次根据这两个结点生成一个新的父结点。现在剩下的结点有7，6，5，我们根据6和5生成新的父节点。

第四步：选择当前权值最小的两个结点，再次根据这两个结点生成一个新的父结点。现在剩下的结点有7，11，我们根据7和11生成新的父节点。

就这样，我们得到了最终的二叉树

🍁哈夫曼树算法的实现

1）结点的存储结构

哈夫曼树是一种二叉树，树中每个结点要包含其双亲信息和孩子结点的信息，由此，每个结点的存储结构如图：

typedef struct{ 
  int weight;      //结点的权值
  int parent,lchild,rchild;  //结点的双亲、左孩子、右孩子的下标
) HTNode,*HuffmanTree;    //动态分配数组存储哈夫曼树

2）构建哈夫曼树

构建哈夫曼树主要分为两大部步

第一步为森林结点的初始化，第二步为哈夫曼树的建立。

💬代码演示

void CreateHuffmanTree(HuffmanTree &HT,int n) 
{//构造哈夫曼树 HT
  if(n<=1) return; 
  m=2*n-1; 
  HT=new HTNode[m+1];     //0 号单元未用，所以需要动态分配 m+l 个单元， HT[m)表示根结点
  for(i=1;i<=m;++i)       //将l~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
  {
    HT[i].parent=O;
    HT[i].lchild=O;
    HT[i].rchild=O;
  } 
  for(i=1;i<=n;++i)     //输人前 n 个单元中叶子结点的权值
    cin>>HT[i].weight; 
  for(i=n+1;i<=m;++i)
  {//通过 n-1 次的选择、删除 、 合并来创建哈夫曼树
    Select (HT,i-1,s1,s2); 
    //在 HT[k] 中选择两个其双亲域为 0 且权值最小的结点，并返回它们在 HT 中的序号 s1和 s2
    HT[s1].parent=i;
    HT[s2].parent=i; 
    //得到新结点 i, 从森林中删除sl, s2, 将sl和s2 的双亲域由 0改为l.
    HT[i].lchild=s1;
    HT[i].rchild=s2;    //sl, s2分别作为 i 的左右孩子
    HT[i].weight=HT[s1].weight+HT[s2].weight; // i 的权值为左右孩子权值之和
  }
}