/*
 哈夫曼树（最优二叉树）
 */
#include <iostream>
#include <string>
using namespace std;
struct Node
{
    int weight;
    int parent,lchild,rchild;
};
class HuffmanTree
{
private:
    Node *hufftree;
    int num;
    void Select(int n,int &i1,int &i2);
public:
    HuffmanTree(){};
    HuffmanTree(int a[],int n);
    void Print();
};
void HuffmanTree::Select(int n,int &i1,int &i2)
{
    int i=0,temp;
    for(;i<n;i++)
    {
        if(hufftree[i].parent==-1){i1=i;break;}
    }
    for (i=i+1;i<n; i++)
    {
        if(hufftree[i].parent==-1){i2=i;break;}
    }
    if(hufftree[i1].weight>hufftree[i2].weight)
    {
        temp=i1;
        i1=i2;
        i2=temp;
    }
    for(i=i+1;i<n;i++)
    {
        if(hufftree[i].parent==-1)
        {
            if(hufftree[i].weight<hufftree[i1].weight)
            {
                i2=i1;
                i1=i;
            }
            else if(hufftree[i].weight<hufftree[i2].weight)
            {
                i2=i;
            }
        }
    }
}
HuffmanTree::HuffmanTree(int a[],int n)
{
    int i,k,i1,i2;
    hufftree=new Node[2*n-1];
    num=n;
    for(i=0;i<2*num-1;i++)
    {
        hufftree[i].parent=-1;
        hufftree[i].lchild=hufftree[i].rchild=-1;
    }
    for(i=0;i<num;i++)
    {
        hufftree[i].weight=a[i];
    }
    for(k=num;k<2*num-1;k++)
    {
        Select(k, i1, i2);
        hufftree[k].weight=hufftree[i1].weight+hufftree[i2].weight;
        hufftree[k].lchild=i1;
        hufftree[k].rchild=i2;
        hufftree[i1].parent=k;
        hufftree[i2].parent=k;
    }
}
void HuffmanTree::Print()
{
    int i,k;
    cout<<"每个叶子到根结点的路径为："<<endl;
    for(i=0;i<num;i++)
    {
        cout<<hufftree[i].weight;
        k=hufftree[i].parent;
        while (k!=-1)
        {
            cout<<"-->"<<hufftree[k].weight;
            k=hufftree[k].parent;
        }
        cout<<endl;
    }
}
int main()
{
    int a[5]={2,3,4,5,7};
    HuffmanTree tree(a,5);
    tree.Print();
}