#include
using namespace std;
typedef struct
{
int weight;
int parent,lch,rch;
}HTNode,*HuffmanTree;
int Select(HuffmanTree HT,int k,int &s1,int &s2)
{
int a, b;
int t,m,q;
for (int i = 1; i <= k; i++)
{
if (HT[i].parent == 0)
{
s1 = i;
t = i;
a = HT[s1].weight;
break;
}
}
t++;
for (; t <= k; t++)
{
if (HT[t].parent == 0)
{
s2 = t;
q = t;
b = HT[s2].weight;
break;
}
}
q++;
if (a > b)
{
m = s2;
s2 = s1;
s1 = m;
}
for (int j = q; j <= k; k++)
{
if (HT[j].parent != 0)
continue;
if (HT[j].weight < HT[s1].weight)
{
s2 = s1;
s1 = j;
}
else if ((HT[j].weightHT[s1].weight))
{
s2 = j;
}
}
return 0;
}
void CreatHuffmanTee(HuffmanTree &HT, int n)
{
int s1, s2;
if (n <= 1) return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for (int i = 1; i <= m; ++i)
{
HT[i].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
}
for (int i = 1; i <= n; ++i)
cin >> HT[i].weight;
for (int i = n + 1; i <= m; ++i)
{
Select(HT, i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lch = s1;
HT[i].rch = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
void printHuffmanTree(HuffmanTree HT,int n)
{
for (int i = 1; i <= 2 * n; i++)
{
cout << HT[i].weight << " " << HT[i].parent << " "
<< HT[i].lch << " " << HT[i].rch << " "<< endl;
}
}
void main()
{
HuffmanTree HT;
int n;
cout << "输入结点数：";
cin >> n;
CreatHuffmanTee(HT,n);
printHuffmanTree(HT,n);
}
