哈夫曼树(Huffman树)原理分析及实现(C++)

1 构造原理

  假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
  (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
  (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
  (3)从森林中删除选取的两棵树,并将新树加入森林;
  (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

显然对n个权值,构造哈夫曼树树需要合并n-1次,形成的树结点总数为2n-1;

2 代码实现

  根据哈夫曼树的构造原理,为方便实现,我们使用数组来存储每个结点,其命名为Tree;

2.1 节点结构

  节点具有以下结构:
  weight:权值
  parent:父节点在数组中的位置(同时用来判断该节点是否已经参与了合并)
  lchild, rchild:左右孩子结点在数组中的位置
  code:该结点所分配的编码

//结点结构
struct HNode{
	float weight;  //权值
	int parent;  //父节点,父节点主要判定一个结点是否已经加入哈夫曼树
	int lchild, rchild;  //左孩子,右孩子
	string code;  //记录结点编码
	HNode() {
		weight = 0;
		parent = lchild = rchild = -1;
		code = "";
	}
	HNode(float w) {
		weight = w;
		parent = lchild = rchild = -1;
		code = "";
	}
};

2.2 关键成员函数解析

2.2.1 构造函数

  为了判定一个结点是否已经加入哈夫曼树中,可通过parent域的值来确定。初始时parent的值为-1,当某结点加入到树中时,该节点parent域的值为其双亲结点在数组中的下标。

  构造哈夫曼树时,首先将n个权值的叶子结点存放到数组haftree的前n个分量中,然后不断将两棵子树合并为一棵子树,并将新子树的根节点顺序存放到数组Tree的前n个分量的后面。

 哈夫曼算法用伪代码描述为
  1、数组haftree初始化,所有数组元素的双亲、左右孩子都置为-1;
  2、数组haftree的前n个元素的权值置给定权值;
  3、进行n-1次合并:
     3.1 在二叉树集合中选取两个权值最小的根节点,其下标分别为i1,i2;
     3.2 将二叉树i1、i2合并为一棵新的二叉树k。

构造函数输入为权值数组和数组长度

	//构造哈夫曼树,输入权值数组 和 数组长度n
	void Create(float* a, int n) {
		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
		Tree = new HNode[TreeSize];
		//权值数组保存在哈夫曼树数组前n个数值
		for (int i = 0; i < n; i++)
		{
			Tree[i].weight = a[i];
		}
		//开始进行n-1次合并操作,形成一颗哈夫曼树
		int s1, s2;
		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
		for (int i =0; i < (TreeSize-1)/2; i++) {
			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
			//对Tree中新节点的孩子结点及权值赋值
			Tree[nextPos].lchild = s1;
			Tree[nextPos].rchild = s2;
			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
			Tree[s1].parent = Tree[s2].parent = nextPos;
			nextPos++;  //插入位置后移一位
		}
	}

2.2.2 寻找最小的两个点

  先寻找到前两个还未合并的点(parent=-1),在和后面未合并过的点比较权值,确定最终最小的两个点,并确保权值小的在前面;

	//寻找数组中权值最小的两个点
	void SelectTwoMin(int nextPos,int &s1, int &s2) 
	{
		//找到第一个未加入哈夫曼树的结点,标记为s1
		int i=0;
		while (Tree[i].parent != -1) {
			i++;
		}
		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
		s1 = i;
		int j = i + 1;
		while (Tree[j].parent != -1) {
			j++;
		}
		s2 = j;
		//调整s1和s2对应权值大小,确保s1对应点的权值更小,从而寻找更小的点时只需和s2比较
		KeepOrder(s1, s2);
		//从s2后一位开始,和s1,s2比较,确定数组中权值最小的两个点
		for (int k = j + 1; k <nextPos; k++) 
		{
			if (Tree[k].parent == -1) {
				if (Tree[k].weight < Tree[s2].weight) {
					s2 = k;
					//找到小于s2的点后,需和s1比较确定大小顺序
					KeepOrder(s1, s2);
				}
			}
		}
	}
	//确保n1对应结点的权值小于n2
	void KeepOrder(int& n1,int& n2) {
		if (Tree[n1].weight > Tree[n2].weight)
		{
			float tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
	}

2.2.3 对构造好的哈夫曼树进行编码并输出

  这里使用层次遍历,借助一个队列实现;孩子结点的编码由父节点的code加上’1’/’0’(根据其处于父节点的左孩子还是右孩子而定,左孩子为’1’);
  只输出叶子结点的编码.也可以在编码完成后直接输出Tree数组的前n个的结点的编码;

	//对树中结点编码并输出
	void PrintCoder() 
	{
		cout << "index weight     code" << endl;
		queue<int> codeQueue;  //只保存编号
		int tmp;
		codeQueue.push(TreeSize - 1);
		while (!codeQueue.empty())
		{
			tmp = codeQueue.front();
			codeQueue.pop();
			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
				//叶子节点直接输出
				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
			}
			else {//因为哈夫曼树中只有N0和N2
				codeQueue.push(Tree[tmp].lchild);
				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码
				codeQueue.push(Tree[tmp].rchild);
				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
			}
		}
	}
};

2.2.4 输出整个哈夫曼树所有的结点的全部信息(除编码);

	//输出构建完成的哈夫曼树
	void PrintTree() {
		cout << "index weight parent lchild rchild" << endl;
		for (int i = 0; i < TreeSize; i++) {
			cout << setw(5) << i;
			cout << setw(6) << Tree[i].weight;
			cout << setw(6) << Tree[i].parent;
			cout << setw(6) << Tree[i].lchild;
			cout << setw(6) << Tree[i].rchild;
			cout << endl;
		}
	}

2.2 完整代码

#pragma once
#include <iostream>
#include <iomanip>
#include <Queue>
#include <string>
using namespace std;
//用来获取数组长度
template <class T>
int getArrayLen(T& array)
{
	return (sizeof(array) / sizeof(array[0]));
}
//结点结构
struct HNode{
	float weight;  //权值
	int parent;  //父节点,父节点主要判定一个结点是否已经加入哈夫曼树
	int lchild, rchild;  //左孩子,右孩子
	string code;  //记录结点编码
	HNode() {
		weight = 0;
		parent = lchild = rchild = -1;
		code = "";
	}
	HNode(float w) {
		weight = w;
		parent = lchild = rchild = -1;
		code = "";
	}
};
class HuffmanTree {
	HNode* Tree;  //哈夫曼树结点数组头部
	int TreeSize; //树中结点树总数,TreeSize=叶子结点n(要编码的字符个数) * 2 - 1
public:
	HuffmanTree() {
		Tree = NULL;
		TreeSize = 0;
	}
	~HuffmanTree() {
		delete[] Tree;
	}
	//构造哈夫曼树,输入权值数组 和 数组长度n
	void Create(float* a, int n) {
		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
		Tree = new HNode[TreeSize];
		//权值数组保存在哈夫曼树数组前n个数值
		for (int i = 0; i < n; i++)
		{
			Tree[i].weight = a[i];
		}
		//开始进行n-1次合并操作,形成一颗哈夫曼树
		int s1, s2;
		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
		for (int i =0; i < (TreeSize-1)/2; i++) {
			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
			//对Tree中新节点的孩子结点及权值赋值
			Tree[nextPos].lchild = s1;
			Tree[nextPos].rchild = s2;
			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
			Tree[s1].parent = Tree[s2].parent = nextPos;
			nextPos++;  //插入位置后移一位
		}
	}
	//寻找数组中权值最小的两个点
	void SelectTwoMin(int nextPos,int &s1, int &s2) 
	{
		//找到第一个未加入哈夫曼树的结点,标记为s1
		int i=0;
		while (Tree[i].parent != -1) {
			i++;
		}
		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
		s1 = i;
		int j = i + 1;
		while (Tree[j].parent != -1) {
			j++;
		}
		s2 = j;
		//调整s1和s2对应权值大小,确保s1对应点的权值更小,从而寻找更小的点时只需和s2比较
		KeepOrder(s1, s2);
		//从s2后一位开始,和s1,s2比较,确定数组中权值最小的两个点
		for (int k = j + 1; k <nextPos; k++) 
		{
			if (Tree[k].parent == -1) {
				if (Tree[k].weight < Tree[s2].weight) {
					s2 = k;
					//找到小于s2的点后,需和s1比较确定大小顺序
					KeepOrder(s1, s2);
				}
			}
		}
	}
	//确保n1对应结点的权值小于n2
	void KeepOrder(int& n1,int& n2) {
		if (Tree[n1].weight > Tree[n2].weight)
		{
			float tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
	}
	//输出构建完成的哈夫曼树
	void PrintTree() {
		cout << "index weight parent lchild rchild" << endl;
		for (int i = 0; i < TreeSize; i++) {
			cout << setw(5) << i;
			cout << setw(6) << Tree[i].weight;
			cout << setw(6) << Tree[i].parent;
			cout << setw(6) << Tree[i].lchild;
			cout << setw(6) << Tree[i].rchild;
			cout << endl;
		}
	}
	//对树中结点编码并输出
	void PrintCoder() 
	{
		cout << "index weight     code" << endl;
		queue<int> codeQueue;  //只保存编号
		int tmp;
		codeQueue.push(TreeSize - 1);
		while (!codeQueue.empty())
		{
			tmp = codeQueue.front();
			codeQueue.pop();
			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
				//叶子节点直接输出
				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
			}
			else {//因为哈夫曼树中只有N0和N2
				codeQueue.push(Tree[tmp].lchild);
				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码
				codeQueue.push(Tree[tmp].rchild);
				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
			}
		}
	}
};

3 测试代码及输出

    ///哈夫曼树
    HuffmanTree hTree;
	float x[] = { 5,29,7,8,14,23,3,11 };
	hTree.Create(x, getArrayLen(x));//避免输入错误的数组长度导致错误
	hTree.PrintTree();
	hTree.PrintCoder();

正确输出:

4 参考资料

1.哈夫曼树算法及C++实现:https://www.cnblogs.com/smile233/p/8184492.html
2.百度百科·哈夫曼树:https://baike.baidu.com/item/哈夫曼树/2305769#5
3.数据结构:Huffman树(哈夫曼树)原理及C++实现:https://blog.csdn.net/weixin_41427400/article/details/80383686

https://juejin.im/post/5de8c3a7f265da33f718a6ba

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论