Huffman树的先序构建以及Huffman编码

#include
#define N 8                                        //叶子结点数目
#define M (2*N-1)                                  //总结点数目，可证明
#define MAXVALUE 10000                             //最大权值
#define MAXBIT 20                                  //哈夫曼编码最大长度

typedef struct
{
	char ch;                                       //编号所代表的数据域
	int weight;                                    //权值
	int parent;                                    //双亲结点
	int Lchild, Rchild;                            //左右孩子结点
}Htreetype;

typedef struct
{
	int bit[N];                                    //位串，01编号
	int start;                                     //编码在位串中的起始位置
	char ch;
}Hcodetype;

//选择权值最小的结点

void select(Htreetype t[], int k, int* p1, int* p2) //使用p1,p2将权值最小的两个字符的下标传递回来，作为左右孩子
{
	*p1 = *p2 = 0;
	int min1, min2;           //min1，min2将最小的两个权值传递至weight中
	min1 = min2 = MAXVALUE;
	int i;
	for (i = 0; i < k; i++)
	{
		if (t[i].parent == -1)
		{
			if (t[i].weight < min1)   //传递第一个权值最小的
			{
				min2 = min1;
				min1 = t[i].weight;
				*p2 = *p1;
				*p1 = i;
			}
			else if (t[i].weight < min2) //传递第二个权值最小的
			{
				min2 = t[i].weight;
				*p2 = i;
			}
		}
	}
}

//构造哈夫曼树
void HuffmanTree(Htreetype t[])
{
	int i, j, p1, p2, f;
	p1 = p2 = 0;
	char c;
	for (i = 0; i < M; i++)                            //初始化，空树
	{
		t[i].weight = 0;
		t[i].Lchild = -1;
		t[i].parent = -1;
		t[i].Rchild = -1;
	}
	printf("共有%d个字符\n", N);
	for (i = 0; i < N; i++)                            //输入字符和对应的权值
	{
		printf("请输入第%d个字符和权值以逗号分隔：", i + 1);
		scanf_s("%c,%d", &c, &f);
		getchar();
		t[i].ch = c;
		t[i].weight = f;
	}
	for (i = N; i < M; i++)                            //构造哈夫曼树
	{
		select(t, i, &p1, &p2);                        //调用select方法，选择权值最小的两个作为左右孩子
		t[p1].parent = i;
		t[p2].parent = i;
		t[i].Lchild = p1;
		t[i].Rchild = p2;
		t[i].weight = t[p1].weight + t[p2].weight;     //新结点为权值最小的两个结点的双亲
	}
}

//哈夫曼编码
void HuffmanCode(Hcodetype code[], Htreetype t[])
{
	int i, c, p;
	Hcodetype cd;            //缓冲变量，暂时存储
	HuffmanTree(t);
	for (i = 0; i < N; i++)
	{
		cd.start = N;
		cd.ch = t[i].ch;
		c = i;               //从叶子结点向上
		p = t[i].parent;     //t[p]是t[i]的双亲
		while (p != -1)
		{
			cd.start--;
			if (t[p].Lchild == c)
				cd.bit[cd.start] = '0';        //左子树编为0
			else
				cd.bit[cd.start] = '1';        //右子树编为1
			c = p;                             //移动
			p = t[c].parent;
		}
		code[i] = cd;                         //第i+1个字符的编码存入code
	}
}

//输出哈夫曼编码
void show(Htreetype t[], Hcodetype code[])
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		printf("%c: ", code[i].ch);
		for (j = code[i].start; j < N; j++)
			printf("%c ", code[i].bit[j]);
		printf("\n");
	}
}

//调用上述函数
int main()
{
	Htreetype t[M];
	Hcodetype code[N];
	HuffmanCode(code, t);
	show(t, code);
	return 0;
}

具体原理参考《数据结构（C语言）》第二版——人民邮电出版社

                        哈夫曼编码实现（Bilibili-章英老师）——华中农业大学