2014-2_5树与二叉树(4h).pptVIP

* * * * * * * * * * * * * * * * * * * * * 性质3：在任意一棵二叉数中，度为0的结点（即叶子结点）总是比度为2的结点多一个 * 3. Huffman编码 编码：用二进制数的不同组合来表示字符的方法。 前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。 a 0 b 0 1 c d 0 1 1 编码：A（0） B（10） C（110） D（111） 方法约定： 1）左分支为‘0’ 2）右分支为‘1’ 3）由叶到根路径上字符组成的二进制串就是该叶结点的编码。 Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。 Huffman编码举例 在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为{5，29，7，8，14，23，3，11}，n=8，其Huffman树为： 8 1 0 0 0 0 0 0 0 1 1 1 1 1 1 5 3 7 14 29 11 23 42 58 100 Huffman编码为： A 5 0110 B 29 10 C 7 1110 D 8 1111 E 14 110 F 23 00 G 3 0111 H 11 010 4.Huffman编码存储结构 由于Huffman树中没有度为1的结点，则n个叶结点的Huffman树共有2n-1个结点。例如，4个叶结点的Huffman树，共有7个结点。因此可以用长度为2n-1的一维数组存放。 求Huffman编码： 从根到叶的编码。因此要知道每个结点的父结点。 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 Huffman编码为： A 5 0110 B 29 10 C 7 1110 D 8 1111 E 14 110 F 23 00 G 3 0111 H 11 010 5.Huffman编码的译码 从Huffman编码树上不难看出，代码全部在叶结点上，根据Huffman编码，就能求出相应的字符。该过程称为“译码”。 译码是根据从根到叶的Huffman编码求相应的字符。因此要知道每个结点的左右子结点。 例如，根据“1111”，就能求出对应的字符是“8”。 5 3 0 0 0 0 0 0 0 1 1 1 1 1 1 1 7 8 14 29 11 23 42 58 100 作业 在某系统的通信联络中可能出现10种字符（A-I），其频率分别为0.04、0.15、0.07、0.08、0.14、0.21、0.02、0.12、0.16、0.09。试建立其Huffman树并给出其Huffman编码。 课本：习题2.16 ，习题 2.22。 总结 1.树的定义 2.树的基本概念 3.二叉树 4.特殊二叉树 5.二叉树的遍历操作 * * * * * * * * * * * * * * * * * * * * * * * * * * （3）二叉排序树定义一 二叉排序树 或者是空二叉树； 或者是： 左子树上所有结点的值均小于根结点的值； 右子树上所有结点的值均大于等于根结点的值； 左、右子树本身又是一棵二叉排序树。 最后一句话可否去掉？ 区别于有序树 二叉排序树定义（二） X是二叉排序树T中的一个结点； 所有的左后裔小于X； 所有的右后裔大于等于X； T可以为空树； T称为二叉排序树。 10 4 7 12 14 18 14 （a）二叉排序树 14 14 18 4 10 12 13 7 （b）非二叉排序树 2.5.3 二叉树的遍历 遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。 遍历的方法很多，常用的有： 前序法（PreOrder） 中序法（InOrder） 后序法（PostOrder） 1、前序法（PreOrder） 方法描述： 从根结点a开始访问， 接着访问左子结点b， 最后访问右子结点c。 即： 根 左子 右子 a b c A 访问根结点 B 先序遍历左子树 C 先序遍历右子树 2、中序法（In