《C++数据结构与算法（第2版）》Euler二叉树后代节点计数方法疑问

核心概念铺垫 #

欧拉遍历对二叉树的每个节点做两次标记：

• 左访问（首次触发）：从父节点进入当前节点时，记录递增的计数器值（记为in[p]）
• 右访问（二次触发）：处理完当前节点的所有子树、回溯回父节点前，记录此时的计数器值（记为out[p]）

计数器从1开始，每完成一次访问（左/右）就加1。以你提到的树为例，先明确树结构：
根节点为1，左子节点2；节点2的左子4、右子5；根节点1的右子节点3；节点3的右子6。

对应的完整遍历序列及计数器值：

1. 左访问节点1 → in[1] = 1
2. 左访问节点2 → in[2] = 2
3. 左访问节点4 → in[4] = 3
4. 右访问节点4 → out[4] = 4
5. 左访问节点5 → in[5] = 5
6. 右访问节点5 → out[5] = 6
7. 右访问节点2 → out[2] = 7
8. 左访问节点3 → in[3] = 8
9. 左访问节点6 → in[6] = 9
10. 右访问节点6 → out[6] = 10
11. 右访问节点3 → out[3] = 11
12. 右访问节点1 → out[1] = 12

规则的本质逻辑 #

节点p的所有后代（包括自身）的左访问计数器值，必然落在in[p]和out[p]之间。因为每个后代节点都会被标记两次，所以in[p]到out[p]之间的访问记录数，恰好是后代节点数的2倍。

作者提到的“计算p左访问与右访问时计数器的差值并加1”，实际是计算包含p自身的子树总节点数的前置步骤，完整计算逻辑为：

子树总节点数（含p）= (out[p] - in[p] + 1) / 2

若仅需计算不含p的后代节点数，则公式调整为：

后代节点数（不含p）= (out[p] - in[p] - 1) / 2

实例验证 #

1. 节点4的后代计算

   • in[4] = 3，out[4] = 4
   • 含自身的节点数：(4-3+1)/2 = 1（正确，仅节点4）
   • 不含自身的后代数：(4-3-1)/2 = 0（正确，无后代）

2. 节点2的后代计算

   • in[2] = 2，out[2] = 7
   • 含自身的节点数：(7-2+1)/2 = 3（对应节点2、4、5，正确）
   • 不含自身的后代数：(7-2-1)/2 = 2（对应节点4、5，正确）

3. 节点1的后代计算

   • in[1] = 1，out[1] = 12
   • 含自身的节点数：(12-1+1)/2 = 6（对应所有节点，正确）
   • 不含自身的后代数：(12-1-1)/2 = 5（对应节点2、3、4、5、6，正确）

时间复杂度说明 #

整个欧拉遍历需要遍历每个节点两次，总访问次数为2n（n为节点总数），因此预处理in和out值的时间复杂度为O(n)。之后计算任意节点的后代数量仅需O(1)时间，整体复杂度为O(n)。

内容的提问来源于stack exchange，提问作者yapkm01