哈夫曼树

#include<iostream>
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;
}