哈夫曼树

#include<stdio.h>


#define N 100
#define HUGE 100
//定义哈夫曼树的结点类型
typedef struct hnode {
	int weight;  //权值
	int parent;	//双亲
	int lchild;	//左孩子
	int rchild; //右孩子
}hnode;

hnode h[N];		//存放所有节点
int w[N] = { 0 };		//存放权值

//输入叶子结点的个数和权值
int n, m;
void input() {
	printf("请输入叶子的个数:");
	scanf("%d", &m);
	printf("请输入%d个叶子结点的权值:", m);
	for (int i = 0; i < m; i++)
		scanf("%d", &w[i]);
	n = 2 * m - 1;		//所有节点的个数
}

//初始化,说明
void init() {
	for (int i = 0; i < n; i++)
	{
		h[i].weight = w[i];
		h[i].parent = -1;
		h[i].lchild = -1;
		h[i].rchild = -1;
	}
}

int minmun() {
	int min, k;
	min = w[0];
	k = 0;
	for (int i = 0; i < n; i++)
		if (w[i] < min && w[i] != 0)
		{
			min = w[i];
			k = i;
		}
	w[k] = HUGE;		//把挑走的值改掉,防止重复挑选
	return k;
}

void creat() {
	int l, r;//最小值下标
	

	for (int i = m; i < n; i++)
	{
		l = minmun();
		r = minmun();
		h[i].lchild = l;
		h[i].rchild = r;
		h[i].weight = h[l].weight + h[r].weight;
		h[l].parent = i;
		h[r].parent = i;
		w[i] = h[i].weight;
	}

}

void output() {
	for (int i = 0; i < n; i++)
		printf("%5d%5d%5d%5d%5d\n", i, h[i].weight, h[i].parent, h[i].lchild, h[i].rchild);
}

void main()
{
	input();
	init();
	creat();
	printf("  下标  权值  双亲  左孩子  右孩子\n");
	printf("-----------------------------------------\n");
	output();
}