北京师范大学《数据结构——C语言描述》教学课件：第六章 树和二叉树

第六章树和三叉树

第六章 树和二叉树

第六 树 章 树的AD定义 从关系约束的角度定义树 以递归形式定义树 树和二叉树 相关术语 根结点-叶结点-非叶结点 父结点-子结点 祖先结点-子孙结点 结点的度-树的度 路径-路径长度 有向树-无向树 结点的层数 树的深度

第 六 章 树 和 二 叉 树 一、树 ◼ 树的ADT定义 – 从关系约束的角度定义树 – 以递归形式定义树 ◼ 相关术语 – 根结点-叶结点-非叶结点 – 父结点-子结点 – 祖先结点-子孙结点 – 结点的度-树的度 – 路径-路径长度 – 有向树-无向树 – 结点的层数 – 树的深度

第六 二、二叉树 章 ■二叉树的定义 度不大于2的有向树称为二叉树。 树,相关术语 和二叉树 左子结点-右子结点

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的定义 – 度不大于2的有向树称为二叉树。 ◼ 相关术语 – 左子结点-右子结点

第六 二、二叉树 章 二叉树的性质 第层最多有2个结点 树和二叉树 深度为h,则最少有h个结点,最多有2h-1个结点 结点数为n,则深度最多为n,最少为r1og(n+1)1 满二叉树 完全二叉树 7)(8)(9)(10 (12)(13

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的性质 第i层最多有2i个结点 深度为h，则最少有h个结点，最多有2h-1个结点 结点数为n，则深度最多为n，最少为┌log(n+1)┐ 满二叉树 完全二叉树 7 8 9 10 11 12 13 3 4 5 6 1 2 0

第六 二、二叉树 章 二叉树的性质 对完全二叉树,结点的左子结点序号为2i+1 树和二叉树 对完全二叉树,结点的右子结点序号为2i+2 对完全二叉树,结点的父结点序号为L(-1)/2 8 9)(10(11)①2)(13

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的性质 对完全二叉树，结点i的左子结点序号为2i+1 对完全二叉树，结点i的右子结点序号为2i+2 对完全二叉树，结点i的父结点序号为└(i-1)/2┘ 7 8 9 10 11 12 13 3 4 5 6 1 2 0

第 叉树 章 二叉树的实现 二叉链结构 父链结构 三叉链结构 树 ∧∧ g ∧∧ ∧∧ CODING

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的实现 – 二叉链结构 – 父链结构 – 三叉链结构 a b c e f g h i d CODING a b ∧ c d ∧ ∧ e f ∧ i ∧ ∧ h ∧ ∧ g ∧ ∧

第六 二、二叉树 章 ■二叉树的遍历 前序遍历:根左子右子 abdcegjkhfi 树和二叉树 中序遍历:左子根右子 dbajgkehcfi 后序遍历:左子右子根 dbjkgheifca 层次遍历:逐层 abcdefghi ik d CODING

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的遍历 – 前序遍历：根 左子 右子 – 中序遍历：左子 根 右子 – 后序遍历：左子 右子 根 – 层次遍历：逐层 a b c e f g h i d j k abdcegjkhfi dbajgkehcfi dbjkgheifca abcdefghijk CODING

第六 二、二叉树 章 ■二叉树的遍历 应用举例:遍历与输入二叉树 树和二叉树 a a C e g abd###ceg##h##f#立## CoD工NG

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的遍历 – 应用举例：遍历与输入二叉树 abd###ceg##h##f#i## a b c e f g h i d a b c e f g h i d CODING

第六 二、二叉树 章 二叉树的遍历 应用举例:二叉树的撤销 树和二叉树 CoD工NG

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的遍历 – 应用举例：二叉树的撤销 CODING

第六 二、二叉树 章 二叉树的遍历 遍历序与二叉树的对应 树和二叉树 ■前序遍历序+中序遍历序唯一确定二叉树 前序遍历序: abdceghfi 中序遍历序: dbagehcfi

第 六 章 树 和 二 叉 树 二、二叉树 ◼ 二叉树的遍历 – 遍历序与二叉树的对应 ◼ 前序遍历序+中序遍历序唯一确定二叉树 a b c e f g h i d 前序遍历序：abdceghfi 中序遍历序：dbagehcfi