数据结构：思想与方法-翁惠玉-27783第五章幻灯片.ppt

* A B C D F G E H I J A B C D F G E H I J * 森林 森林通常定义为树的集合或树的序列。 森林的存储：存储一个森林要包括两方面的内容 存储森林中的每一棵树 表示这些树是属于同一个森林。 * 森林的二叉树存储 将每棵树Ti转换成对应的二叉树Bi； 将Bi作为Bi-1根结点的的右子树。 * A B C R F G H D E I J K L M N （a）森林F A B C R F G H D E I J K L M N （b）森林F中的树对应的二叉树 * A B C R F G H D E I J K L M N 森林F中的树对应的二叉树 * 总结 本章是数据结构的重点之一，也是本书许多后续章节的基础。 本章主要介绍了树形结构的基本概念，详细讨论了一种重要的数据结构 — 二叉树的设计和实现。在此基础上介绍了二叉树的两种应用 — 表达式树和哈夫曼树。 最后，本章还介绍了如何处理普通的树形结构以及森林。普通的树形结构和森林的处理方法是将它们转换成二叉树来处理 * * * * * * * * * * * * * * * 哈夫曼编码的生成 每个字符的编码是根节点到该字符的路径 左枝为0，右枝为1 * 哈夫曼树类的实现 为了便于找出一组符号的哈夫曼编码，我们可以定义一个哈夫曼树类。 哈夫曼树类的对象可以接受一组符号以及对应的权值，并告知每个符号对应的哈夫曼编码。因此，哈夫曼树类应该有两个公有的成员函数： 构造函数：接受一组待编码的符号以及它们的权值，构造一棵哈夫曼树。 GetCode函数根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。 * 哈夫曼树的存储 在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为2的节点 一旦给定了要编码的元素个数，由n0＝n2＋1可知哈夫曼树的大小为2n-1 哈夫曼树可以用一个大小为2n的数组来存储。0节点不用，根存放在节点1。叶结点依次放在n+1到2n的位置 每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置 * 值 a e i s t sp nl 权 58 33 25 18 8 4 10 15 12 3 4 13 1 父 1 1 2 4 5 4 2 3 6 5 3 6 左 2 4 9 5 6 10 右 3 8 12 7 11 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 i 12 13 空格 25 58 e 15 33 a 10 18 t 4 S 3 1 换行 4 8 * 13 12 11 10 9 8 7 6 5 4 3 2 1 0 13 11 7 12 8 3 右 10 6 5 9 4 2 左 6 3 5 6 3 2 4 5 4 2 1 1 父 1 13 4 3 12 15 10 4 8 18 25 33 58 权 nl sp t s i e a 值 生成过程 * 编码的产生 值 a e i s t sp nl 权 58 33 25 18 8 4 10 15 12 3 4 13 1 父 1 1 2 4 5 4 2 3 6 5 3 6 左 2 4 9 5 6 10 右 3 8 12 7 11 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 生成a的代码：结点4的右孩子（1），结点4是结点2的左孩子（01），结点2是结点1的左孩子（001） 对每个结点，从叶子往根推进，是左枝加0，是右枝加1 * 哈夫曼树类 存储设计 结点的表示：结点的数据、权值和父结点和左右孩子的位置 哈夫曼树的存储：一个结点数组以及一个整型数据成员，保存数组的大小。 操作 构建一棵哈夫曼树：构造函数实现。 给出节点数据数组，权值数组和数据个数 获取树上节点的哈夫曼编码 返回一个数组，数组的元素由数据和编码两部分组成的 * template class Type class hfTree{ private: struct Node { Type data; //结点值 int weight; //结点的权值 int parent, left, right; }; Node *elem; int length; * public: struct hfCode { Type data; string code; }; hfTree(const Type *x, const int *w, int size); void getCode(hfCode result[ ]); ~hfTree() {d