满二叉树 如果一棵二叉树的任何结点,或者是树叶, 或者恰有两棵非空子树,则此二叉树称作 满二叉树 C B FGⅡI 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 满二叉树 ◼ 如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作 满二叉树
完全二叉树 若一颗二叉树 最多只有最下面的两层结点度数可以小于2 最下面一层的结点都集中在该层最左边的若干位置上 则称此二叉树为完全二叉树 在许多算法和算法分析中都明显地或隐含地用到 全二叉树的概念 北京大学信息学院 版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 完全二叉树 ◼ 若一颗二叉树 ◼ 最多只有最下面的两层结点度数可以小于2 ◼ 最下面一层的结点都集中在该层最左边的若干位置上， 则称此二叉树为完全二叉树 ◼ 在许多算法和算法分析中都明显地或隐含地用到完 全二叉树的概念
完全二叉树 C B oC G DE FGH IJ K 北京大学信息学院 版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 完全二叉树
打充二叉树 ■当二叉树里出现空的子树时,就增加新的、特 殊的结点—空树叶 对于原来二叉树里度数为1的分支结点,在它下面 增加一个空树叶 对于原来二叉树的树叶,在它下面增加两个空树叶 ■扩充的二叉树是满二叉树,新增加的空树叶 (外部结点)的个数等于原来二叉树的结点(内 部结点)个数加1 北京大学信息学院 版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 ◼ 当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶 ◼ 对于原来二叉树里度数为1的分支结点，在它下面 增加一个空树叶 ◼ 对于原来二叉树的树叶，在它下面增加两个空树叶 ◼ 扩充的二叉树是满二叉树，新增加的空树叶 (外部结点)的个数等于原来二叉树的结点(内 部结点)个数加1
打充二叉树 wan zol wil yO wen yim xul yu m wu xem yonR 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 扩充二叉树