完全二叉树的判定算法

在二叉树中，有一种特殊的种类，即完全二叉树。它的定义是一棵二叉树，如果除了最后一层节点不满，其它每一层的节点数都是最大节点数，最后一层从左到右排列。判断一棵给定的二叉树是否为完全二叉树是一道非常基础而重要的算法题。本文将从多个角度分析完全二叉树的判定算法。

1. 完全二叉树的性质

为了更好地理解完全二叉树，我们可以先来探讨一下完全二叉树的一些性质：

- 如果完全二叉树的节点数为n，那么节点编号为i（1≤i≤n）的节点，其左右子节点的编号分别为2i和2i+1；

- 由于节点编号是从1开始的，所以对于任意一个节点i来说，如果i的编号为j，那么其父节点的编号就是j/2（若为小数，则向下取整）。

2. 判定算法

下面介绍两种常见的完全二叉树判定算法：

2.1. 深度优先遍历（DFS）

对于一棵完全二叉树，我们可以通过深度优先遍历（DFS）来判断其是否为完全二叉树。具体的，我们可以针对每个节点保存其编号及其在当前层的位置，然后记录最后一个遍历到的节点的编号last和在上一层的位置pos， 判断pos和last是否满足上述性质即可。

为了更好地理解，我们可以通过以下的示例建树：

```

1

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

```

我们以DFS方式遍历每个节点。在遍历节点2时，发现其在第二层而不是第一层。接着在遍历节点4时，发现其左子树不为空，但是右子树为空，说明这棵树不是完全二叉树。因此，DFS遍历算法的时间复杂度是O(n)，其中n是节点数。

2.2. 广度优先遍历（BFS）

对于一棵完全二叉树，我们还可以通过广度优先遍历（BFS）来判断其是否为完全二叉树。对于每个节点，我们可以计算出其编号，然后按照层序遍历的方式，将一层中的节点放入一个数组中，并按照其编号从左到右按顺序放置。最后，我们判断这个数组是否满足下面两个性质即可：

- 数组中没有空隙；

- 如果数组的长度为n，对于任意一个编号为i（1≤i≤n）的节点，其在数组中的位置是2i或2i+1。

为了更好地理解，我们还是以之前的示例建树，并进行BFS遍历。最后得到的数组为：

```

[1, 2, 3, 4, 5, 6, 7, 8, 9]

```

数组中没有空隙，每个编号在数组中的位置都满足性质二。因此，这棵树是一棵完全二叉树。BFS遍历算法的时间复杂度也是O(n)。

3. 总结

本文从完全二叉树的性质以及两种判定算法（DFS和BFS）入手，总结了完全二叉树的判定过程。DFS和BFS两种算法都可以在O(n)的时间内完成，其中n为节点数。因此，这两种算法都比较高效，在实际应用中可以根据具体需求选择使用哪一种。总之，掌握完全二叉树的判定算法对于理解二叉树相关算法极其重要。