二叉树 计1.二叉树的定义 二叉树是一个由n(n>0)个结点构成的 有限集合,它或者为空树,或者是由一个根 结点和两个分别被称为左子树和右子树的互 不相交的子集构成的,其左、右子树也是二 叉树
计 算 机 软 件 基 础 三. 二叉树 1. 二叉树的定义 二叉树是一个由n（n≥0）个结点构成的 有限集合，它或者为空树，或者是由一个根 结点和两个分别被称为左子树和右子树的互 不相交的子集构成的，其左、右子树也是二 叉树。
二叉树的特点 A 1)度小于等于2,即 树中不存在度大于2的 B 结点; (2)有序树,即每个 结点的子树有左右之分, G H 不能交换 二叉树示意图
计 算 机 软 件 基 础 B C D E G F H A 二叉树示意图 ❖ 二叉树的特点 （1）度小于等于2，即 树中不存在度大于2的 结点； （2）有序树，即每个 结点的子树有左右之分， 不能交换。
2.二叉树的性质 (1)二叉树的第层上至多有21个结点。 (2)深度为k的二叉树的结点总数至多为2k-1 个。 (3)若一棵二叉树上度为0(叶子)和度为2的 结点数分别为nn和n2, 则:n=n2+1
计 算 机 软 件 基 础 2. 二叉树的性质 （1）二叉树的第i层上至多有2 i-1个结点。 （2）深度为k的二叉树的结点总数至多为2 k -1 个。 （3）若一棵二叉树上度为0（叶子）和度为2的 结点数分别为n0和n2， 则：n0=n2+1
3.特殊的二叉树 (1)满二叉树 若一棵二叉树的深度为k,其结点总数为2k-1 个,则称此二叉树为满二叉树。 B 满二叉树示例 E F G
计 算 机 软 件 基 础 3. 特殊的二叉树 （1）满二叉树 若一棵二叉树的深度为k，其结点总数为2 k -1 个，则称此二叉树为满二叉树。 B C D E G A F 满二叉树示例
(2)完全二叉树 若一棵深度为k、具有n个结点的二叉树,能 够与一棵同深度的满二叉树中编号从1到n的结 点(从上到下,从左到右编号)相对应,则称 此二叉树为完全二叉树。 思考 A 深度为3的完全 二叉树有几种 B 形态? E 完全二叉树示例
计 算 机 软 件 基 础 （2）完全二叉树 若一棵深度为k、具有n个结点的二叉树，能 够与一棵同深度的满二叉树中编号从1 到n的结 点（从上到下，从左到右编号）相对应，则称 此二叉树为完全二叉树。 B C D E A 完全二叉树示例 思考： 深度为3的完全 二叉树有几种 形态？