数据结构第6章树和二叉树.ppt

1 第六章树和二叉树 6 1树的类型定义 6 2二叉树的类型定义和实现 6 3遍历二叉树和线索二叉树 6 4树和森林 6 5Huffman树与Huffman编码 2 对比树型结构和线性结构的结构特点 第一个数据元素 无前驱 最后一个数据元素 无后继 其它数据元素 一个前驱 一个后继 根结点 无前驱 多个叶子结点 无后继 其它数据元素 一个前驱 多个后继 3 6 1树的类型定义 树是n n 0 个结点的有限集D 当n 1时 1 有一个特定的结点root被称为根 结点 2 除根以外的结点被分成m m 0 个不相交的有限集T1 T2 Tm 其中每个集合又是一棵树 称为根的子树 4 结点 结点的度 树的度 叶子结点 分支结点 数据元素 若干指向子树的分支 分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点 树的基本术语 从根到结点的 路径 由从根到该结点所经分支和结点构成 5 孩子结点 结点的子树的根称为该结点的孩子双亲结点 B结点是A结点的孩子 则A结点是B结点的双亲兄弟结点 同一双亲的孩子之间互称兄弟堂兄弟结点 其双亲在同一层的结点互称堂兄弟祖先结点 从根到该结点所经分支上的所有结点子孙结点 以某结点为根的子树中任一结点都称为该结点的子孙 6 孩子结点双亲结点兄弟结点堂兄弟结点祖先结点子孙结点 结点的层次 树的深度 假设根结点的层次为1 第L层结点的子树的根结点层次为L 1 树中叶子结点所在的最大层次 7 有序树 子树之间存在确定的次序关系 最左边子树的根称为第一个孩子 最右边子树的根称为最后一个孩子 森林 是m m 0 棵互不相交的树的集合 无序树 不考虑子树的顺序 8 任何一棵非空树是一个二元组Tree root F 其中 root被称为根结点F被称为子树森林 森林和树之间的联系 一棵树去掉根后 其子树构成一个森林 一个森林增加一个根结点成为树 9 A B E F K L C G D H I J M T1 T3 T2 树根 广义表 树的表示方法 层次结构 1 嵌套集合 2 广义表 3 凹入表示法 10 ADTTree 数据对象D D是具有相同特性的数据元素的集合 数据关系R 若D为空集 则称为空树 若D中仅含一个数据元素 则关系R为空集 否则R H 1 在D中存在唯一的称为根的数据元素root 它在关系H下无前驱 2 当n 1时 其余数据元素可分为m m 0 个互不相交的 非空 有限集T1 T2 Tm 其中每一个子集本身又是一棵符合本定义的树 称为根root的子树 每一棵子树的根xi都是根root的后继 即 H i 1 2 m 树的抽象数据类型定义如下 11 基本操作 结构初始化 InitTree 初始条件 树T存在 操作结果 销毁树T 12 引用型操作 TreeEmpty T 初始条件 树T存在 操作结果 若T为空树 则返回TRUE 否则返回FALSE TreeDepth T 初始条件 树T存在 操作结果 返回T的深度 Root T 初始条件 树T存在 操作结果 返回T的根 13 Value T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 返回cur e的值 Parent T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非根结点 则返回它的双亲 否则返回 空 LeftChild T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非叶子结点 则返回它的最左孩子 否则返回 空 14 RightSibling T cur e 初始条件 树T存在 cur e是T中某个结点操作结果 若cur e有右兄弟 则返回它的右兄弟 否则返回 空 TraverseTree T visit 初始条件 树T存在 visit是对结点操作的应用函数操作结果 按某种次序对T的每个结点调用函数visit 一次且至多一次 一旦visit 失败 则操作失败 加工型操作 Assign 初始条件 树T存在 cur e是T中某个结点 操作结果 结点cur e赋值为value 15 ClearTree 初始条件 树T存在 p指向T中某个结点 1 i p指结点的度 操作结果 删除T中p所指结点的第i棵子树 ADTTree 16 定义或为空树 或是由一个根结点和两棵互不相交的左子树 右子树构成 并且左 右子树本身也是二叉树 特性二叉树中每个结点最多有两棵子树 二叉树每个结点的度小于等于2子树有左右之分 不能颠倒 有序树二叉树是递归结构 在二叉树的定义中又用到了二叉树的概念 6 2二叉树的类型定义和实现 17 二叉树与度为2的树相同吗 为什么 答案 二叉树与度为2的树不相同 1 度为2的树不能为空树 二叉树可以为空树 2 度为2的树从形式上看与二叉树很相似 但它的子树是无序的 而二叉树是有序的 即 在一般树中若某结点只有一个孩子 就无需区分其左右次序 而在二叉树中即使是一个孩子也有左右之分 18 a b两棵二叉树相同吗 为什么 a b 答案 不相同 因为 二叉树是有序树 而a和b两棵二叉树的左右子树不同 19 二叉树的五种基本形态 空树 只含根结点 右子树为空树 左子树为空树 左右子树均不为空树 20 二叉树的抽象数据类型定义如下 ADTBinaryTree 数据对象 D是具有相同特性的数据元素的集合 数据关系 若D为空集 则称为空树 否则 1 在D中存在唯一的称为根的数据元素root 2 当n 1时 其余结点可分为2个互不相交的有限集T1 T2 其中每一棵子集本身又是一棵符合本定义的二叉树 T1称为根root的左子树 T2称为根root的右子树 21 基本操作 初始化操作 InitBiTree T 操作结果 构造空二叉树T DestroyBiTree 初始条件 二叉树T存在 操作结果 销毁二叉树T 结构销毁操作 CreateBiTree T definition 初始条件 definition给出二叉树T的定义 操作结果 按definition构造二叉树T 22 引用型操作 Root T 初始条件 二叉树T存在 操作结果 返回二叉树T的根结点 Parent T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 若e是T的非根结点 则返回它的双亲 否则返回 空 Value T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的值 23 引用型操作 续 LeftChild T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的左孩子 若e无左孩子 则返回 空 RightChild T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的右孩子 若e无右孩子 则返回 空 24 引用型操作 续 RightSibling T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的右兄弟 若e是其双亲的右孩子或无右兄弟 则返回 空 LeftSibling T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的左兄弟 若e是其双亲的左孩子或无左兄弟 则返回 空 25 引用型操作 续 BiTreeEmpty T 初始条件 二叉树T存在 操作结果 若T为空二叉树 则返回TRUE 否则返回FALSE BiTreeDepth T 初始条件 二叉树T存在 操作结果 返回T的深度 26 引用型操作 续 PreOrderTraverse T Visit 根左右初始条件 二叉树T存在 visit是对结点操作的应用函数 操作结果 先序遍历T 对每个结点调用函数visit一次且仅一次 一旦visit 失败 则操作失败 InOrderTraverse T Visit 左根右初始条件 二叉树T存在 visit是对结点操作的应用函数 操作结果 中序遍历T 对每个结点调用函数Visit一次且仅一次 一旦visit 失败 则操作失败 27 引用型操作 续 PostOrderTraverse T Visit 左右根初始条件 二叉树T存在 visit是对结点操作的应用函数 操作结果 后序遍历T 对每个结点调用函数visit一次且仅一次 一旦visit 失败 则操作失败 LevelOrderTraverse T Visit 初始条件 二叉树T存在 visit是对结点操作的应用函数 操作结果 层序遍历T 对每个结点调用函数visit一次且仅一次 一旦visit 失败 则操作失败 28 加工型操作 InsertChild T p LR c 初始条件 二叉树T存在 p指向T中某个结点 LR为0或1 非空二叉树c与T不相交且右子树为空 操作结果 根据LR为0或1 插入c为T中p所指结点的左或右子树 p所指结点原有左或右子树成为c的右子树 29 加工型操作 DeleteChild 初始条件 二叉树T存在 p指向T中某个结点 LR为0或1 操作结果 根据LR为0或1 删除T中p所指结点的左或右子树 30 加工型操作 续 ClearBiTree T 初始条件 二叉树T存在 操作结果 将二叉树T清为空树 ADTBinaryTree Assign T e value 初始条件 二叉树T存在 e是T中某个结点 操作结果 结点e赋值为value 31 性质1在二叉树的第i层上至多有2i 1个结点 i 1 证明 用归纳法证明 当i 1时 只有根结点1个结点 2i 1 20 1 结论成立 假设 当i j时 命题成立 即第j层最多有2j 1个结点 当i j 1时 即第j 1层 第j 1层的结点是由第j层的孩子组成 又 二叉树上每个结点最多有两个孩子 第j 1层最多有2j 1 2 2j 2 j 1 1个结点 结论成立 二叉树的重要特性 32 性质2深度为k的二叉树上至多含2k 1个结点 k 1 证明 由性质1 第i层至多有2i 1个结点 深度为k的二叉树 最多共有20 21 2k 1个结点而20 21 2k 1 2k 1 公式 1 x 1 x1 x2 xn 1 1 xn 33 性质3对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 证明 设二叉树上总结点数为n 度为1的结点数为n1 则n n0 n1 n2 设B为二叉树中分支总数 除根结点外 每个结点都有一个分支进入 则B n 1 二叉树中所有分支是由度为1的结点和度为2的结点射出的 度为1的结点射出一条边 度为2的结点射出2条 B n1 2n2 由 可得 n0 n2 1 34 满二叉树 深度为k 且有2k 1个结点的二叉树 特点 每一层上的结点数都是最大数目 结点层序编号方法 从根结点起自上而下逐层 层内自左至右 对二叉树的结点进行连续编号 两类特殊的二叉树 35 完全二叉树 一棵深度为k有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 称之为完全二叉树 特点 叶子结点只可能在层次数最大的两层上出现 只有最下一层的结点数可能未达到最大值 对任一结点 如果其右子树的最大层次为L 则其左子树的最大层次为L或L 1 完全二叉树结点数2k 1 1 n 2k 1满二叉树一定是完全二叉树 反之不成立 36 是完全二叉树吗 37 Q1 满二叉树和完全二叉树有什么区别 答案 满二叉树是叶子一个也不少的树 而完全二叉树虽然前n 1层是满的 但最底层却允许在右边缺少连续若干个结点 满二叉树是完全二叉树的一个特例 Q2 为什么要研究满二叉树和完全二叉树这两种特殊形式 答案 因为只有这两种形式可以实现顺序存储 38 性质4具有n个结点的完全二叉树的深度为 log2n 1 证明 设完全二叉树的深度为k 根据第二条性质 对深度为k的满二叉树共有2k 1个结点 深度为k 1的满二叉树共有2k 1 1个结点 n个结点的完全二叉树 深度为k 2k 1 1 n 2k 1 即2k 1 n 2k k 1 log2n k又 k为深度 只能是整数 k log2n 1 说明 x 取下界 即取不超过x的最大整数 39 Q3 一棵深度为6的满二叉树有个分支结点和个个叶子 答案 满二叉树没有度为1的结点 所有分支结点都是二度结点 前5层结点都为分支结点 共25 1 31个 或利用公式n0 n2 1 n1 n2 0 n2 n0 1 31叶子结点都在第6层 共26 1 32 一棵具有257个结点的完全二叉树 它的深度为 答案 利用公式k log2n 1 log2257 1 9 一棵含有n n 1 个结点的k叉树 可能达到的最大深度为 最小深度为 答案 当k 1 单叉树 时应该最深 深度 n 层 当k n 1 n 1叉树 时应该最浅 深度 2 层 31 32 9 2 n 40 Q4 设一棵完全二叉树具有1000个结点 则它有个叶子结点 有个度为2的结点 有个结点只有非空左子树 有个结点只有非空右子树 489 1 0 答案 易求出总层数和末层叶子数 总层数k log2n 1 10 210 1024且前9层总结点数为29 1 511 完全二叉树的前k 1层肯定是满的 所以末层叶子数为1000 511 489个 由于最后一层叶子数为489个 是奇数 说明有1个结点只有非空左子树 而完全二叉树中不可能出现非空右子树 0个 41 请注意 叶子结点总数 末层叶子数 还应加上第k 1层 靠右边 的0度结点个数 分析 末层的489个叶子只占据了上层的245个结点 489 2 上层 k 9 右边的0度结点数还有29 1 245 11个 第i层上的满结点数为2i 1 所以 全部叶子数 489 末层 11 k 1层 500个 度为2的结点 叶子总数 1 499个 n0 n2 1 42 另一法 可先求2度结点数 再由此得到叶子总数 首先 前k 2层的28 1 255 个结点肯定都是2度的 完全二叉 另外 末层叶子 刚才已求出为489 所对应的双亲也是度 2 共有 489 2 244个 所以全部2度结点数为255 k 2层 244 k 1层 499个 总叶子数 2度结点数 1 500个