树与二叉树B分析.ppt

* 第6章 树和二叉树（ Tree Binary Tree ） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 （本章及本课程的重点） 上机内容： Huffman 编/译码器的设计与实现 （实验要求参见严题集P149 ） * 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 （二叉树的运算见下一节） * 2. 二叉树的性质 (3+2) 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k0）。 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 课堂练习： 1. 树Ｔ中各结点的度的最大值称为树Ｔ的 。 Ａ) 高度 Ｂ) 层次 Ｃ) 深度 Ｄ) 度 2.深度为k的二叉树的结点总数，最多为 个。 Ａ)２k-1 Ｂ) log2k Ｃ) ２k－１ Ｄ)２k 3. 深度为9的二叉树中至少有 个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1 √ √ √ * 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 性质4: 具有n个结点的完全二叉树的深度必为?log2n?＋1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n≤2k-1 或2k-1≤n2k 三边同时取对数，于是有：k-1≤log2nk 因为k是整数，所以k= ?log2n? +1 可根据归纳法证明。 * 课堂讨论： Q1：满二叉树和完全二叉树有什么区别？ A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。 满二叉树是完全二叉树的一个特例。 Q3: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 489 488 1 0 Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？ A1：因为只有这两种形式可以实现顺序存储！ 由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。 A3：易求出总层数和末层叶子数。总层数k=?log2n?＋1 =10; 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为1000-511=489个。 * 请注意叶子结点总数≠末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：末层的489个叶子只占据了上层的245个结点（?489/2? ) 上层（k=9)右边的0度结点数还有29-1-245=11个！ 另一法：可先求2度结点数,再由此得到叶子总数。 首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉） 另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2， （共有?489/2?＝244个）。 所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个； 总叶子数＝2度结点数＋1=500个。 第i层上的满结点数为2i-1 所以， 全部叶子数＝489(末层)＋11(k-1层)=500个。 度为2的结点＝叶子总数－1=499个。 * 4. 二叉树的存储结构 一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 A B C D E F G H I [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C G E I D H F 问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。 T[0]一般不用 * 讨论