CSP-S 提高级 · CSP 2022 提高级第一轮 第 7 题

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

核心思路： 完全 3 叉树（每个节点 3 个子节点），深度 5，前序遍历编号。

要先算前 4 层总节点数：

• 第 1 层：3⁰ = 1 个节点
• 第 2 层：3¹ = 3 个节点
• 第 3 层：3² = 9 个节点
• 第 4 层：3³ = 27 个节点
• 前 4 层合计：1 + 3 + 9 + 27 = 40 个节点

第 100 号节点在第 5 层（编号范围 41~121），它是第 5 层被前序遍历到的第 60 个节点（100 - 40 = 60）。

要求它的父节点编号。前序遍历下，第 4 层第 k 个节点的编号范围是它前面所有节点数+1 起。第 4 层共 27 个节点，分别编号为第 41~67 的前序遍历顺序开头部分？

不对，让我用更清晰的思路。 第 4 层的节点编号是前 40 个节点中的最后 27 个（编号 14~40）。

这道题标准的解法是用编号反推父节点： 前序遍历下，节点 i 的子节点范围是连续的。对 3 叉树，若父节点编号为 p，其第 1 个子树的编号范围从 p+1 开始，第 2 个子树在其后，第 3 个子树在最后。

利用"前序遍历每个子树编号连续"的性质，第 4 层的父节点中，编号 97 的子节点范围覆盖了 100，所以父节点是 97。

最容易犯的错： 误用"完全二叉树层次遍历编号"的规律来做前序遍历题。完全二叉树的层次遍历编号有简便公式（父 i，子 2i+1 等），但前序遍历没有这样的公式，必须根据遍历顺序来推导。

另外容易算错： 误把 3 叉树当 2 叉树算，或者忘记前 4 层的总节点数。

考察知识点： 树形结构 — 完全多叉树的前序遍历编号

解题方法（前序遍历连续区间法）：

前序遍历的顺序是：访问根 → 前序遍历子树 1 → 前序遍历子树 2 → 前序遍历子树 3

这意味着：每个节点出发，它的整棵子树在编号上是连续的一段。

具体推导：

第 1 层 1 个节点，编号 1。

第 2 层 3 个节点，编号 2~4（根节点之后先访问第 1 棵子树）。

第 3 层：

• 节点 2 的子树（3 叉）：节点 5~13（3 个子树，各含 3 个节点？不对，第 3 层每个节点在第 4 层还有子树）

这道题更简洁的解法是利用 3 叉树前序遍历的一个性质：前序遍历编号 n 的节点的父节点编号可以通过以下方式求得：

对完全 3 叉树，第 i 层有 3^(i-1) 个节点。前 4 层 40 个节点，第 5 层第 60 个节点是第 100 号。

第 5 层的第 1~27 个节点属于第 4 层第 1 个节点的子树，第 28~54 个属于第 4 层第 2 个节点，第 55~81 个属于第 4 层第 3 个节点。

100 号是第 5 层的第 60 个（100-40=60），60 属于第 3 段（55~81），所以它的父节点是第 4 层第 3 个节点。第 4 层第 3 个节点的编号 = 14 + 2（前 2 个节点各占一段）... 实际上第 4 层节点编号是 14~40。

等等，更直接的思路： 完全 3 叉树前序遍历，父节点编号 p，其 3 个子树中第 1 个子树的根编号是 p+1。

题目结论：第 100 号节点的父节点是 97。

技巧： 树的编号题，画图胜千言。画出前 3~4 层的编号分布就能看出规律。