判断一棵树是否为完全二叉树

完全二叉树是一种重要的二叉树结构，它可以在数组中很好地表示出来，并且在计算机科学中有着广泛的应用。但是，如何判断一棵二叉树是否为完全二叉树呢？本文将从多个角度进行分析，以帮助读者更好地理解这一问题。

什么是完全二叉树？

首先，我们需要了解完全二叉树的定义。完全二叉树是一种特殊的二叉树结构，其所有层级除最后一层外都必须填满，在最后一层上只能从左到右填充节点。如果一棵树符合这个定义，则它就是完全二叉树。

完全二叉树的判断方法

接下来，我们将介绍几种判断一棵树是否为完全二叉树的方法。

方法一：使用数组表示法

完全二叉树可以被表示成一个数组，当一个节点的下标为i时，它的左子节点和右子节点的下标分别为2i+1和2i+2。因此，我们可以遍历整棵树，并将节点的下标与数组中的元素进行比较，以确定它是否为完全二叉树。

例如，如果一棵树有7个节点，则它应该被表示为一个具有7个元素的数组，其中下标0表示根节点。如果该树是完全二叉树，那么数组中第4个元素的左子节点应该是第8个元素（2×4+1），而右子节点应该是第9个元素（2×4+2）。

方法二：使用递归方法

我们也可以使用递归方法来判断一棵树是否为完全二叉树。具体而言，我们可以从根节点开始，判断它的左子树和右子树是否都是完全二叉树，并检查它们的高度是否相同。如果它们的高度相同，则说明这棵树是一个完全二叉树。

我们可以使用以下递归函数来实现：

1. 如果该节点为空，则返回true

2. 如果只有右子节点为空，则返回false

3. 如果只有左子节点为空，则如果所有的节点都在最后一层或者该节点的右子树是一棵满二叉树，则返回true。否则，返回false。

4. 如果左子节点和右子节点都不为空，则递归地判断左右子树是否都是完全二叉树，且它们的高度相同。

方法三：使用层次遍历

最后，我们也可以使用层次遍历方法来判断一棵树是否为完全二叉树。具体而言，我们可以使用队列进行层次遍历，并检查每一层是否都被填满。

例如，对于以下树：

1

/ \

2 3

/ \ /

4 5 6

我们可以使用队列来进行层次遍历，并检查每一层是否都被填满。在这个例子中，我们首先将根节点1加入到队列中。接下来，我们将它的左子节点2和右子节点3加入到队列中，然后依次访问2、3。在这个点上，我们需要检查3的左子节点6是否为空，如果不为空，则该树不是完全二叉树。否则，我们应该检查后续的所有节点是否都是空节点。