2.5.2-二叉树及其基本性质

2基本数据结构及其运算 2 1数据结构的基本概念2 2线性表及其顺序存储结构2 3线性链表及其运算2 4数组2 5树与二叉树2 6图 2 5树与二叉树 2 5 1树的基本概念2 5 2二叉树及其基本性质2 5 3二叉树的遍历2 5 4二叉树的存储结构2 5 5穿线二叉树2 5 6表达式的线性化 1 什么是二叉树2 二叉树的基本性质3 满二叉树与完全二叉树 2 5 2二叉树及其基本性质 1 什么是二叉树 BinaryTree 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 p116 补充定义 二叉树是n n 0 个结点的有限集 它或者是空集 n 0 或者由一个根结点及两棵不相交的分别称为这个根的左子树和右子树的二叉树组成 二叉树的五种基本形态 a b c d e 二叉树的度为2二叉树是无序树二叉树是有序树 思考 树与二叉树有何区别 二叉树 二叉树和树是两种不同的数据结构 补充 两棵不同的二叉树 补充习题 分别画出具有3个结点的树和3个结点的二叉树的所有不同形态 树 二叉树 无序树 2 二叉树的基本性质 证明 数学归纳法 性质1 在二叉树的第k层上 最多有2k 1 k 1 个结点 21 1 22 1 23 1 24 1 性质2 深度为m的二叉树最多有2m 1个结点 21 1 22 1 2m 1 2m 1 21 1 22 1 23 1 24 1 性质3 在任意一棵二叉树中 度为0的结点 即叶子结点 总是比度为2的结点多一个 n0 度为0的结点个数 叶子结点 n1 度为1的结点个数n2 度为2的结点个数 n0 n1 n2 结点总数 n0 n2 1 射出分支总数 根结点 进入分支总数 根结点 n1 2n2 1 课堂练习 1 若一棵二叉树具有10个度为2的结点 5个度为1的结点 则度为0的结点个数为 11 性质4 具有n个结点的二叉树 其深度至少为 log2n 1其中 log2n 表示取log2n的整数部分 证明 反证法 假设m log2n 1 因为m为整数 所以m log2n log2n 结点总数 m log2n 1 例 具有8个结点的二叉树 其深度至少为 log28 1 4 3 满二叉树与完全二叉树 1 满二叉树 除了最后一层外 每一层上的所有结点都有两个子结点 第k层上的结点数 2k 1 深度为m的满二叉树 共有结点 2m 1 c 深度为4的满二叉树 2 完全二叉树 除了最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 a 深度为3的完全二叉树 b 深度为4的完全二叉树 深度为3的满二叉树 深度为3的完全二叉树 1 2 3 4 5 6 7 1 2 3 4 5 补充习题 一棵高度为h的完全二叉树至少有 个结点 A 2h 1 B 2h 1 1 C 2h 1 D 2h C 补充习题 一棵高度为h的完全二叉树至多有 个结点 A 2h 1 B 2h 1 1 C 2h 1 D 2h A 性质5 具有n个结点的完全二叉树的深度m log2n 1 深度为m的完全二叉树的前m 1层是深度为m 1的满二叉树前m 1层的结点总数为2m 1 1因为深度为m 所以第m层结点数不为0 则2m 1 1 n 2m 12m 1 n 2mm 1 log2n mm 1 log2n 性质6 设完全二叉树共有n个结点如果从根结点开始 按层序 每一层从左到右 用自然数1 2 n给结点进行编号 则对于编号为k k 1 2 n 的结点有以下结论 1 若k 1 则该结点是根结点 无父结点若k 1 则该结点的父结点编号为INT k 2 如何确定一个结点的父结点 2 若2k n 则编号为k的结点的左子结点编号为2k 否则该结点无左子结点 显然也没有右子结点 如何确定一个结点的