数据结构求哈夫曼编码

已知某系统在通信联络中只可能出现8种字符ABCDEFGH，其概率分别为8 15 4 6 24 13 11 20。先画出哈夫曼树的示意图，再根据该树依次写出这8种字符的哈夫曼编码。

感觉这种题一搜一大把
https://blog.csdn.net/weixin_44462294/article/details/103644915

不知道你这个问题是否已经解决, 如果还没有解决的话:

你可以看下这个问题的回答https://ask.csdn.net/questions/7686732
这篇博客也不错, 你可以看下字符串的测试题：1、从字符串“abcdefzhig”中取下标为偶数的字符放入另一字符串中，并输出。（用两种方法完成：①、用字符数组来完成。②、用字符串来完成。）
除此之外, 这篇博客: 拓扑排序解决ABC比较大小问题中的 拓扑排序解决ABC比较大小问题 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
ABC
有三个数，分别用A，B，C表示，告诉你他们的两两比较的结果，输出他们的大小关系。Input输入的数据有多组，每组数据有三行，每行有两个字母，表示前面的字母代表的数比后面的字母代表的数大,每行的两个字母不相同。Output如果他们比较的结果合法，那么把它们按照从小到大的顺序输出，两个字母中间应有“<”号，否则就输出“The input is not true!”,输出占一行。
Sample Input
AB
BC
AC
AB
BA
AC
Sample Output
C<B<A
The input is not true!
既然是字母比较，那么拓扑排序就能很好解决这个问题。为什么？
因为拓扑排序是有向无环图，他的实质是对有向图的顶点排成一个线性序列。简单来说。由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
回到问题，我们需要的结果恰好就是一个序列，我们的输入可以看作是拓扑排序给定的先后顺序。且当成环时（AB BC CA），就会无法拓扑排序也就是ABC无法比较。
那么怎么排序呢？
首先我们需要处理输入的数据，就拿AB BC AC 举例子
AB相当于 A>B,由于我们的输出是从小到大
所以，姑且想象成B->A（此时A的入度需要+1，拓扑排序根据入度依次删除节点）
同时记录下B的可去的一个节点增加一个A
同理BC 就是B的入度+1，C的可去的一个节点增加一个B
最后AC 就是A的入度+1，C的可去的一个节点增加一个A
然后开始进行拓扑排序：
现在A的入度为2，B的入度为1，C的入度为0
找到C，删去它，并且找到它的可去的节点（C->A 和C->B）使A,B入度-1；
现在A的入度为1，B的入度为0，C已被处理
找到B，删去它，并且找到它的可去的节点（B->A）使A入度-1；
现在A的入度为0，B已被处理，C已被处理
找到A，删去它，发现他没有可去的节点，那么抵达末尾，循环结束；
因为有三个节点，所以如果我们循环三次说明是正确的。
然后按照删除节点的顺序打印C->B->A即可
以上便是
正常结果的情况
下面看看如果不是正确结果的情况
如果没有循环三次，说明他可能成环了，（AB BA AC）
经过上面同理处理，A入度为2，可去节点为B；B入度为1，可去节点为A； C入度为0可去节点为A
那么先删去C，然后使A入度-1，那么此时无入度为0的点跳出循环。
你可能会问若第三条不是AC而是BC呢？那会变成B的入度为2，然后先删C，B入度-1，还是没有入度为0的点。
接下来我们考虑一下特殊输入，比如AB出现两次，那么我们就需要让多余的数据不处理
还有就是一个节点指向两个节点，另外两个节点不知道顺序的情况（AB AB CB）B入度为0，但是AC入度均为1.所以没有入度为2的节点需要提前结束循环判为错误，因为我们的题目需要保证ABC存在绝对比较性
好了，下面是代码时间：
```
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ABC{
 char u;//自身所代表字母 
 int d;//入度 
 vector<int> v;//存比它大的字母 
}e[3];//ABC分别对应三个点
queue<ABC> q;
char res[4];
bool used(vector<int> v,int x)//判断vector是否存在x 
{
 	for(vector<int>::iterator i=v.begin();i!=v.end();i++)
 	{
  		if(*i==x)
  		{
   			return true;
  		}
 	}
 	return false;
}
int main()
{
   	int n=0;
 	char x[3],y[3],z[3];
	 e[0].u='A';
 	 e[1].u='B';
	 e[2].u='C';
 	//初始化ABC 
 
   while(~scanf("%s%s%s",&x,&y,&z))
   {
  	 e[x[1]-'A'].v.push_back(x[0]-'A');
   	 e[x[0]-'A'].d++;
   	 if(!used(e[y[1]-'A'].v,y[0]-'A'))//如果没有加入到vector才加入，删去重复输入 
  	 {
   	 	e[y[1]-'A'].v.push_back(y[0]-'A');
    	 	e[y[0]-'A'].d++;
  	 }
  	 if(!used(e[z[1]-'A'].v,z[0]-'A'))
   	 {
    	 	e[z[1]-'A'].v.push_back(z[0]-'A');
    	 	e[z[0]-'A'].d++;
  	 } 
  	 for(int i=0;i<3;i++)//获取入度为0的字母 
	 {
  	 	if(!e[i].d)
  	 	{
  	 	 	q.push(e[i]);
  	 	 	break;
  	 	}
 	 }
   	int sum=0;
 	 while(!q.empty())//BFS 
  	{
   		ABC temp=q.front();
   		res[sum++]=temp.u;//记录结果 
   		q.pop();
   		if(temp.v.size()==2)
   		{
   			//如果某个点 和两个点连接 且那两个点的权值相等，说明两个点无法比较大小 
    			if(e[temp.v[0]].d==e[temp.v[1]].d)
    			break;
   		}
   		for(vector<int>::iterator i=temp.v.begin();i!=temp.v.end();i++)
   		{
    			if(!(--e[*i].d))//所连线边入度-1，且如果其入度为0，就加入队列 
   		 	q.push(e[*i]);
   		}
  }
  if(sum==3)//如果有三次则说明ok 
  {
   cout<<res[0]<<"<"<<res[1]<<"<"<<res[2]<<endl;
  }
  else{
   puts("The input is not true!");
  }
   
  
  for(int i=0;i<3;i++)//重置e 
  {
   e[i].d=0;
   e[i].v.clear();
  }
     
 }
}
```
以下回答来自chatgpt:
我可以解决该问题。
首先根据给定的字符和对应的概率构造哈夫曼树，具体方法如下： 1. 把所有字符看做一个森林，每个森林只有一个节点； 2. 把森林中概率最小的两个节点合并为一个节点，该节点作为新的森林的一棵树； 3. 在新森林中重复执行步骤2，直到只剩下一棵树，此时构造出了哈夫曼树。根据这个方法，我们可以得到下面的哈夫曼树示意图：
接着根据哈夫曼树，可以得到每个字符的哈夫曼编码： | 字符 | 频率 | 编码 | | --- | --- | --- | | A | 8 | 111 | | B | 15 | 10 | | C | 4 | 0001 | | D | 6 | 0010 | | E | 24 | 01 | | F | 13 | 0011 | | G | 11 | 110 | | H | 20 | 0000 |
最后回答第二个问题，哈夫曼编码的平均码长为： 8/100 * 3 + 15/100 * 2 + 4/100 * 4 + 6/100 * 4 + 24/100 * 2 + 13/100 * 4 + 11/100 * 3 + 20/100 * 4 = 2.71 而等长编码的平均码长为3，所以哈夫曼编码是等长编码的2.71/3=0.90，意味着哈夫曼编码使得电文平均压缩了近10%。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^