首先小编来介绍一下 Huffman Tree

根据每个结点的权值不同把每个结点放在树的不同层，权值越大，层数越小；

在一个已知的数据中对这组数据进行HuffmanTree 的构建，

1、每次将最小的两个结点取出进行自下而上的顺序构建树，

2、将其权值相加放在数组中，并将这两个结点去除，

3、循环 1、2 步骤，直至只有一个结点，HuffmanTree构建成功

Ps：我这里是默认 从左到右 从小到大的顺序来构建的，顺序无所谓，只是自己在写的时候将构建顺序约定好，方便敲出来

#include<stdio.h>
#include<stdbool.h>
/*
4
9 8 1 5
9 8 1 5 6        9 8 0 0 6			2	3
9 8 0 0 6 14	 9 0 0 0 0 14		1	4
9 0 0 0 0 14 23	 0 0 0 0 0 0  23	0	5

6
9 8 1 5 4 6
*/
typedef struct Node {
	bool flag;		// 用来标记该结点 是否 是有效结点 
	int weight;		// 权值 
	int parent;		// 父节点 
	int leftChild;	// 左孩子 
	int rightChild;	// 右孩子 
}HuffmanTreeNode;

// 初始化 HuffmanTree，将数据放入数组的前 N 个位置 
void initialTree(HuffmanTreeNode [],int,int);
// 打印整个HuffmanTree 数组 
void output(HuffmanTreeNode [],int);
// 输出某一个位置的信息 
void outputOneNode(HuffmanTreeNode);
// 在初始化HuffmanTree的基础上，创建Huffman 
void createHuffmanTree(HuffmanTreeNode [],int,int);
// 挑选有效的HuffmanTree结点中的最小的结点索引 
int  selectMinIndex(HuffmanTreeNode [],int);
// 判断 挑选的两个新的索引 是否是两新的 或是 只有一个是新的 
bool judgeAllNewIndex(int,int,int,int);
// 将结点 聚合成HuffmanTree  
void converge(int,int,int,HuffmanTreeNode []);

int main(void){
	int n;
	scanf("%d",&n);
	HuffmanTreeNode huffmanTree[2*n-1];
	initialTree(huffmanTree,n,2*n-1);
	output(huffmanTree,2*n-1);
	createHuffmanTree(huffmanTree,n,2*n-1);
	output(huffmanTree,2*n-1);
	return 0;
}

void converge(int left,int right,int i,HuffmanTreeNode h[]){
	h[left].parent = i;
	h[left].flag = false;
	h[right].parent = i;
	h[right].flag = false;
	
	h[i].weight = h[left].weight + h[right].weight;
	h[i].leftChild = left;
	h[i].rightChild = right;
}

bool judgeAllNewIndex(int left,int right,int tmpLeft,int tmpRight){
	if(left == tmpLeft){
		return false;
	}
	if(left == tmpRight){
		return false;
	}
	if(right == tmpLeft){
		return false;
	}
	if(right == tmpRight){
		return false;
	}
	return true;
}

int selectMinIndex(HuffmanTreeNode h[],int n){
	int i;
	int index = 0;
	for(i = 0;i < n;i ++){
		if(h[i].flag != false){
			index = i;
			break;
		}
	}
	int min = h[index].weight;
	for(i = index;i < n;i++){
		if(h[i].flag != false){
			if(h[i].weight < min){
				index = i;
				min = h[i].weight;
			}
		}
	}
	h[index].flag = false; // 之前没有写这个，导致每次挑选后索引相同，在下次挑选是这个点应该视为无效结点才对 
	return index;
}

void createHuffmanTree(HuffmanTreeNode h[],int n,int capacity){
	int i;
	int tmpLeft = -1,tmpRight = -1;
	for(i = n;i < capacity;i ++){
		int left = selectMinIndex(h,i);
		int right = selectMinIndex(h,i);
		if(judgeAllNewIndex(left,right,tmpLeft,tmpRight)){
			converge(left,right,i,h);
			tmpLeft = left;
			tmpRight = right;
		}else{
			tmpLeft = left;
			tmpRight = right;
			converge(tmpLeft,tmpRight,i,h);
		}
	}
}

void outputOneNode(HuffmanTreeNode h){
	printf("flag=%d weight=%02d parent=%02d leftChild=%02d rightChild=%02d\n",h.flag,h.weight,h.parent,h.leftChild,h.rightChild);
}

void output(HuffmanTreeNode h[],int n){
	int i;
	for(i = 0;i < n;i ++){
		outputOneNode(h[i]);
	}
	putchar('\n');
}

void initialTree(HuffmanTreeNode h[],int n,int capacity){
	int i;
	for(i = 0;i < n;i ++){
		scanf("%d",&h[i].weight);
		h[i].flag = true;
		h[i].parent = h[i].leftChild = h[i].rightChild = -1;
	}
	for(i = n;i < capacity;i ++){
		h[i].weight = 0;
		h[i].flag = true;
		h[i].parent = h[i].leftChild = h[i].rightChild = -1;
	}
}