哈夫曼树建立

#include <stdio.h>
#define  MAXVALUE  10000              /*定义最大权值*/
#define  MAXLEAF  30                      /*定义哈夫曼树中叶子结点个数*/
#define  MAXNODE  60                      /*定义哈夫曼树的结点数*/
#define  MAXBIT  10                        /*定义哈夫曼编码的最大长度*/

/*哈夫曼编码结构*/
typedef  struct {
	int  bit[MAXBIT];
	int  start;
}
HCodeType;

/*哈夫曼树结点结构*/
typedef  struct {
	char  data;
	int  weight;
	int  parent;
	int  lchild;
	int  rchild;
}
HNodeType;
/*哈夫曼树的构造算法*/
void    HuffmanTree(HNodeType  HuffNode[], int  n);
/*生成哈夫曼编码*/
void    HuffmanCode(HNodeType  HuffNode[], HCodeType  HuffCode[], int  n);

void    HuffmanTree(HNodeType  HuffNode[], int  n) {
	int i, j, m1, m2, x1, x2;
	for (i = 0; i < n - 1; i++) {
		m1 = m2 = MAXVALUE;
		x1 = x2 = 0;
		for (j = 0; j < n + i; j++) {
			if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1) {
				m2 = m1;
				x2 = x1;
				m1 = HuffNode[j].weight;
				x1 = j;
			} else if (HuffNode[j].weight < m2 &&
			           HuffNode[j].parent  == -1) {
				m2 = HuffNode[j].weight;
				x2 = j;
			}
		}
		HuffNode[x1].parent = n + i;
		HuffNode[x2].parent = n + i;
		HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
		HuffNode[n + i].lchild = x1;
		HuffNode[n + i].rchild = x2;
	}

}

void  HuffmanCode(HNodeType  HuffNode[], HCodeType  HuffCode[], int  n) {
	HCodeType cd;
	int i, j, c, p;
	for (i = 0; i < n; i++) {
		cd.start = n - 1;
		c = i;
		p = HuffNode[i].parent;
		while (p != -1) {
			if (HuffNode[p].lchild == c)
				cd.bit[cd.start] = 0;
			else
				cd.bit[cd.start] = 1;
			cd.start--;
			c = p;
			p = HuffNode[p].parent;
		}
		for (j = cd.start + 1; j < n; j++)
			HuffCode[i].bit[j] = cd.bit[j];
		HuffCode[i].start = cd.start;
	}

}

int  main() {
	HNodeType  HuffNode[MAXNODE];
	HCodeType  HuffCode[MAXLEAF];
	int  n, i, j;
	scanf("%d", &n);
	getchar();
	/*数组HuffNode[  ]初始化*/
	for  (i = 0;  i < 2 * n - 1;  i++) {
		HuffNode[i].data = '0';
		HuffNode[i].weight = 0;
		HuffNode[i].parent = -1;
		HuffNode[i].lchild = -1;
		HuffNode[i].rchild = -1;
	}
	/*输入n个叶子结点的权值*/
	for  (i = 0;  i < n;  i++) {
		scanf("%c,%d", &HuffNode[i].data, &HuffNode[i].weight);
		getchar();
	}
	HuffmanTree(HuffNode, n);
	printf("HuffTable:\n");
	for (i = 0;  i < 2 * n - 1;  i++) {
		putchar(HuffNode[i].data);
		printf("  %d", HuffNode[i].weight);
		printf("  %d", HuffNode[i].parent);
		printf("  %d", HuffNode[i].lchild);
		printf("  %d", HuffNode[i].rchild);
		printf("\n");
	}
	printf("HuffCode:\n");
	HuffmanCode(HuffNode, HuffCode, n);
	/*输出每个叶子结点的哈夫曼编码*/
	for  (i = 0;  i < n;  i++) {
		printf("%c:", HuffNode[i].data);
		for (j = HuffCode[i].start + 1;  j < n;  j++)
			printf("%d", HuffCode[i].bit[j]);
		printf("\n");
	}
	return  0;
}