基于数组实现的三叉树：如何通过节点索引计算节点深度

推导思路 #

先明确数组存储的节点索引与深度的对应规律：

• 深度为d的节点，其索引范围是：

  (3^d + 1)/2 ≤ index ≤ (3^(d+1) - 1)/2
  

  比如：
  • 深度0（根节点）：索引范围[1,1]
  • 深度1：索引范围[2,4]
  • 深度2：索引范围[5,13]

对上述不等式变形，得到关于d的约束：

1. 3^d ≤ 2*index - 1
2. 3^(d+1) ≥ 2*index + 1

对两边取以3为底的对数后取整，即可得到节点深度。

计算公式 #

结合Python的数学函数，公式如下：

import math
d = math.floor(math.log(2 * index - 1, 3))

验证示例 #

• 根节点A（index=1）：2*1-1=1，log₃(1)=0，floor(0)=0，深度正确。
• 节点B（index=2）：2*2-1=3，log₃(3)=1，floor(1)=1，深度正确。
• 节点F（index=6）：2*6-1=11，log₃(11)≈2.18，floor(2.18)=2，深度正确。
• 节点M（index=13）：2*13-1=25，log₃(25)≈2.93，floor(2.93)=2，深度正确。
• 深度3的第一个节点（index=14）：2*14-1=27，log₃(27)=3，floor(3)=3，深度正确。

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