C语言：详解哈夫曼树（赫夫曼树、最优树）

哈夫曼树的定义

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

结点的权（权重）：给每一个结点赋予一个数值，被称为这个结点的权（权重）。

结点的路径长度：从根节点到该节点路径上的连接数。

树的路径长度：树中每个叶子节点的路径长度之和。

结点带权路径长度：结点的路径长度与结点的权值的乘积。

树的带权路径长度（WPL）：所有叶子节点带权路径长度之和。

如上图：a结点的权重是7；b结点的路径长度是2；c结点的带权路径长度是3*2=6；树的路径长度是6；树的带权路径长度是1*7+2*5+3*2+3*4=35。

WPL的值越小，构造出来的二叉树性能越优。当WPL值最小的时候，我们称这棵二叉树为哈夫曼树（赫夫曼树、最优树）。

创建出一棵哈夫曼树（图解）

我们现在有一组数字：

首先，找出这组数字的两个最小值：2，4。将他们作为叶子节点：

注意，这时候数字6也放入剩余的数组中作比较，接着重复第一步，找两个最小值：5，6：

因为只剩下7和11了，将他们结合一下：

创建出一棵哈夫曼树（代码）

我们用顺序表来创建一棵哈夫曼树：1，2，3，4

用上面4个元素构建一棵哈夫曼树，因为每次都是比较两个元素来创建出一个父元素放入元素组中，所以构建出来的哈夫曼树有7个结点。大家可以动手画一画！

所以，用n个元素构建一棵哈夫曼树，总共的结点为2n-1个。我们不妨先创建一个存放结点结构体数组：结点的结构体如下：

typedef struct hftree{
	int data;
	int lchild;
	int rchild;
	int parent;
}treeNode;

每个结点的结构体除了存放一个数据，还有左子结点的标识，用来记录左子结点在数组中的位置；右子结点的标识，用来记录右子结点在数组中的位置；父亲标识，用来记录父结点（双亲结点）在数组中的位置。

我们再创建一个存放结构体数组的结构体，pointer指向的是新建的结构体数组，length是要排序的元素个数 4（不是创建数组的长度）：

typedef struct base{
	int length;
	treeNode * pointer;
}hfNode;

接下里我们可以初始化结构体了：

hfNode * init(int arr[],int length){
	int i;
	hfNode * T=(hfNode *)malloc(sizeof(hfNode));
	T->length=length;
	T->pointer=(treeNode *)malloc(sizeof(treeNode)*(2*length-1));
	for(i=0;ipointer[i].data=arr[i];
		T->pointer[i].lchild=T->pointer[i].rchild=-1;
		T->pointer[i].parent=0;
	}
	return T;
}

每次从数组中找到两个最小值并返回最小值下标的函数：

int * selectMin(hfNode * p){
	int i;
    int secondMinIndex;
	int minIndex;
	int min=10000;
	int secondMin=10000;
	
	int * temp=NULL;
	for(i=0;ilength;i++){
		if(p->pointer[i].parent==0){
			if(p->pointer[i].datapointer[i].data;
				minIndex=i;
			}
		}
	}
	for(i=0;ilength;i++){
		if(p->pointer[i].parent==0 && i!=minIndex){
			if(p->pointer[i].datapointer[i].data;
				secondMinIndex=i;
			}
		}
	}
	temp=(int *)malloc(sizeof(int)*2);
	temp[0]=minIndex;
	temp[1]=secondMinIndex;
	return temp;
}

最后，我们就可以遍历填充数组中空白的元素啦：

void creatTree(hfNode * p){
	int i;
	int * temp=NULL;
	int minIndex;
	int secondMinIndex;
	int length=2*p->length-1;
	for(i=p->length;ipointer[i].data=p->pointer[minIndex].data+p->pointer[secondMinIndex].data;
		p->pointer[minIndex].parent=i;
		p->pointer[secondMinIndex].parent=i;
		p->pointer[i].parent=0;
		p->pointer[i].lchild=minIndex;
		p->pointer[i].rchild=secondMinIndex;
		p->length++;
	}
}

根据代码创建的数组长这样：

创建好的哈夫曼树结合数组其实是长这样的：

我们用前序遍历从数组最后一个元素递归遍历这棵哈夫曼树，先输出值，再访问左子节点，最后访问右子结点：

void preOrder(hfNode * p,int index){
	if(index==-1){
		return;
	}
	printf("%d\t",p->pointer[index].data);
	preOrder(p,p->pointer[index].lchild);
	preOrder(p,p->pointer[index].rchild);
}
void main(){
	int arr[4]={1,2,3,4};
	hfNode * T=init(arr,4);
	creatTree(T);
	preOrder(T,T->length-1);
	system("pause");
}

---

好啦，哈夫曼树就讲完啦，只要大家静下心来跟着敲代码，就一定能懂哒~

如文章有任何的错误和不足，欢迎大家积极纠正！期待下次和你见面！