哈夫曼编码
1) 问题描述
设某编码系统共有n个字符，使用频率分别为{w1, w2, …, wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2) 基本要求
(1) 设计数据结构；
(2) 设计编码算法；
(3) 分析时间复杂度和空间复杂度。
3) 设计思想
利用Huffman编码树求得最佳的编码方案。
根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。



构造哈夫曼树的伪代码如下：
1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；
2. 数组huffTree的前n个元素的权值置给定权值w[n]；
3. 进行n-1次合并
3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；
3.2 将二叉树i1、i2合并为一棵新的二叉树k；
在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。