[数据结构与算法]哈夫曼树C++

哈夫曼树也叫最优二叉树，也是搜索二叉树，也是完全二叉树，最优二叉树也就是WPL值最小，二叉搜索树满足权值左边小右边大的规则。
要笔记的可以私信下面直接讲解代码
首先 老规矩写个结构体！
思路：
1.录入结点，并且录入结点权值 所以定义一个字符类型和int weight
2.哈夫曼树是通过两个最小值组合称为双亲结点然后再构成一棵二叉树
所以会有双亲结点跟左右结点并且为 int类型。
在这里说明一下为什么是int 类型的左右结点还有parent结点，因为由**左结点最小值+右结点最小值=新的父节点值

typedef struct HuffmanTree
{
	char data;//结点数据
	int weight;//权值
	int parent;
	int lchild;
	int rchild;
}HuffNode, * HuffTree;

这里有了结构体，那老思路，我们先初始化一下，这个我放到create函数里初始化出了点问题，所以我后面直接把初始化扔到main函数里实现 也就是把
下面代码给放到了main函数里一会看函数具体实现

HuffTree T = new HuffNode[2 * sum];//初始化，sum要输入的结点个数

那么我们直接构造哈夫曼树！
思路！：
1.首先如果我们输入的输入的结点个数大于等于1的话直接退出，因为后面有个select（）函数操作，这里是进行n-1次找最小值合并的

2.然后我们把每个结点初始值说一下，这个操作还是重要的后面会用到~！

3.归并,这里有个主要的操作那就是select（）函数去找最小值
然后找到了最小值把两个最小值合并为新的权值
记住！虽然两个都是手动输入的权值里的最小值！但是！合并的时候依然得满足左边小右边大！不然这不是二叉搜索树！

void CreatHufftree(HuffTree& T, int n)
{
	int s1, s2;//通过select（）把这两个值赋值给左右结点.
	int i;
	if (n <= 1)
	{
		cout << "您输入的结点个数有误请输入的结点个数大于1" << endl;
		return;
	}
	//首先！初始化！
	//T = new HuffNode[2*n]; 这里出了点问题所以后面给放main函数里了
	for (i = 0; i <= 2 * n; i++)
	{
		//T[i].weight = 0;
		T[i].parent = -1;
		T[i].lchild = -1;
		T[i].rchild = -1;
	}


	//进行归并
	for (i = n ; i < 2 * n-1; i++)//进行n-1次的结合 //最后一个位置为2n-1 
	{
		Select(T, i , s1, s2);//权值最小的两个结点归并成一个父结点
		T[i].weight = T[s1].weight + T[s2].weight;//合并成新的权值
		T[s1].parent = i;//更新父结点
		T[s2].parent = i;
		T[i].lchild = s1;
		T[i].rchild = s2;
	}
}

重点来了！ 这个也搞了我好一段时间，因为思路出了点问题卡了一两天挺尴尬的
那就是我前面一直念叨的Select() 操作！
Select()操作！
思路！：
1.这里一定要让i1，i2是引用的操作！ 因为接下来要修改地址内部的值所以用引用当然你也可以用指针！
在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；.
2.将二叉树i1、i2合并为一棵新的二叉树k；
3.当遍历的时候如果父结点一直为初始值也就是-1直接退出
4.这里有个比较重要的条件，就是i1不能等于i2 不然会出现二义性。

void Select(HuffTree &T, int k, int& i1, int& i2) {
	/*选择根结点权值最小的两个结点。*/ 
	int i, j;
	for (i = 0; i < k; i++)
		if (T[i].parent == -1)
		 {
		  	i1 = i; 
		  	break;
		 }
	for (j = i + 1; j < k; j++)//因为进行n-1次 所以从i-1开始
		if (T[j].parent == -1)
		 { 
		 	i2 = j; 
		 	break;
		  }
	for (i = 0; i < k; i++)
		if ((T[i].parent == -1) && (T[i].weight < T[i1].weight) && (i2 != i))
		{
			i1 = i;
		}
	for (j = 0; j < k; j++)
		if ((T[j].parent == -1) && (T[j].weight < T[i2].weight) && (i1 != j))
		{
			i2 = j;
		}
}

那构造成功了后都想看一下成效 那们就来看看吧
打印操作
思路！：
1.首先！如果树为空那就是空嘛 直接退出
2.这遍历直接到叶结点个数的 叶结点也就是2结点个数-1 也就是2n-1；

void Print_Huff_Tree(HuffTree& T, int n)
{
	if (T == NULL)
	{
		cout << "这是个空树没有数据！" << endl;
		return;
	}
	cout << "结点 " << "权值 " << "双亲结点 " << "左孩子 " << "右孩子\n";
	for (int i = 0; i < 2 * n-1; i++)
	{
		cout << T[i].data << '\t' << T[i].weight << '\t' << T[i].parent << '\t' << T[i].lchild << '\t' << T[i].rchild << endl;
	}
}

