想象一下下面的树:
A
/ \
B C
/ \ \
D E F
我正在寻找一种方法来查询例如 F 是否是 A 的后代(注意:F 不需要是 A 的直接后代)，在这个特定的情况会是真的。仅需要针对更大的潜在后代节点池测试有限数量的潜在父节点。
在测试一个节点是否是潜在父池中某个节点的后代时，需要针对所有潜在父节点进行测试。
这是一个想出的:
将多路树转换为 trie，即为上述树中的每个节点分配以下前缀:
A = 1 B = 11 C = 12 D = 111 E = 112 F = 121然后，为每个可能的前缀大小保留一个位数组，并添加要测试的父节点，即如果将 C 添加到潜在的父节点池中，则执行:
1 2 3 <- Prefix length *[1] [1] ... [2] *[2] ... [3] [3] ... [4] [4] ... ... ...当测试一个节点是否是潜在父节点的后代时，获取它的 trie 前缀，查找第一个“前缀数组”(见上文)中的第一个字符，如果存在，查找第二个前缀第二个“前缀数组”中的字符等等，即测试 F 导致:
F = 1 2 1 *[1] [1] ... [2] *[2] ... [3] [3] ... [4] [4] ... ... ...所以是的，F 是 C 的后代。
这个测试似乎是 O(n) 的最坏情况，其中 n = 最大前缀长度 = 最大树深度，因此它的最坏情况恰好等于只上树并比较节点的明显方式。然而，如果被测试的节点靠近树的底部并且潜在的父节点在顶部某处，这会表现得更好。结合这两种算法将减轻两种最坏的情况。但是，内存开销是一个问题。
还有其他方法吗？非常感谢任何指点!
最佳答案
你的输入树总是静态的吗？如果是这样，那么您可以使用最低公共(public)祖先算法在 O(1) 时间内用 O(n) 时间/空间构造回答后代问题。 LCA 查询有两个节点，并询问哪个是树中最低的节点，其子树包含这两个节点。然后，您可以使用单个 LCA 查询来回答 IsDescendent 查询，如果 LCA(A, B) == A 或 LCA(A, B) == B，则一个是另一个的后代。
这Topcoder algorithm tuorial对问题进行了全面讨论，并在代码复杂性/效率的各个级别提供了一些解决方案。
关于algorithm - O(1)算法确定节点是否是多路树中另一个节点的后代？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6020369/