#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