algorithm - 确定层次结构中的两个节点是否已连接

Question

我有一堆节点按如下层次结构排列:

我想确定一个节点是否连接到另一个节点，即使两者之间的连接被层次结构中的不同级别分开。

例如，节点 A 通过节点 B 和 D 连接到节点 K。节点 A 还通过节点 B 和 D 或节点 C 和 G 连接到节点 L。

节点 E、F、H、J 和 M 没有连接到节点 L。

无需将层次结构从父节点遍历到某个子节点以确定两个节点是否连接，我相信可以为每个节点分配一些数值并通过一个取两个数值的公式节点可以确定它们已连接。

这可能吗？

Answer 1

是的，通过提供某种累进数字或模式 (Id) 可以对此有所帮助。看看下面的图片-(对不起，图片尺寸太小。点击它可以正确查看)

我已经为每个节点分配了一个 Id no like 1 给根，然后 1-1....1-N 给它的子节点。现在要检查节点是否已连接，我们只需要检查一个节点 ID 是否以另一个节点开头。如果是这样，则节点已连接，否则不会。