C++中完全二叉树的定义与基本性质
完全二叉树是一种特殊的二叉树，其中除了最后一层之外，每一层的节点数都达到了最大值，最后一层的节点都集中在左侧。具体来说，一棵二叉树如果满足以下条件之一，则称其为完全二叉树：
该二叉树是一棵空树，或者只有一个节点。
该二叉树的根节点至少有一个左子节点。
该二叉树的根节点至少有一个右子节点，并且其左子树是一棵满足完全二叉树条件的二叉树，其右子树是一棵满足完全二叉树条件的二叉树，并且其左子树的高度等于其右子树的高度，或者相差1。
基于完全二叉树的定义，我们可以得到以下几个基本性质：
对于一棵有 n 个节点的完全二叉树，其深度为 log2(n)。
对于一棵有 n 个节点的完全二叉树，其第 i 层的节点数为 2^(i-1)，其中 i=1,2,...,log2(n)+1。
对于一棵有 n 个节点的完全二叉树，其最后一层的节点数在 1 到 2^(log2(n)) 之间。
对于一棵有 n 个节点的完全二叉树，其节点从上到下，从左到右依次编号为 1, 2, ..., n。对于任意一个节点 i，它的左子节点的编号为 2i，右子节点的编号为 2i+1，其父节点的编号为 i/2。
基于以上性质，我们可以利用完全二叉树的特点来实现一些高效的算法，例如堆排序中使用的堆就是一种完全二叉树。此外，由于完全二叉树中的节点位置相对固定，因此可以使用数组来存储一棵完全二叉树，进一步提高其访问效率。
除了上述基本性质外，完全二叉树还有一些其他的性质：
对于一棵有 n 个节点的完全二叉树，如果用数组 A 来存储这棵二叉树，则对于任意一个下标 i，其左子节点的下标为 2i，右子节点的下标为 2i+1，其父节点的下标为 i/2（向下取整）。因此，可以使用数组来实现一棵完全二叉树的存储，而不需要使用指针来实现。
对于一棵有 n 个节点的完全二叉树，如果用数组 A 来存储这棵二叉树，则从 A[1] 到 A[n] 的元素构成了一个堆，且堆是一棵完全二叉树。因此，完全二叉树是堆的一种特殊情况。
对于一棵有 n 个节点的完全二叉树，其高度为 O(log n)。因此，完全二叉树上的操作，如查找、插入、删除等，都可以在 O(log n) 的时间内完成。
对于一棵有 n 个节点的完全二叉树，其最后一个非叶子节点的下标为 n/2（向下取整）。因此，可以在数组实现的完全二叉树中，直接从最后一个非叶子节点开始进行堆排序，而不需要考虑叶子节点。
综上所述，完全二叉树是一种具有特殊性质的二叉树，可以使用数组来实现，也是堆排序算法中的重要数据结构。在实际应用中，经常使用完全二叉树来实现优先队列、哈夫曼编码等算法。
以下是一棵具有 10 个节点的完全二叉树的示意图：
1 / \\ 2 3 / \\ / \\ 4 5 6 7 / \\ 8 9
可以看到，这棵完全二叉树的每一层都是满的，除了最后一层。并且，最后一层的节点都尽可能地排列在左侧，使得整棵树保持完美平衡的状态。此外，这棵树的节点按照从上到下、从左到右的顺序编号，编号为 i 的节点的左子节点的编号为 2i，右子节点的编号为 2i+1，其父节点的编号为 i/2（向下取整）。这些性质可以方便地用数组来实现完全二叉树的存储和操作。
