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

二叉树是计算机科学中常用的一种数据结构，它由许多节点组成，每个节点最多有两个子节点。而完全二叉树和满二叉树则是二叉树的两种特殊形式。本文将从多个角度分析完全二叉树和满二叉树的区别。

1.定义

完全二叉树的定义为：在一颗二叉树中，如果除了最后一层节点不满，其它每一层的节点数都达到了最大值，并且最后一层的节点都集中在该层最左边的若干位置上，那么这棵二叉树就是完全二叉树。

满二叉树的定义为：在一棵二叉树中，如果除了叶子节点外，每个节点都有左右两个子节点，并且所有的叶子节点都在同一层上，那么这棵二叉树就是满二叉树。

2.单一特征

完全二叉树和满二叉树在单一特征上有所不同。一颗完全二叉树的深度为h，其节点数n的下界为2^h-1，上界为2^(h+1)-1，而在一棵深度为h的满二叉树中，它的节点数恰好为2^(h+1)-1。

3.节点分布

在完全二叉树中，除最后一层外，每个节点都有两个子节点。而在最后一层，只有左侧一段连续的节点被使用，而右侧的节点都为空。

而在满二叉树中，每个非叶子节点都有左右两个子节点。在任何一层中，如果有节点缺失，那么缺失的一定是右侧的节点。

4.存储空间

对于每一个节点，除了存放数据外，还需要存储指向其左右子节点的指针或引用。因此，在相同高度的情况下，相比较于满二叉树，完全二叉树需要更少的存储空间，因为在完全二叉树中有许多空节点，而在满二叉树中则没有。

5.遍历方式

在对完全二叉树、满二叉树进行遍历时，也有所不同。

对于完全二叉树，由于每层除最后一层外都有两个子节点，可以通过前序遍历、中序遍历、后序遍历、层次遍历等方式来遍历。

但是在满二叉树中，由于每个非叶子节点都有左右两个子节点，通过前序遍历、中序遍历、后序遍历等方式遍历都可以，但是层次遍历会使遍历的效率下降。