深夜爆肝：万字长文3种语言实现Huffman树（强烈建议三连）

一、C语言能干大事

1. C语言下Huffman树的计算过程分析

例1 有权重集合分别是：5、29、7、8、14、23、3、11，计算Huffman树。

这个题目的计算过程如下：

（1）首先是把数据填写在以下表格里：

这个在编程中一定注意：空白格子里是NULL，这点不要搞错。

首先是寻找到两个最小权重的结点，找到的是第7、1号结点，权重合计是8，我们先标记这两个结点s=1(代表已经处理过了)，并生成第9号结点，权重是8，并让第7、1号结点的父结点是9，第9号结点的左、右孩子分别是第7、1结点，就是如下表：

重复上面的过程，从头寻找s=0的结点里、权重最小的两个结点、就是第3、4号结点，权重合计是15，这样，标记这两个结点s=1，并生成第10号结点，权重是15，而第7、8的父结点是第10号结点，第10号结点的左右孩子是第3、4号结点，就是下表：

重复这个过程，处理到第15个结点，使其权重合计为100，就是：

最终这个树的计算到此结束，在这样的表中计算出的过程以及结果，就是我们下面编程的主要依据。

2. C语言下Huffman树的编程

针对前面介绍的表格，用C语言描述这样的表就是：

struct Huffman 
{
	int W,Parent,lChild,rChild,S;
};

对Huffman树，由于它是正则二叉树，所以有n个权重数据则必然有2*n-1个树结点。

有了表的C语言定义，则首先是寻找未标记的、权重最小的结点，如果这个表是H，则全部代码就是：

int FindMinNode(struct Huffman *H,int N)
{
	int i,W,Node;
	W=100;Node=0;
	if(H==NULL) return -1;
	for(i=0;i0&&H[i].W