Question

满二叉树和完全二叉树的区别

Answer 1

满二叉树和完全二叉树的区别：

完全二叉树是深度为k，有n个结点的二叉树，当且仅当其每一个结点，都与深度为k的满二叉树中编号从1至n的结点逐一对应的二叉树。完全二叉树的叶子结点只可能在层次最大的两层上出现。

对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或者I加1。满二叉树是一棵深度为k，且有2的k次方减1个节点的二叉树。满二叉树的每一层上的结点数都是最大结点数。

满二叉树与完全二叉树的关系：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树是一种叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左边的特殊二叉树。

当树的深度相同时，若对树的结点按从上至下、从左到右的顺序进行编号，则在两种树上同一个位置上的结点的编号相同。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。