#include<stdio.h>
#define n 10
#define m n * 2 - 1
typedef struct
{
    int weight;
    int lchild, rchild, parent;
}HTNode;
typedef HTNode HuffmanTree[m];
HuffmanTree t;

void IniHuffumanTree(HuffmanTree t)//初始化每个元素 
{
    int i;
    for (i = 0; i < m; i++)
    {
        t[i].weight = 0;
        t[i].lchild = t[i].rchild = t[i].parent = -1;
    }
}

void InputWeight(HuffmanTree t)//输入每个结点（树）的权值 
{
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &t[i].weight);
    }
}
void SelectMin(HuffmanTree t, int i, int *p1, int *p2)//在森林中找出两个权最小的树 
{
    int j;
    int min1, min2;
    min1 = min2 = -1;
    for (j = 0; j <= i; j++)
    {
        if (t[j].parent == -1)//表示无双亲的结点 
        {
            if (t[j].weight < min1 || min1 == -1)
            {
                if (min1 != -1)//因为t[j].weight < min1，又min2 > min1，故将min1的相关数据赋给min2 
                {
                    *p2 = *p1;
                    min2 = min1;
                }
                *p1 = j;
                min1 = t[j].weight;
            }
            else if (t[j].weight < min2 || min2 == -1) 
            {
                *p2 = j;
                min2 = t[j].weight;
            }
        }
    }
}
void CreateHuffmanTree(HuffmanTree t)//创建哈夫曼树 
{
    int i, p1, p2;
    IniHuffumanTree(t);
    InputWeight(t);
    for (i = n; i < m; i++)
    {
        SelectMin(t, i - 1, &p1, &p2);
        t[p1].parent = t[p2].parent = i;
        t[i].lchild = p1;
        t[i].rchild = p2;
        t[i].weight = t[p1].weight + t[p2].weight;
    }
}
void Preorder(HuffmanTree t, int j)//对哈夫曼树的前序遍历 
{
    int i = -1, h, stack[50];
    stack[++i] = h = j;
    while (h != -1)
    {
        h = stack[i--];
        printf("%d ", t[h].weight);
        if (t[h].rchild != -1)
        {
            stack[++i] = t[h].rchild;
        }
        if (t[h].lchild != -1)
        {
            stack[++i] = t[h].lchild;
        }
        if (i == -1)
        {
            return;
        }
    }
} 

int main()
{
    int i;
    CreateHuffmanTree(t);
    for (i = 0; i < m; i++)
    {
        printf("%d ", t[i].weight);
    }
    printf("\n");
    Preorder(t, m - 1);
    system("pause");
    return 0;
}        
/*测试数据 
1 2 3 4 5 6 7 8 9 10