★几种特殊形式的二叉树 今满二叉树 ●定义:一棵深度为k且有2←-1个结点的二叉树称为 特点:每一层上的结点数都是最大结点数 今完全二叉树 定义:深度为k,有n个结点的二叉树当且仅当其每一个结点 都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称为 ●特点 ◆叶子结点只可能在层次最大的两层上出现 ◆对任一结点,若其右分支下子孙的最大层次为则其左 分支下子孙的最大层次必为或|+1 ●性质 ◆性质4:具有n个结点的完全二叉树的深度为bog2n+1几种特殊形式的二叉树 ❖满二叉树 ⚫定义： 一棵深度为 且有2 −1个结点的二叉树称为~ k k ⚫特点：每一层上的结点数都是最大结点数 ❖完全二叉树 ⚫定义：深度为k，有n个结点的二叉树当且仅当其每一个结点 都与深度为k的满二叉树中编号从1至n的结点一一对应时， 称为~ ⚫特点 ◆叶子结点只可能在层次最大的两层上出现 ◆对任一结点，若其右分支下子孙的最大层次为l，则其左 分支下子孙的最大层次必为l 或l+1 ⚫性质 ◆性质4： 具有n个结点的完全二叉树的深度为log 2 n +1