哈弗曼树

最优二叉树：带权路径长度最小的二叉树称为哈弗曼树，也称为最优二叉。

哈弗曼树本身有N个节点，将这N个节点，从这N个节点选取2个最小的，合并成一个新节点。这时有N-1个节点，再将这N

-1个节点重复处理最终合并成一个节点。此时得到的树就是最优二叉树。

#include<iostream>
#include<algorithm>
using namespace std;
#define max 1000
int coun=0;
struct HuffManTree
{
    int weight;
    int parent;
    int lchild;
    int rchild;
};

void min(HuffManTree a[],int n,int &m)
{
    m=0;
    for(int i=0;i<n;i++)
    {
        if(a[i].weight<a[m].weight)
            m=i;
    }
}

void set_parent(HuffManTree &a,int parent)
{
    a.weight=max;
    a.parent=parent;
}

void set_child(HuffManTree &a,int lchild,int rchild)
{
    a.lchild=lchild;
    a.rchild=rchild;
}

void HuffCode(HuffManTree a[],int n)
{
    for(int i=n;i<2*n-1;i++)
    {
        int m1,m2;
        min(a,i,m1);
        a[i].weight=a[m1].weight;
        set_parent(a[m1],i);
        min(a,i,m2);
        a[i].weight+=a[m2].weight;
        set_parent(a[m2],i);
        set_child(a[i],m1,m2);
        coun+=a[i].weight;
    }
}

void Input(HuffManTree a[],int n)
{
    for(int i=0;i<n;i++)
    {
        cin>>a[i].weight;
        a[i].lchild=-1;
        a[i].rchild=-1;
    }
    a[2*n-2].parent=2*n-1;
}

void Output(HuffManTree a[],int n)
{
    for(int i=0;i<2*n-1;i++)
    {
        cout<<a[i].parent<<"  ";
    }
    cout<<coun<<endl;
}

int main()
{
    HuffManTree a[max];
    int n;
    cin>>n;
    Input(a,n);
    HuffCode(a,n);
    Output(a,n);
    return 0;
}