《树和森林》精选课件.ppt

6.4 树和森林 6.4.1 树的存储结构 6.4.1 树和森林与二叉树的转换 树转二叉树举例： 讨论2：二叉树怎样还原为树？ 森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树） 讨论4：二叉树如何还原为森林？ 6.4.2 树和森林的存储方式 例如： 6.4.3 树和森林的遍历 森林的遍历 附：二叉树若干典型算法 附2：层次遍历算法(需要利用队列) 附3：判别给定二叉树是否为完全二叉树 附4：中序遍历的非递归算法(或称迭代算法)见教材P131 6.5 Huffman树及其应用 一、 Huffman树（最优二叉树） 树的带权路径长度如何计算？ 例: 有4个叶子结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 1. 构造Huffman树的步骤（即Huffman算法）： 具体操作步骤： 求以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树，并求出其带权路径长度WPL。 2. 构造Huffman树的基本思想： 二、Huffman编码 step2：按左“0”右“1” 对Huffman树的所有分支编号 如何编程实现Huffman编码？ 如何编程实现Huffman编码？ (续前)再求出n个字符的Huffman编码HC Huffman编码举例 小结：哈夫曼树及其应用 本 章 小 结 作业 一、基础知识题 图6.1 二叉树例子 二、算法设计题 1. 一个二叉树以链式结构存储，分别给出求二叉树结点总数和叶子结点总数的算法。 3. 设计一个算法将一个以链式存储结构的二叉树，按顺序方式存储到一维数组中。 例 w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 8 7 15 14 29 23 3 5 8 11 11 3 5 8 19 14 29 23 8 7 15 11 3 5 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42 29 14 8 7 15 29 58 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 请注意：哈夫曼树样式不惟一！ typedef struct { int data; int pa，lc，rc; }BithrNode; Huffman算法实现 一棵有n个叶子结点的Huffman树有2n-1个结点 采用顺序存储结构——一维结构数组结点类型定义 算法： lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 0 0 0 7 5 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (1) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 0 0 7 5 2 4 6 0 0 0 0 0 0 4 0 0 0 0 5 5 0 0 0 k x1=3,x2=4 m1=2,m2=4 (2) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6 11 0 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k x1=2,x2=5 m1=5,m2=6 (3) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0 0 0 4 5 6 7 6 5 5 6 7 0 k x1=1,x2=6 m1=7,m2=11 (4) 例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码（如二进制编码） 令d=00，i=01，a=10，n=11，则： WPL1＝2bit×(7＋5＋2＋4）＝36 法2：不等长编码（如Huffman编码） 令d=0;i=10,a=110,n=111，则： 明确：要实现Huffman编码，就要先构造Huffman树 讨论：Huffman树有什么用？ 权值大的结点用短路径，权值小的结点用长路径。 WPL最小的树 频度高的信息用短码，反之用长码，传输效率肯定高！ WPL2=1bit×7＋2bit×5+3bit×(2+4)=35 最小冗余编码、信息高效传输 （1）由于Huffman树的WPL最小，说明编码所需