3.2 算法的设计
利用 Huffman 编码树求得最佳的编码方案。
根据哈夫曼算法,建立哈夫曼树时,可以将哈夫曼树定义为一个结构型的一维数组
HuffTree,保存哈夫曼树中各结点的信息,每个结点包括:权值、左孩子、右孩子、双亲,
如图 6 所示。由于哈夫曼树中共有 2n-1 个结点,并且进行 n-1 次合并操作,所以该数组的
长度为 2n-1。
图 3-1 哈夫曼树的结点结构
weight lchild rchild parent
构造哈夫曼树的伪代码如下:
1. 数组 huffTree 初始化,所有元素结点的双亲、左右孩子都置为-1;
2. 数组 huffTree 的前 n 个元素的权值置给定权值 w[n];
3. 进行 n-1 次合并
3.1 在二叉树集合中选取两个权值最小的根结点,其下标分别为 i1, i2;
3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k;
在哈夫曼树中,设左分支为 0,右分支为 1,从根结点出发,遍历整棵哈夫曼树,求得
各个叶子结点所表示字符的哈夫曼编码。
3.3 抽象数据类型的设计
ADT Tree
Data
树是由一个根结点和若干棵子树构成,树中结点具有相同数据类型及层次关系
Operation
InitTree
前置条件:树不存在
输入:无
功能:初始化一棵树
输出:无
后置条件:构造一棵树
前置条件:树已存在
输入:无
功能:销毁一棵树
输出:无
DestroyTree