数据结构与算法——树讲述.ppt

编制一个将百分制转换成五分制的程序。可用二叉树描述判定过程。 a ? 80 a ? 90 不及格 良好 中等 及格 优秀 a ? 60 a ? 70 例 在求得某些判定问题时，利用Huffman树获得最佳判定算法。 6.7 Huffman树及其应用 其判定过程: 转换一个分数所需的比较次数= 从根到对应结点的路径长度 转换10000个分数所需的总比较次数= 10000 ? (0.05 ? 1+0.15 ? 2+0.4 ? 3+0.3 ? 4+0.1 ? 4） 二叉树的 带权路径长度 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下： a ? 80 a ? 90 不及格 良好 中等 及格 优秀 a ? 60 a ? 70 例 6.7 Huffman树及其应用 树 和 二 叉 树 先根遍历 中根遍历 后根遍历 层次遍历 树的存储结构 树和森林的转换与二叉树的转换 树和森林的遍历 树的ADT 逻辑结构 存储结构 树和森林 树的应用 Huffman树 Huffman编码 判定过程 二叉树 二叉树逻辑结构 二叉树存储结构 二叉树基本性质 二叉树的遍历 二叉树的应用 线索二叉树 顺序存储 二叉链表 本章小结 熟练掌握二叉树的结构特性，了解相应的证明方法。（完全二叉树、满二叉树、哈夫曼树） 熟悉二叉树的各种存储结构的特点及适用范围。 　熟练掌握二叉树的遍历二叉树方法及二叉树的构造方法。 熟练掌握各种遍历策略的递归算法和主要的非递归算法； 本章小结 B C D E F G H I J K 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。 森林由三部分构成： 6.6.3 树和森林的遍历 知识回顾 int TreeDepth(CSTree T) {//T是森林 if(!T) return 0; else { h1 = TreeDepth( T-firstchild ); //森林中第一棵树的子树森林的深度 h2 = TreeDepth( T-firstbrother); //森林中其他子树构成的森林的深度，与T在同一层 } } // TreeDepth return(max(h1+1, h2)); 求树的深度的算法： 6.6.3 树和森林的遍历 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用 HUFFMAN编码又称哈夫曼编码，是一种可变长编码方式，是由美国数学家David Huffman1952年在麻省理工攻读博士时所发明的; 6.7 Huffman树及其应用 编码的原理： (1)将使用次数多的代码转换成长度较短的代码; (2)保持编码的唯一可解性。 Huffman介绍 哈夫曼编码的理论依据：是变字长编码理论; 在变字长编码中，按编码输入信息符号出现的统计概率，给输出码字分配以不同的字长; Huffman 编码是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。 Huffman介绍 6.7 Huffman树及其应用 Huffman树是二叉树的一种特殊转化形式。Huffman树又称最优二叉树，是一种带权路径长度最短的二叉树。 结点的路径长度：从根结点到该结点的路径上分支的数目; 树的路径长度：树中每个结点的路径长度之和。 在结点数相同的条件下，完全二叉树是路径最短的二叉树。 非完全二叉树 完全二叉树 1 2 3 4 6 2 3 4 7 6 5 8 1 Huffman树的相关概念 6.7 Huffman树及其应用 树的带权路径长度定义： 树中所有叶子结点的带权路径长度之和 WPL(T) = ?wklk (对所有叶子结点)。 “最优树”或Huffman树。 在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”或Huffman树。 Huffman树的相关概念 6.7 Huffman树及其应用 2 4 5 7 2 4 7 5 7 5 2 4 (a) WPL=36 (b) WPL=46 (c) WPL=35 Huf