实用数据结构基础(第三版)课程PPT第7章树和二叉树.ppt

性质 4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n? +1 课堂练习题 树T有n个结点且结点的度均为k或者0，则树中的叶子结点总数为_____________。 （广东工业大学05年考研试题） 预习题 1.二叉树的存储方法有哪几种？ 2.什么叫二叉树的遍历？ 3.先左后右的二叉树遍历算法有哪几种？ 预习题 什么叫二叉树的线索化？为什么要线索化？ 如何把一棵普通的m叉树转换为二叉树表示？ 预习题 1.如何用算法求二叉树的叶子结点个数？ 2.如何用算法求二叉树的高度？ 3.什么叫最优二叉树（哈夫曼树）？ 【例7-10】画出（A+（B-C））/（（D+E）*（F+G-H））的标识符树，并求它的前序序列和后序序列。 / A - C B + D E + * F - H G + 前序序列：/ + A–B C * + D E–+ F G H 后序序列：A B C–+ D E + F G + H–* / 动画演示 7-6 哈夫曼树极其应用 哈夫曼（Haffman）树，也称最优二叉树。 7-6-1 哈夫曼树的引入 1．几个术语 （1）路径长度——从树中的一个结点到另一个结点之间的分支构成两个结点间的路径，路径上的分支数目，称作路径长度。 （2）树的路径长度——从树根到每个结点的路径长度之和称为树的路径长度。 （3）结点的带权路径长度——从该结点到树根之间路径长度与该结点上权的乘积。 （4）树的带权路径长度——树中所有叶子结点的带权路径长度之和，称为树的带权路径长度。 （5）最优二叉树——带权路径长度最小的二叉树，称为最优二叉树。 2．如何求树的带权路径长度？ 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度（WPL），记为： ? 其中： Wk——为第k个叶结点的权值； L k ——为第k个叶结点到根结点的路径长度。 【例7-11】 设给定权值分别为2，3，5，9的四个结点，图7-30构造了5个形状不同的二叉树。请分别计算它们的带权路径长度。 五棵树的带权路径长度分别为： （a）WPL＝2×2＋3×2＋5×2＋9×2＝38 （b）WPL＝2×3＋3×3＋5×2＋9×1＝34 （c）WPL＝2×2＋3×3＋5×3＋9×1＝37 （d）WPL＝9×3＋5×3＋3×2＋2×1＝50 （e）WPL＝2×1＋3×3＋5×3＋9×2＝44 五个图的叶结点具有相同权值，由于其构成的二叉树形态不同，则它们的带权路径长度也各不相同。其中以图(b)的带权路径长度最小，它的特点是权值越大的叶结点越靠近根结点，而权值越小的叶结点则远离根结点，事实上它就是一棵最优二叉树。由于构成最优二叉树的方法是由D · Haffman 最早提出的，所以又称为哈夫曼树。 3．为什么要使用哈夫曼树 在分析一些决策判定问题的时候，利用哈夫曼树，可以获得最佳的决策算法。 例如，要编制一个将百分制数（n）转换为五级分制的程序。这是一个十分简单的程序，只要用简单的条件选择语句即可完成。如： if (n60) b=E; else if (n70) b=D else if (n80) b=C else if (n90) b=B else b=A; 图7-31(a) 上述判定过程可以用图7-31（a）的判定树来表示 图7-31(b) 分数 n 0~59 60~69 70~79 80~89 90~100 比例数 5% 15% 40% 30% 10% 等级 b E D C B A 表7-1：学生成绩分布表 图7-31(c) 如果以百分比值5、15、40、30、10为权构造一棵有五个叶子结点构成的哈夫曼树，则可得到图7-31（b）所示的判定树，它使大部分数据经过较少的比较次数，就能得到换算结果。由于每个判定框都有两次比较，将这两次比较分开，就可以得到如图7-31 (c)所示的判定树，按此判定树编写出的程序，将大大减少比较的次数，从而提高运算的速度。 7-6-2 哈夫曼树的建立 1．哈夫曼树构成的基本思想是： （1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合: F＝{T1，T2，…，Tn}； （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建