C++中完全二叉树的数组表示法

在 C++ 中，可以用数组来表示完全二叉树。对于具有 n 个节点的完全二叉树，可以使用一个大小为 n+1 的数组来存储其节点，数组下标从 1 开始，节点的编号也从 1 开始，具体如下：

• 数组下标为 i 的节点的编号为 i；

• 数组下标为 i 的节点的左子节点的下标为 2i；

• 数组下标为 i 的节点的右子节点的下标为 2i+1；

• 数组下标为 i 的节点的父节点的下标为 i/2（向下取整）。

其中，下标为 0 的元素可以不用，方便起见，下标从 1 开始。下面是一个具有 10 个节点的完全二叉树的数组表示法的示例：

int tree[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

其中，tree[1] 表示根节点，tree[2] 表示根节点的左子节点，tree[3] 表示根节点的右子节点，以此类推。通过这种方式，可以方便地存储和操作完全二叉树。

以下是一个具有 10 个节点的完全二叉树的数组表示法的示意图：

         +---+
         | 1 |
         +---+
        /     \\
     +---+   +---+
     | 2 |   | 3 |
     +---+   +---+
    /   \\   /   \\
 +---+ +---+ +---+ +---+
 | 4 | | 5 | | 6 | | 7 |
 +---+ +---+ +---+ +---+
  / \\
+---+ +---+
| 8 | | 9 |
+---+ +---+