第六章树和三叉树
第六章 树和二叉树
第六 树 章 树的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