构建哈弗曼树 C/C++

标签: # 数据结构

什么是哈弗曼树?

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

权值:树的每个节点数据域data可以放一个特定的数来代表它的值,可以叫做权值。

路径:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。也就是经过的节点。

路径长度:路径通路中分支的数目称为路径长度。也就是边的条数。

带权路径长度:从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度:所有叶子结点的带权路径长度之和,记为WPL。

怎么构建哈弗曼树?

哈弗曼树就是带权路径长度最小的二叉树,那么意味着权重越大的叶子结点离根节点的路径长度越短。

若要将前面那颗二叉树转换成一棵二叉树,应该是这样:

它们同一层的各个节点权重也可以换位置,同样构成哈弗曼树。

构造步骤:

一、根据权重构造节点。创建一个保持升序的队列。

二、将带权重节点压入队列中

三、弹出队首前两个节点,节点的权重是最小和次小。将这两个节点权重相加构成一个新权重,再用新权重构造一个新节点。将新节点作为这两个节点的根节点,构造成一棵二叉树,并将根节点压入队列中:(队列保持升序)

四、重复步骤三,再次弹出队首两个节点,权重为最小和次小。同样将两个的权重相加,得到一个新权重,构造一个新节点,新构造的节点作为根节点。构成一棵新的二叉树。

五、重复步骤四,得到如下这棵树,将根节点插入队列中,得到队列中仅有一个节点。

六、弹出队列中唯一这个节点,这个节点就是这棵哈夫曼树的根节点。

 

队列一定是任何时候都保持升序,可以利用C++的优先队列:priority_queue

但是按照节点权重进行升序,需要自定义比较方法。

说得比较粗糙,完全自己笔记。见谅。

看下实现代码:

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

//哈弗曼树节点和权重比较方法,优先队列会使用这个权重比较方法
typedef struct HuffmanNode
{
	int weight;
	struct HuffmanNode *lChild;  //左节点
	struct HuffmanNode *rChild;  //右节点
	//重写()作为队列比较函数
	bool operator()(struct HuffmanNode*nodeA, struct HuffmanNode *nodeB)
	{
		return nodeA->weight > nodeB->weight;
	}
}HuffNode;



//构建哈夫曼树
HuffNode * createHuffmanTree(vector<int> weight)
{
	//优先队列
	priority_queue<HuffmanNode*,vector<HuffmanNode*>,HuffNode > huffQue;
	size_t len = weight.size();

	//按照权重构造节点,并将节点插入队列中
	for (vector<int>::iterator it = weight.begin(); it != weight.end(); it++)
	{
		HuffNode *node = new HuffNode;
		node->weight = *it;
		node->lChild = NULL;
		node->rChild = NULL;
		huffQue.push(node);
	}

	//将权重最小和次小的节点弹出,将两个节点的权重相加,作为构造新节点的权重
	//将这个新节点作为根节点,权重最小的节点作为左孩子,次小的作为右孩子。
	//将新的根节点插入队列中
	while (huffQue.size() > 1)
	{
		HuffNode *lChild = huffQue.top();
		huffQue.pop();
		HuffNode *rChild = huffQue.top();
		huffQue.pop();

		HuffmanNode *parent = new HuffmanNode;
		parent->lChild = lChild;
		parent->rChild = rChild;
		parent->weight = lChild->weight + rChild->weight;
		huffQue.push(parent);
	}

	//弹出队列中最后一个节点,作为哈弗曼树的根节点
	HuffmanNode *root = new HuffmanNode;
	root = huffQue.top();
	return root;
}

//先序遍历哈弗曼树
void preOrder(HuffmanNode *root)
{
	if (NULL == root)
	{
		return;
	}

	cout << root->weight<<" ";
	preOrder(root->lChild);
	preOrder(root->rChild);
}

int main()
{
	vector<int> weight = { 4,5,10,15,20};

	//构造哈夫曼树
	HuffmanNode *root = createHuffmanTree(weight);

	//前序遍历哈弗曼树
	cout << "哈弗曼树的前序遍历结果为:" << endl;
	preOrder(root);
	cout << endl;


	system("pause");
	return 0;
}

输出结果:

顺序与前面得到的哈弗曼树先序遍历结果一致。

版权声明:本文为feel_myself_is_lowB原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/feel_myself_is_lowB/article/details/107153710