本文共 2546 字，大约阅读时间需要 8 分钟。

哈夫曼树

1.相关概念

2.哈夫曼树的特点

为了让带权路径长度计算值最小

3，哈夫曼树的基本思想

#include
   
    using namespace std;//哈夫曼树----静态链表方式存储struct HtnNode {
   	int weight;// 权值	int lchild, rchild, parent;}*Node;//存放哈夫曼树的静态链表的构建和用户输入权值void creatNode(HtnNode*& node,int w[]){
   	int num = 0;	cout << "请输入节点的个数：" << endl;	cin >> num;	node = new HtnNode[2 * num - 1];//在堆区创建一个大小为2*num -1长度的汉夫曼静态链表数组	cout << "数组长度为：" << num << endl;	cout << "请输入4个权值：" << endl;	for (int i = 0; i < 4; i++)		cin >> w[i];}//寻找parent为-1的最小的和最次小的节点//哈夫曼静态链表的树的数组  当前进行构建的节点下标  权值最小的节点下标 权值最次小的节点下标void select(HtnNode*& node,int k,int& i1,int& i2){
   	int min=0;	//找到哈夫曼树中权值最小和最次小的节点的静态链表数组下标	for (int i = 0; i < k; i++)	{
   		//找到第一个parent值为-1的节点，假设该节点权值最小		if (node[i].parent == -1)		{
   		  min = i; //假设数组中第i个节点权值最小		  break;		}	}	for (int i = 1; i < k; i++)	{
   		if (node[i].parent == -1)		{
   			//如果当前节点的权值小于node[min]节点的权值，就把i的值赋值给min			if (node[i].weight < node[min].weight)				min = i;		}	}	//此时min的值为权值最小的节点在静态链表中的下标	//再次对数组进行遍历操作，但是把下标为min的元素排除在比较范围里面	int lessmin=0;	for (int i = 0; i < k; i++)	{
   		if (i != min)		{
   			if (node[i].parent == -1)			{
   				lessmin = i;				break;			}		}	}	for (int i = 0; i < k; i++)	{
   		if (node[i].parent == -1)		{
   			if (i != min)			{
   				if (node[i].weight < node[lessmin].weight)				{
   					lessmin = i;								}			}		}	}     	i1 = min;//将min赋值给i1,表明i1得到的是权值最小的节点下标	i2 = lessmin;//将lessmin赋值给i2,表明i2得到的是权值次小的节点下标	cout << "最小的节点下标为：" << min << "   次小的节点下标为：" << lessmin << endl;}//哈夫曼树的构建:静态链表数组， 存放权值的数组，节点的个数void HuffMan(HtnNode*& node, int w[], int n){
   	//1.初始化所有节点的项目为-1	for (int i = 0; i < 2*n-1; i++)	{
   		node[i].weight = -1;		node[i].parent = -1;//-1表示没有双亲		node[i].lchild = -1;		node[i].rchild = -1;	}	//2.初始化前n个节点的权值	for (int i = 0; i < n; i++)		node[i].weight = w[i];	//3.构建哈夫曼树	int i1=0, i2=0;	for (int k = n; k< 2 * n - 1; k++)	{
   		//先找到parent为-1的最小的和次小的节点		select(node, k, i1, i2);//parent要为-1才可以进行权值的大小比较		node[k].weight = node[i1].weight + node[i2].weight;		node[k].lchild = i1;		node[k].rchild = i2;		node[i1].parent = k;		node[i2].parent = k;	}}//打印构建好的哈夫曼树的数组内容void display(HtnNode *& node,int n){
   	//遍历哈夫曼树	cout << "weight  parent  lchild  rchild" << endl;	for (int i = 0; i < 2 * n - 1; i++)	{
   		cout << node[i].weight << "     \t" << node[i].parent << "     \t" << node[i].lchild << "     \t" << node[i].rchild << endl;	}}int main(){
   	HtnNode* node = NULL;	int w[4];	creatNode(node, w);	HuffMan(node, w, 4);	display(node, 4);	system("pause");	return 0;}
   

转载地址：http://fwzc.baihongyu.com/