如何计算3阶B树的子节点索引？层序与前序索引如何转换？

一、层序索引下的子节点计算 #

3阶满B树中，每个节点最多有3个子节点，层序索引按「从上到下、同层从左到右」的顺序编号（根节点索引为0）。

核心公式 #

前d+1层（深度0到d）的总节点数：S(d) = (3^(d+1) - 1) / 2（等比数列求和，首项1，公比3）
例如：深度0（根）总节点数S(0)=1，深度1总节点数S(1)=4，深度2总节点数S(2)=13，完全匹配示例中的节点分布。

子节点索引计算步骤 #

1. 确定目标节点的深度d：找到最小的d，满足S(d-1) ≤ n < S(d)（规定S(-1)=0，方便计算深度1的节点）
2. 计算节点在当前深度的层序位置：pos = n - S(d-1)
3. 该节点的3个子节点起始索引为S(d) + pos*3，三个子节点依次为起始索引、起始索引+1、起始索引+2

示例验证：节点层序索引1（深度1），pos=1-1=0，子节点起始索引4+0*3=4，对应4、5、6，和示例一致。

关于深度5的节点索引：深度5的第一个节点索引是S(4)=(3^5-1)/2=121，无需递归求和，直接用公式即可快速计算。

二、层序索引与前序索引的互转 #

前序遍历规则：先访问节点，再依次遍历它的三个子节点（左到右）。以下是满3阶B树（处理到固定深度D）的互转方法：

1. 层序索引转前序索引 #

假设目标节点层序索引为n，步骤如下：

• 计算节点深度d（方法同上）
• 计算节点在当前深度的层序位置pos = n - S(d-1)
• 父节点的层序索引：parent_n = (pos // 3) + S(d-2)（d≥1，根节点无父节点）
• 递归计算父节点的前序索引p_parent
• 节点是父节点的第k个子节点：k = pos % 3
• 当前节点所在子树的总节点数：subtree_size = (3^(D - d + 1) - 1) / 2（叶子节点时subtree_size=1）
• 当前节点的前序索引：p = p_parent + 1 + k * subtree_size

示例验证：层序索引4（深度2），父节点是1（前序索引1），k=0，subtree_size=1，前序索引1+1+0*1=2，符合实际前序顺序。

2. 前序索引转层序索引 #

假设目标节点前序索引为p，步骤如下：

• 计算节点深度d：找到最小的d，满足(3^(d+1)-1)/2 > p
• 深度d的第一个前序索引：first_p_d = d（沿最左路径的节点前序索引等于自身深度）
• 节点在当前深度前序的组索引：group_idx = (p - first_p_d) // 3（每组对应一个父节点的3个子节点）
• 节点在组内的位置：k = (p - first_p_d) % 3
• 当前节点的层序索引：n = S(d-1) + group_idx*3 + k

示例验证：前序索引2（深度2），group_idx=(2-2)//3=0，k=0，层序索引4+0*3+0=4，正确。

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