2669 - 数据结构/二叉树/huffman编码

CAST;
2 4 2 3 3
CAST;
1101000

110101110001
CAT

Hint

	1、结点结构体可以定义如下：

struct TreeNode

{

 int parent;//父结点

 int lchild;//左孩子

 int rchild;//右孩子

 int weight;//结点权重

 char ch;  //字符，非0即叶子结点，输出时可以由此判断

 char code;//编码，改结点是父结点的左孩子时为'0'，右孩子时为'1'

 TreeNode()

 {

  parent=lchild=rchild=0;

  ch=0;

 }

};

2、树的定义可以如下：



#define N 32<br />

struct HuffmanTree

{

 TreeNode table[N+N-1];

 int nLeaves;//叶子结点数量


&nbsp;void CreateTree(char chars[],int weights[])<br />

 {//根据字符集以及每个字符的权值创建树

  nLeaves=strlen(chars);


&nbsp;&nbsp;//TODO:请自行完成<br />

 }


&nbsp;void EncodeChar(char ch)<br />

 {//TODO:编码单个字符

 }

 void EncodeString(char str)

 {//TODO:编码字符串

  char ch;

  while(ch=str++)//逐个编码每个字符

   EncodeChar(ch);

  printf("\n");

 }


&nbsp;void DecodeString(char *codes)<br />

 {//TODO:解码字符串

  printf("\n");

 }


};



3、测试用例可以参考：


int main()

{

 int weights[]={2,4,2,3,3};

 tree.CreateTree("CAST;",weights);

 tree.EncodeString("CAST;");//期待输出为110101110001

 tree.DecodeString("1101000");//期待输出为CAT

 return 0;

}

Solution C++

// Huffman.cpp : 定义控制台应用程序的入口点。
//

#include <stdio.h>
#include <string.h>
//可能的最大权值个数
#define N 32
//表示无穷大
#define MAX 9999
//表示没有双亲
#define NO_PARENT -1
//表示没有孩子
#define NO_CHILD -1
//表示没有编码
#define NO_CODE 0
//表示没有解码值
#define NO_DATA 0

struct TreeNode
{
	int parent;

	int lchild;
	int rchild;
	int weight;//权重
	char ch;
	char code;//编码
	TreeNode()
	{
		parent = NO_PARENT;
		lchild = NO_CHILD;
		rchild = NO_CHILD;
		ch = NO_DATA;
		code = NO_CODE;

	}
};

