第1关：建立一棵哈夫曼树

任务描述
相关知识
哈夫曼树的概念
哈夫曼树的物理结构
哈夫曼树的构造算法
编程要求
测试说明
任务描述
本关任务：给定n个结点的权值，以它们为叶子结点创建一棵哈夫曼树。

相关知识
哈夫曼树的概念
哈夫曼树是一个最优二叉树。它有以下特点：

它有n个叶子结点，n-1个内结点，因此一共有2n-1个结点，从而有2n-2条边，并且每个内结点都有2个孩子结点。
每个叶子结点i有一个权值w 
i
​
 ，有一个到根结点的路径长度l 
i
​
 , 则带权路径长度WPL=∑ 
i=1
n
​
 w 
i
​
 ∗l 
i
​
  在所有满足条件1的树中，达到最小。

图1  权值为（1，2，3，4，5）的哈夫曼曼树及哈夫曼编码

由于huffman树的最优性，所以它在通信编码中有重要应用。假设每个内结点往左的边上标记为1，往右标记为0，则从根到每个叶子结点形成了一个二进制编码。如图1中A点的二进制编码为11，B点为101。如果权值是该编码出现的概率，则WPL就是编码的平均长度。根据huffman树的最优性，使用huffman编码，将具有最高的通信效率。

n个叶子结点的哈夫曼树可以定义为 bnode HT[2*n]; 比较方便的存储方法是n个叶子结点存在HT数组的前n个位置，n-1个内结点存在后部。

哈夫曼树的构造算法
构造时，规定每个结点都有权值，叶子结点的权值为输入时给定，内结点的权值为两个孩子结点的权和。
第一步：建立n个叶子结点，每个叶子结点看作一个单节点的树。
第二步，在当前所有的树中，选择两个根结点权值最小的树，建立一个新的内结点，让这两个树分别作为左右孩子，新的内结点的权值为左右孩子的权和。 这是一个合并两个树的操作，因此树的总数会少减少1。
第三步：如果当前的树的总数为1，则已经构造完成。否则重复第二步。

编程要求
根据提示，在右侧编辑器补充代码，构造一个哈夫曼树。

你要写的代码是第二步中，选择两个权值最小的树，记录其在HT表中位置的子程序
void SelectTwoMin(bnode HT[],int len, int &min1, int &min2）

测试说明
平台将检查你构造的树的WPL值。
先输入叶子结点个数n, 再输入n个权值。

测试输入：5  1 2 3 4 5
预期输出：33.00

开始你的任务吧，祝你成功！

#include "HuffmanTree.h"
#include <string.h>
#include <stdio.h>
int CreateHuffman(bnode HT[], double w[], int n){
	int i,min1,min2;
	double sum;
	
    for (i=0;i<n;i++) {   //建立n个单结点的树
		HT[i].lchild=-1;
	    HT[i].rchild=-1;
	    HT[i].parent=-1;    // parent=-1表示是树根
	    HT[i].weight=w[i];
	    HT[i].pos=i;	    
    } 
	for (i=n;i<2*n;i++){
		SelectTwoMin(HT, i, min1, min2);   //选择树根权值最小的两棵树
	    HT[min1].parent=i;	    
	    HT[min2].parent=i;	    
	    HT[i].lchild=min1;
		HT[i].rchild=min2;
		HT[i].parent=-1;
		HT[i].weight=   HT[min1].weight+ HT[min2].weight;
		HT[i].pos=i;    }
}

void SelectTwoMin(bnode HT[],int len, int &min1, int &min2){
// 在HT数组中，在前面的len个元素中寻找两个权值最小的根结点的位置，给min1和min2赋值
// begin


int i;
int minnum = 0;
for (int i = 0; i < len; i++)
{
	if (HT[i].parent == -1)
	{
		minnum = i;
		break;
	}
}
for (int i = 1; i < len; i++)
{
	if (HT[i].parent == -1)
	{
		if (HT[i].weight < HT[minnum].weight)
			minnum = i;
	}
}
min1 = minnum;
minnum = 0;
for (int i = 1; i < len; i++)
{
	if (HT[i].parent == -1 && i != min1)
	{
		minnum = i;
		break;
	}
}

for (int i = 1; i < len; i++)
{
	if (i != min1 && HT[i].parent == -1)
	{
		if (HT[i].weight < HT[minnum].weight)
			minnum = i;
	}
}
min2 = minnum;
            


//end
} 

void FillLength(bnode HT[], int root, int h_root){  //填写一个树上各结点的路径长度 
	HT[root].length=h_root;
	if (HT[root].lchild!=-1) FillLength(HT, HT[root].lchild,h_root+1);
	if (HT[root].rchild!=-1) FillLength(HT, HT[root].rchild,h_root+1);
    return;
} 
double WPL(bnode HT[],int n){	
	double L=0;
	int i;
	
	FillLength(HT,2*n-2, 0);  //计算结点的路径长度
    for (i=0;i<n;i++)
    	L+=HT[i].weight*HT[i].length;
    return L;
}