2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

该完全二叉树的深度为 9，因为满足 2^(9-1) <= 500 < 2^9。

用二叉链表作为该完全二叉树的存储结构，共有 499 个空指针域。因为在完全二叉树中，除了最后一层，其他层都是满的，所以除了最后一层，每层的节点数都是满的。最后一层的节点数不满，但是空出的节点位置是从左到右依次排列的。因此，除了根节点之外，每个节点都有一个双亲节点，所以共有 500 - 1 = 499 个空指针域。

相关问题

设一棵完全二叉树中有1020个结点，则该二叉树的深度为____10______；若用二叉链表作为该完全二叉树的存储结构，则共有_____1023______个空指针域。

设一棵完全二叉树中有1020个结点，根据完全二叉树的特点[^1]，其深度可以通过公式计算：`depth = floor(log2(n + 1))`。代入n=1020得到深度为：

import math
nodes = 1020
depth = math.floor(math.log2(nodes + 1))
depth

运行这段代码会得到深度为10。

对于二叉链表存储的完全二叉树，除了实际的结点之外，还有每个非叶子节点（即拥有两个子节点的节点）指向其子节点的指针。在一棵深度为k的完全二叉树中，除了最后一个层次可能不全，其他所有层次都是满的。所以除了叶子结点外，每个结点都有一个空指针域。在深度为k的完全二叉树中，总共有2k-1个叶子结点（因为至少有这么多），而每个非叶子结点对应一个额外的空指针域。因此，总共的空指针域数量为：

non_leaf_nodes = 2**depth - 1 - nodes
total_pointers = non_leaf_nodes + nodes  # 叶子结点不包含空指针
total_pointers

运行这段代码会得出共有1023个空指针域。

设一棵完全二叉树中有 21 个结点，如果按照从上到下、从左到右的顺序从 0 开始顺序编号，则编号为 8 的双亲结点的编号是___________，编号为 8 的左孩子结点的编号是_____________。

在完全二叉树中，每个节点的编号与其位置有直接的关系。对于第 `i` 个节点，如果它是从上往下数的第 `j` 行（行数从 0 开始），并且从左往右数的第 `k` 个节点（列数也从 0 开始），那么它的编号就是 `2^(j-1) * k + i - 1`。

对于编号为 8 的节点：
1. 因为它是第 8 号节点，我们可以先计算出它所在的行和列。由于它是从0开始编号，所以需要找出 `(8 - 1)` 是哪两个 `2^n` 的差值之和，也就是 `(8 - 1)` 等于第几层的 `2^(n-1)` 和第几列的 `k` 乘积。这可以逐位检查：

   8 = 2^3 (因为4*2=8)
   所以，8是一个深度为3的节点，即它在第4行，第0列（因为是从0开始计数的）。

其双亲节点将位于上一行的最右边，也就是第 3 行的最后一个节点，其列号将是 2^(3-1) - 1，即 `2 * 1 - 1 = 1`。所以双亲节点的编号是 `2^(3-1) * 1 + 3 - 1 = 2 * 1 + 2 = 4`。

2. 对于编号为 8 的左孩子结点，它将在同一行的下一个位置，即第 4 行第 1 列，因此左孩子的编号是 `2^(3-1) * 2 + 8 - 1 = 2 * 2 + 7 = 11`。

总结起来，编号为 8 的双亲节点的编号是 4，左孩子节点的编号是 11。