struct HuffmanTree
{
	TreeNode table[N + N - 1];
	int nLeaves;//叶子数量
	void CreateTree(char chars[], int weights[])
	{
		//根据字符集以及每个字符的权值创建树
		/*
		用到的变量说明：
		nLeaves 叶子节点数量
		n 表长，即整个哈夫曼树的节点数量
		index1、index2  table表中没有双亲的节点中权值（weight）最小的两个节点的编号（即数组下标）
		i 循环变量

		算法描述：
		1、将权值数组和待编码的字符数组分别按顺序赋值给哈夫曼树的节点表（table）中的前nLeaves个节点的
		权值（weight）和待编码的字符（ch）：
			this->SetHT(chars,weights);
		2、从table表中选出两个最小的且没有双亲的节点，得到其在table表中的下标：
			this->Select(i, index1, index2);
		3、将两个最小的节点的权值的和作为一个新的权值接着放入table中
		*/
		nLeaves = strlen(chars);
		this->SetHT(chars,weights);
		int n = nLeaves + nLeaves - 1;
		int index1 = 0, index2 = 0;

		for (int i = nLeaves; i < n; i++)
		{
			this->Select(i, index1, index2);
			this->table[i].weight = this->table[index1].weight + this->table[index2].weight;
			this->table[i].lchild = index1;//设置第一个最小权值的节点为左孩子
			this->table[i].rchild = index2;//设置第二个最小权值的节点为右孩子
			this->table[index1].parent = i;//设置第一个最小权值的节点的父亲
			this->table[index1].code = '0';//左孩子 其编码为0
			this->table[index2].parent = i;//设置第二个最小权值的节点的父亲
			this->table[index2].code = '1';//右孩子 其编码为1
		}
		
	}
	void EncodeChar(char ch)
	{
		//编码单个字符
		/*
		从叶子节点开始回访找到ch的编码
		*/
		int i = 0;
		int j = 0;
		char *s = new char[N]{0};
		while (ch != this->table[i].ch)
		{
			i++;
		}
		while (this->table[i].parent != NO_PARENT)
		{
			s[j] = this->table[i].code;
			j++;
			i = this->table[i].parent;
		}
		for (int k = j-1; k >= 0; k--)
		{
			printf("%c",s[k]);
		}
	}
	void EncodeString(char *str)
	{//编码字符串
		char ch;
		while (ch = *str++)//逐个编码每个字符
			EncodeChar(ch); 
		printf("\n");
	}
	void DecodeString(char *codes)
	{//解码字符串
		/*
		从根节点开始给codes解码
		因为编码是唯一的，所以当遇到叶子节点时，意味着对应的的编码就解码了
		*/
		int n = strlen(codes);
		for (int i = 0; i < n;)
		{
			int t = nLeaves + nLeaves - 1 - 1;//根节点在table表中的下标
			while (this->table[t].lchild != NO_CHILD)//每个节点要么左右孩子都有，要么没有孩子，所以这里只需要判断一个孩子是否存在就行了
			{
				if (codes[i] == '0')//如果当前的编码值为‘0’，意味着该沿着左孩子方向寻找
				{
					t = this->table[t].lchild;
				}
				else//如果当前的编码值为‘1’，意味着该沿着右孩子方向寻找
				{
					t = this->table[t].rchild;
				}
				i++;
			}
			//执行完以上的while循环后，此时t应该是要找的叶子节点，其ch值就是我们要找的解码结果
			printf("%c",this->table[t].ch);
		}
		printf("\n");
	}
	void SetHT(char chars[], int weights[])
	{
		/*
		函数功能：
		将权值数组和待编码的字符数组分别按顺序赋值给哈夫曼树的节点表（table）中的前nLeaves个节点
		权值（weight）和待编码字符（ch）：
		*/
		for (int i = 0; i < nLeaves;i++)
		{
			this->table[i].weight = weights[i];
			this->table[i].ch = chars[i];
		}
	}
	void Select(int i, int &index1, int &index2)
	{
		int num1 = MAX,num2 = MAX;
		for (int j = 0; j < i; j++)
		{
			if (this->table[j].parent == NO_PARENT)
			{
				if (num1>this->table[j].weight)
				{
					num1 = this->table[j].weight;
					index1 = j;
				}
			}
		}
		for (int j = 0; j < i; j++)
		{
			if (j != index1)
			{
				if (this->table[j].parent == NO_PARENT)
				{
					if (num2>this->table[j].weight)
					{
						num2 = this->table[j].weight;
						index2 = j;
					}
				}
			}
		}
	}
};

int main()
{
	//HuffmanTree tree;
	//int weights[] = { 2, 4, 2, 3, 3 };
	//tree.CreateTree("CAST;", weights);
	//tree.EncodeString("CAST;");//期待输出为110101110001
	//tree.DecodeString("1101000");//期待输出为CAT
	HuffmanTree tree;
	char chars[N]{0};
	int weights[N]{0};
	char charsCh[N]{0};
	char charsCode[N]{0};
	int i = 0;
	int n = 0;
	gets(chars);
	n = strlen(chars);
	for (i = 0; i < n; i++)
	{
		scanf("%d ",&(weights[i]));
	}
	gets(charsCh);
 	gets(charsCode);
	tree.CreateTree(chars, weights);
	tree.EncodeString(charsCh);
	tree.DecodeString(charsCode);
	return 0;
}