【数据结构】赫夫曼树与编码-创新互联

• 前言
• 赫夫曼树
• • 存储结构
  • 初始化树
  • 构建树
• 赫夫曼编码
• • 初始化编码
  • 构建编码

（概念）
路径：从一个节点到另一个节点的分支
路径长度：从一个节点到另一个节点的分支总数
节点的带权路径：该节点到根节点之间路径长度与权值的乘积
树的带权路径长度(WPL)：所有叶子节点的带权路径长度之和

赫夫曼树采取静态存储的方式，以下面为例：

所需头文件：

#includeusing namespace std;
#include#include#include

初始化树：

const int n = 8;                   //叶子个数（权值个数）
const int m = 2 * n;               //树节点个数+1（第0下标不放值，是标记位）
typedef unsigned int WeightType;   //权值类型
typedef unsigned int NodeType;     //节点类型

typedef struct       //树节点
{WeightType weight;
	NodeType parent, leftchild, rightchild;
}HtNode;

typedef HtNode HuffmanTree[m];    //赫夫曼树

void InitHuffmanTree(HuffmanTree hft,const WeightType w[])
{for (int i = 0; i< n; i++)
	{hft[i + 1].weight = w[i];
	}
}

打印树：

void PrintHuffmanTree(HuffmanTree hft)
{cout<< "（赫夫曼树：）"<< endl;
	for (int i = 1; i< m; i++)
	{cout<< "  index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
	}
	cout<< endl<< endl;
}

主函数：

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	PrintHuffmanTree(hft);
	return 0;
}

初始化结果：

使用优先级队列来存放存有下标和权值的结构体，使用greater：将数据大的下沉（形成小顶堆），使用less：将小数据下沉（形成大顶堆）

代码实现：

struct IndexWeight
{int index;   //下标
	WeightType weight;   //权值
	operator WeightType() const {return weight; }   //重载（当用此结构体作比较时，用weight来进行比较）
};

void CreateHuffmanTree(HuffmanTree hft)
{std::priority_queue, std::greater>qu;     //优先级队列（小顶堆）
	for (int i = 1; i<= n; i++)
	{qu.push(IndexWeight{i,hft[i].weight });
	}

	int k = n + 1;
	while (!qu.empty())
	{if (qu.empty()) {break; }
		IndexWeight left = qu.top();
		qu.pop();
		if (qu.empty()) {break; }
		IndexWeight right = qu.top();
		qu.pop();
		hft[k].weight = left.weight + right.weight;
		hft[k].leftchild = left.index;
		hft[k].rightchild = right.index;
		hft[left.index].parent = k;
		hft[right.index].parent = k;
		qu.push(IndexWeight{k,hft[k].weight });
		k++;
	}
}

打印树：

void PrintHuffmanTree(HuffmanTree hft)
{cout<< "（赫夫曼树：）"<< endl;
	for (int i = 1; i< m; i++)
	{cout<< "  index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
	}
	cout<< endl<< endl;
}

主函数：

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);
	return 0;
}

构建结果：

以此赫夫曼树为例：

原本发送"ABCDEFGH"这些字符时，每个字符都是8个二进制位（char 1字节）总共要发：8*8=64位二进制，但通过赫夫曼编码后总共要发：27位二进制，因此赫夫曼编码在文件传输时有巨大作用

代码实现：

typedef struct
{char ch;        //节点对应的数据
	char code[n+1]; //该节点的赫夫曼编码
}HuffmanCode;

typedef HuffmanCode HuffmanCoding[n];

void InitHuffmanCode(HuffmanCoding hfc,const char ch[])
{for(int i=0;ihfc[i].ch=ch[i];
		hfc[i].code[n]={'\0'};
	}
}

打印编码：

void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
	{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码："<< hfc[i].code<< endl;
	}
}

主函数：

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);
	const char ch[n + 1] = {"ABCDEFGH" };  //必须是n+1，双引号最后会有一个'\0'
	HuffmanCoding hfc = {0 };
	InitHuffmanCode(hfc, ch);
	PrinthuffmanCode(hfc);
	return 0;
}

初始化结果：

从叶子节点向根节点走，如果是左孩子则为0，反之则为1
创建一个数组来存放0，1值，从后向前存放，这样读取的时候就是正着读取的

代码实现：

void CreateHuffmanCode(HuffmanTree hft, HuffmanCoding hfc)
{char code[n + 1] = {0 };
	for (int i = 1; i<= 8; i++)
	{int k = n;
		int child = i;
		int parent = hft[i].parent;
		while (parent != 0)
		{	if (child == hft[parent].leftchild)
			{		code[--k] = {'0' };
			}
			else if (child == hft[parent].rightchild)
			{		code[--k] = {'1' };
			}
			child = parent;
			parent = hft[child].parent;
		}
		strcpy_s(hfc[i - 1].code, n, &code[k]);
	}
}

打印编码：

void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
	{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码："<< hfc[i].code<< endl;
	}
}

主函数：

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);

	const char ch[n + 1] = {"ABCDEFGH" };  //必须是n+1，双引号最后会有一个'\0'
	HuffmanCoding hfc = {0 };
	InitHuffmanCode(hfc, ch);
	CreateHuffmanCode(hft, hfc);
	PrinthuffmanCode(hfc);
}

构建结果：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