哈夫曼树 编码-【数据结构】树形结构——哈夫曼编码

目录

  一、哈夫曼编码的概念

  在电报业务和数字通信中，可以用0和1组成的编码表示一个字母或其他字符，用编码序列表示字符序列以进行远距离传送。长途通信的代价是比较高的，希望用尽可能短的编码序列长度来传递给定的信息量，以提高通信的效率和降低传输的成本。

  如果根据字符出现的次数为每个字符设计长度不等的编码，使用频率高的字符采用尽可能短的编码，则传送电文的总长便可减少。但是长短不同的编码也会给翻译带来不便，产生歧义。因此，若要设计长短不等的编码，则必须是任一个字符编码都不是另一个字符编码的前缀，这种编码称作前缀编码。

  若需要编码的字符为C1、C2哈夫曼树 编码，……，Cn，它们在电文中出现的频率分别为W1、W2，……，Wn，以字符作为叶子结点构造一棵哈夫曼树。规定哈夫曼树中每个分支结点的左分支表示0，右分支表示1，将从根结点到每个叶子结点所经过路径上的0和1连接起来，作为叶结点所代表字符的编码。这样得到的编码称为哈夫曼编码。在哈夫曼编码中，每个字符的编码长度就等于根结点到字符所在叶子结点的路径长度。由哈夫曼树的定义可知，哈夫曼树是带权路径长度最小的二叉树，树的路径长度就是每个字符的编码长度与其出现频率的乘积之和，因此利用哈夫曼树构造的编码总长度最短。由于从根到叶结点只有一条唯一的路径，且不经过其他叶子结点，因此哈夫曼编码是一种不等长的前缀编码。

  二、哈夫曼编码的实现

  哈夫曼编码过程由于是从叶子向上追溯到根，编码过程记录下的是每一个字符逆序的编码，因此除了存储从叶子到根经过的编码外，还需记录编码的起始位置start。每个字符的哈夫曼编码的存储结构定义如下：

   struct{

  int bitMAXBIT;

  int start;

  };

  生成哈夫曼编码的过程如下：

  （1）由叶子结点出发，向上直到树根，向上的过程中，结点若为其双亲的左孩子，则编码为0；否则编码为1，由于是从叶子向上追溯到根，所以编码也是从后向前哈夫曼树 编码，记住编码的起始位置start。

  （2）直到所有叶子结点均编码结束为止。

  void ( [], [],int n){

   cd;

  int i,j,c,p;

  for(i=0;i

  cd.start=n-1;

  c=i;

  p=c.parent;

  while(p!=1){

  if(p.lchild==c)

  cd.bitcd.start=0;

  else

  cd.bitcd.start=1;

  cd.start--;

  c=p;

  p=c.parent;

  }

  for(j=cd.start+1;j

  i.bitj=cd.bitj;

  }

  i.start=cd.start;

  }

  }

本文共 707 个字数,平均阅读时长 ≈ 2分钟