哈夫曼树浅谈

哈夫曼树浅谈

1.定义

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等

• 结点的带权路径长度：从树的 根结点 到该结点的路径长度（经过的边数）与该结点上权值的乘积

• 树的带权路径长度：树中所有 叶结点 的带权路径长度之和（ WPL, Weighted PathLength ）

• 在含有 n 个带权叶结点的二叉树中，其中带权路径长度（ WPL ）最小的 二叉树 称为哈夫曼树，也称最优二叉树

2.构造

哈夫曼树权值越大的叶子离根越近
贪心算法思想，先选择最小的叶子

1. 给定 n 个权值分别为 w1, w2,…, wn 的结点，构造哈夫曼树的算法描述如下：

2. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F 。

3. 构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。

4. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入F 中。

5. 重复步骤2和3，直至 F 中只剩下一棵树为止。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n ,m , cnt;
struct tree{
    ll id;
    ll fa ,l ,r;
    ll w;
};
tree wow[1000];
tree wow2[1000];
bool cmp(tree a ,tree b){
    return a.w > b.w;
}
int main()
{
    cin >> n;
    cnt=m=n;
    for(int i=1;i<=n;i++){
        cin >> wow[i].w;
        wow2[i].w=wow[i].w;
        wow2[i].id=wow[i].id=i;
    }
    while(m>1)
    {
        sort(wow + 1 ,wow + m + 1,cmp);
        cnt++;
        //wow为现在的树 ，wow2为结点 ，wow[m]wow[m-1]删除组成新的一部分树
        wow2[cnt].id=cnt;
        wow2[cnt].l=wow[m-1].id;
        wow2[cnt].r=wow[m].id;
        wow2[wow[m].id].fa=wow2[wow[m-1].id].fa=cnt;
        wow2[cnt].w=wow2[wow[m].id].w+wow2[wow[m-1].id].w;
        wow[m-1].id=cnt;
        wow[m-1].w=wow2[cnt].w;
        
        m--;
    }
    for(int i=1;i<=cnt;i++){
        cout <<wow2[i].w<<' '<< wow2[i].fa << ' ' << wow2[i].l << ' ' << wow2[i].r  << endl;
    }
}

例题

P2556
P2168