[模板]哈夫曼树

#include <stdio.h>
#include <algorithm>
using namespace std;
struct arr
{
    int data,lc,rc,addr;
};
arr f[1000],a[1000];
int cam(arr a,arr b)
{
    return a.data<b.data;
}
int vist(int x)
{
    if (f[x].data==0) return 0;
    printf("%d ",f[x].data);
    vist(f[x].lc);
    vist(f[x].rc);
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].data);
        f[i].data=a[i].data;
        a[i].addr=i;
    }
    int t=n+1,i=n;

    while (i>1)
    {
        sort(a+1,a+i+1,cam);
        f[t].data=a[1].data+a[2].data;
        f[t].lc=a[1].addr;
        f[t].rc=a[2].addr;
        a[1].data=f[t].data;
        a[1].addr=t;
        a[2].data=a[i].data;
        a[2].addr=a[i].addr;
        t++; i--;
    }
    vist(t-1);
}

哈夫曼编码

#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
struct arr
{
    int data,lc,rc,addr,l;
};
arr f[1000],a[1000];
int cam(arr a,arr b)
{
    return a.data<b.data;
}
int vist(int x,string ch)
{
    if (f[x].data==0) return 0;
    vist(f[x].lc,ch+"0");
    vist(f[x].rc,ch+"1");
    if (f[x].lc==0&&f[x].rc==0) 
        printf("%d:%s\n",f[x].data,ch.c_str());
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].data);
        f[i].data=a[i].data;
        a[i].addr=i;
    }
    int t=n+1,i=n;

    while (i>1)
    {
        sort(a+1,a+i+1,cam);
        f[t].data=a[1].data+a[2].data;
        f[t].lc=a[1].addr;
        f[t].rc=a[2].addr;
        a[1].data=f[t].data;
        a[1].addr=t;
        a[2].data=a[i].data;
        a[2].addr=a[i].addr;
        t++; i--;
    }

    char st[100];

    vist(t-1,"");
}