完全二叉树的判定方法

二叉树是一种重要的树型结构，它是一种特殊的有序树，并且每个节点最多只有两个子节点。在二叉树中，完全二叉树是一种比较常见的形式，因为它在存储和遍历方面都有很好的优势，因此很多算法和数据结构课程中都会涉及到完全二叉树。那么什么是完全二叉树，如何判断一个二叉树是否是完全二叉树呢？下面从多个角度进行分析，为大家解答。

一、什么是完全二叉树？

完全二叉树的定义是：除最后一层外，其余各层的节点数都达到最大值；在最后一层上只缺少右侧若干节点。也就是说，如果用数组来存储一棵完全二叉树，它的前n个元素就按照完全二叉树的规则排列，从根节点开始，每个节点对应数组中的一个元素，其左子节点在数组中对应的位置是2i+1，右子节点在数组中对应的位置是2i+2，其中i表示节点在数组中对应的索引。

例如，下图就是一棵完全二叉树：


二、如何判断一个二叉树是否是完全二叉树？

1. 按层序遍历

按照完全二叉树的定义，最后一层节点可以不完全充满，但是最后一层的缺失节点必须在右侧，所以我们可以按照层序遍历的方式，从上到下、从左到右遍历二叉树，并检查是否存在不符合完全二叉树定义的节点。具体实现可以使用队列来保存每一层的节点，如果发现某个节点只有左子节点却没有右子节点，或者某个节点后面还有其他节点却没有左右子节点，那么这个二叉树就不是完全二叉树。

2. 判断满二叉树

另一种判断完全二叉树的方法是通过判断满二叉树。如果一棵二叉树的深度为h，并且它是一棵满二叉树，那么它的节点总数是2^h-1。因此，我们可以先求出当前二叉树的深度h，然后统计节点数n，如果n等于2^h-1，那么这个二叉树就是满二叉树，也就是完全二叉树。

3. 遍历判断

还有一种方法是，先求出当前二叉树的深度h，然后以中序遍历的方式依次遍历每个节点，如果当前节点的索引小于2^(h-1)，那么这个节点一定在树的左半部分，否则在树的右半部分。如果某个节点的索引不满足这个规律，那么这个二叉树就不是完全二叉树。

三、完全二叉树的优势和应用

1. 存储和遍历

完全二叉树在存储和遍历方面都有很好的优势。在存储方面，因为它有固定的规律，所以可以用数组来存储，从而避免使用指针的开销；在遍历方面，利用完全二叉树的规律，我们可以很快地实现树的遍历，例如按层序遍历。

2. 堆的实现

堆是一种常用的数据结构，它是一种特殊的完全二叉树。在堆中，每个节点的值都不小于（或不大于）它的子节点的值，通常用来实现优先队列等。因为堆是一棵完全二叉树，因此可以利用完全二叉树的特性来实现堆的相关算法。