ch6树和二叉树.ppt

* 例2 假设用于通信的电文仅由8个字母{ a, b, c, d, e, f, g, h } 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？ 赫夫曼编码的基本思想是： 概率大的字符用短码，概率小的用长码。由于赫夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。 解：先将概率放大100倍，以方便构造哈夫曼树。 权值集合 w={ 7, 19, 2, 6, 32, 3, 21, 10 }， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。 * w4={19, 21, 28, 32} 为清晰起见，重新排序为:w={2, 3, 6, 7, 10, 19, 21, 32} 2 3 5 6 w1={5, 6, 7, 10, 19, 21, 32} w2={7, 10, 11, 19, 21, 32} w3={11, 17, 19, 21, 32} 11 10 7 17 28 21 19 40 w5={28,32,40} 32 60 w6={40,60} w7={100} 100 b c a d e g f h 哈夫曼树 × × × × × × × × × × × × × × * 对应的哈夫曼编码（左0右1）： 2 3 5 6 11 10 7 32 17 28 21 40 60 100 b c a d e g f h 0 0 0 0 0 1 1 1 1 1 1 1 0 0 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 Huffman码的WPL＝2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 二进制码 * 另一种结果表示： * 例3 设字符集为26个英文字母，其出现频度如下表所示。 51 48 1 15 63 57 20 32 5 1 频度 z y x w v u t 字符 1 16 1 18 8 23 80 频度 p 21 f q 15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符 先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。 * 提示1：赫夫曼树中各结点的结构可以定义为如下5个分量： char weight parent lchild Rchild 将整个赫夫曼树的结点存储在一个数组中：HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3：赫夫曼树如何构造？构造好之后又如何求得各结点对应的赫夫曼编码？——算法参见教材P147。 提示2：赫夫曼树的存储结构可采用顺序存储结构： Huffman树及Huffman编码的编程实现： 树 结 构 树 二叉树 逻辑结构 逻辑结构 存储结构 存储结构 树的定义 基本术语 抽象数据类型 双亲表示法 孩子表示法 孩子兄弟表示法 二叉树的定义 特殊的二叉树 二叉树的性质 抽象数据类型 顺序存储结构 二叉链表 ⑴ 单支树 ⑵ 满二叉树 ⑶ 完全二叉树 三叉链表 线索链表 树的遍历 ⑴ 先根遍历 ⑵ 后根遍历 ⑶ 层序遍历 二叉树的遍历 ⑴ 前序遍历 ⑵ 中序遍历 ⑶ 后序遍历 ⑷ 层序遍历 ⑴ 遍历操作的 实现 ⑵ 基于遍历的 其他算法 相互转换 小结: 第 6 章 树和二叉树 * 二叉树小结 1、定义和性质 2、存储结构 3、遍历 4、线索化：线索树 顺序结构 链式结构 二叉链表 三叉链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 中序遍历 后序遍历 先序遍历 赫夫曼树 赫夫曼编码 * void InThreading (BiThrTree p) { if (p) { InThreading( p-lchild ); // 左子树线索化 if ( !p-lchi