哈夫曼编码/译码器

用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n－1次合并，所以共产生n－1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n－1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码，编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。假设每种字符在电文中出现的次数为Wi，编码长