CSP-S 2022 第一轮 第7题：一个深度为5（根结点深度为1）的完全3叉树，按前序遍历的顺序给结点从1开始编号，

题目

一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（  ）号。

选项

• A. 95
• B. 96
• C. 97
• D. 98

答案

C

题解

答案是 C．97。（按本题出题意图，按各层都排满的 3 叉树计算。）

前序遍历：先访问根结点，再从左到右遍历各棵子树。 因此，每棵子树的编号是连续的。

1. 根结点编号为 1，它的每棵子树有 4 层，包含

\[ 1+3+9+27=40 \] 个结点。因此三棵子树的编号范围分别为 2～41、42～81、82～121。100 在以 82 为根的子树中。

1. 82 的每棵子树有 3 层，包含

\[ 1+3+9=13 \] 个结点，编号范围分别为 83～95、96～108、109～121。100 在以 96 为根的子树中。

1. 96 的第一个孩子编号为 97，97 的三个孩子都是叶子，依次编号为 98、99、100：

``text 96 └─97 ├─98 ├─99 └─100 ``

所以，第 100 号结点的父结点是 第 97 号结点。