完全二叉树的定义与基本性质

完全二叉树（Complete Binary Tree）是一种特殊的二叉树，具有以下定义和基本性质：

定义：

完全二叉树是一棵二叉树，其中除了最后一层的叶子结点可能不满，其他层的结点都是满的，而且最后一层的叶子结点从左向右依次填满。也就是说，在完全二叉树中，从左到右依次填充结点，不会留下空缺。

基本性质：

1. 完全二叉树的高度（深度）为 h，其中 h 为从根节点到最左叶子结点的最短路径的长度。

2. 在完全二叉树中，最大结点数出现在最后一层。

3. 如果一棵完全二叉树的结点数为 n，则高度为 log₂(n) + 1，其中 log₂ 表示以2为底的对数。

4. 对于完全二叉树，从左到右编号（从1开始），结点 i 的性质如下：

• 如果 i = 1，即根结点，没有父节点。

• 如果 i > 1，则结点 i 的父节点编号为 i / 2（整数除法）。

• 如果 2i ≤ n，则结点 i 的左子节点编号为 2i。

• 如果 2i + 1 ≤ n，则结点 i 的右子节点编号为 2i + 1。

5. 完全二叉树的一个重要性质是可以使用数组来存储。具体地，对于结点 i，它在数组中的索引位置为 i-1。这样，根节点存储在数组的第一个位置，左子节点在第二个位置，右子节点在第三个位置，以此类推。这种存储方式可以高效地实现完全二叉树的各种操作。

完全二叉树常用于堆（Heap）数据结构和优先队列的实现，因为它的性质使得这些数据结构的操作更加高效。