构造哈弗曼编码
这个还是挺简单，只要遇到左边的结点就为‘0’ 右边就为‘1’；
思路！：
在说思路之前先提一嘴，编码的时候是从叶结点向上回溯的 所以这点一定要注意！
1.首先 有个临时数组来存编码也就有了string类型来存
2.设定一个哨兵记录一下当前位置
3.只要父结点不为-1 也就是不碰到结束符，因为根结点没有父结点嘛我们就一直向上回溯，当当前结点跟左子数位置相等我们就让临时数组加一个字符0
如果碰到右子树就加一个字符1 记住加的是字符不是做加法！
然后每次更新父结点就行了

void  HuffmanCode(HuffTree& T, string huffmanCode[], int n) {
	//设置一个临时存储空间
	int cur;
	int parent;
	//遍历哈夫曼树，生成哈夫曼编码
	for (int i = 0; i < n; i++) {
		cur = i;//记录当前处理位置
		parent = T[i].parent;//找到当前结点的父节点
		while (parent != -1) {//父节点不等于-1指的就是当前
			if (T[parent].lchild == cur)
				huffmanCode[i] = '0' + huffmanCode[i];//当前为左子树则编码0
				//huffmanCode[i] += '0';
			else
				huffmanCode[i] = '1' + huffmanCode[i];
			//huffmanCode += '1';
		//改变当前结点与父节点位置向上上搜索 
			cur = parent;
			parent = T[parent].parent;
		}
	}
}

来了 具体实现！直接上代码啦

#include<iostream>
#include<string>
using namespace std;
typedef struct HuffmanTree
{
	char data;//结点数据
	int weight;//权值
	int parent;
	int lchild;
	int rchild;
}HuffNode, * HuffTree;
void Select(HuffTree &T, int k, int& i1, int& i2) {
	/*选择根结点权值最小的两个结点。*/
	int i, j;
	for (i = 0; i < k; i++)
		if (T[i].parent == -1) { i1 = i; break; }
	for (j = i + 1; j < k; j++)
		if (T[j].parent == -1) { i2 = j; break; }
	for (i = 0; i < k; i++)
		if ((T[i].parent == -1) && (T[i].weight < T[i1].weight) && (i2 != i))
		{
			i1 = i;
		}
	for (j = 0; j < k; j++)
		if ((T[j].parent == -1) && (T[j].weight < T[i2].weight) && (i1 != j))
		{
			i2 = j;
		}
}


void CreatHufftree(HuffTree& T, int n)
{
	int s1, s2;
	int i;
	if (n <= 1)
	{
		cout << "您输入的结点个数有误请输入的结点个数大于1" << endl;
		return;
	}
	//首先！初始化！
	//T = new HuffNode[2*n];
	for (i = 0; i <= 2 * n; i++)
	{
		//T[i].weight = 0;
		T[i].parent = -1;
		T[i].lchild = -1;
		T[i].rchild = -1;
	}


	//进行归并
	for (i = n ; i < 2 * n-1; i++)//进行n-1次的结合 //最后一个位置为2n-1 
	{
		Select(T, i , s1, s2);//权值最小的两个结点归并成一个父结点
		T[i].weight = T[s1].weight + T[s2].weight;
		T[s1].parent = i;
		T[s2].parent = i;
		T[i].lchild = s1;
		T[i].rchild = s2;
	}
}

void Print_Huff_Tree(HuffTree& T, int n)
{
	if (T == NULL)
	{
		cout << "这是个空树没有数据！" << endl;
		return;
	}
	cout << "结点 " << "权值 " << "双亲结点 " << "左孩子 " << "右孩子\n";
	for (int i = 0; i < 2 * n-1; i++)
	{
		cout << T[i].data << '\t' << T[i].weight << '\t' << T[i].parent << '\t' << T[i].lchild << '\t' << T[i].rchild << endl;
	}
}

void  HuffmanCode(HuffTree& T, string huffmanCode[], int n) {
	//设置一个临时存储空间
	int cur;
	int parent;
	//遍历哈夫曼树，生成哈夫曼编码
	for (int i = 0; i < n; i++) {
		cur = i;//记录当前处理位置
		parent = T[i].parent;//找到当前结点的父节点
		while (parent != -1) {//父节点不等于-1指的就是当前
			if (T[parent].lchild == cur)
				huffmanCode[i] = '0' + huffmanCode[i];//当前为左子树则编码0
				//huffmanCode[i] += '0';
			else
				huffmanCode[i] = '1' + huffmanCode[i];
			//huffmanCode += '1';
		//改变当前结点与父节点位置向上上搜索 
			cur = parent;
			parent = T[parent].parent;
		}
	}

}

int main()
{
	string huffmanCode[6];//设立一个临时数组存哈弗曼编码，给的空间要大
	cout << "请输入您要输入的结点个数：";
	int sum;
	cin >> sum;
	HuffTree T = new HuffNode[2 * sum];
	//录入数据！
	for (int i = 0; i < sum; i++)
	{
		cout << "请输入第" << i+1 << "个字符:";
		cin >> T[i].data;
		cout << "请输入第" << i+1 << "个结点的权值：";
		cin >> T[i].weight;
	}
	CreatHufftree(T, sum);
	Print_Huff_Tree(T, sum);
	cout << "哈夫曼编码为：" << endl;
	HuffmanCode(T, huffmanCode, sum);
	for (int i = 0; i < sum; i++)
	{
		cout << "结点" << T[i].data << ":" << huffmanCode[i] << endl;
	}
	return 0;
}