Question

完全二叉树与满二叉树的区别是什么？

Answer 1

完全二叉树与满二叉树的区别为：性质不同、包含不同、叶子结点不同。

一、性质不同

1、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

2、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

二、包含不同

1、完全二叉树：完全二叉树包含满二叉树。

2、满二叉树：满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。 

三、叶子结点不同

1、完全二叉树：完全二叉树的叶子结点可出现在最下层或次下层。

2、满二叉树：满二叉树的叶子结点只能出现在最下层和次下层。