说明

实验原理：

　　哈夫曼树(Huffman)——带权路径长度最短的树.....此处省略200字

 

实验步骤：

　　1.实现树结点的定义。

　　2.实现树的定义，包含的方法有创建树，编码字符串，解码字符串。

 

输入格式

每组测试用例由四行组成：

第一行是一个字符串，表示字符集；

第二行是每个字符对应的权值，每个权值大于1小于1000；

第三行是一个编码前的字符串；

第四行是一个编码后的字符串。

输出格式

每组测试用例需要输出两行：

第一行是对输入的第三行的编码；

第二行是对输入的第四行的解码。

 

CAST;
2 4 2 3 3
CAST;
1101000

110101110001
CAT

提示

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
struct HuffmanTree
{
 TreeNode table[N+N-1];
 int nLeaves;//叶子结点数量

 void CreateTree(char chars[],int weights[])
 {//根据字符集以及每个字符的权值创建树
  nLeaves=strlen(chars);

  //TODO:请自行完成
 }

 void EncodeChar(char ch)
 {//TODO:编码单个字符
 }
 void EncodeString(char *str)
 {//TODO:编码字符串
  char ch;
  while(ch=*str++)//逐个编码每个字符
   EncodeChar(ch);
  printf("\n");
 }

 void DecodeString(char *codes)
 {//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;
}

来源

数据结构-树/二叉树