想象一下下面的树：

    A
   / \
  B   C
 / \   \
D   E   F

我在寻找一种方式来查询，例如F是的后代（注：F并不需要是一个直接后代的F），其中，在这个特殊的情况是真实的。需要潜在的父节点只有有限的量来对一个较大的潜在后代节点池进行测试。

I'm looking for a way to query if for example F is a descendant of A (note: F doesn't need to be a direct descendant of F), which, in this particular case would be true. Only a limited amount of potential parent nodes need to be tested against a larger potential descendants node pool.

更新：当测试一个节点是否是潜在的父池节点的后代，它需要对所有潜在的父节点测试

UPDATE: when testing whether a node is a descendant of a node in the potential parent pool, it needs to be tested against ALL potential parent nodes.

这是一个想出了：

多通树转换为线索，即分配以下prefixes于上述树的每个节点

Convert multiway tree to a trie, i.e. assign the following prefixes to every node in the above tree:

 A = 1
 B = 11
 C = 12
 D = 111
 E = 112
 F = 121

然后，保留一个位阵列为每一个可能的preFIX大小和添加父节点要对所测试的，也就是说，如果C被添加到潜在的父节点池，执行：

Then, reserve a bit array for every possible prefix size and add the parent nodes to be tested against, i.e. if C is added to the potential parent node pool, do:

  1    2    3  <- Prefix length

*[1]  [1]  ...
 [2] *[2]  ...
 [3]  [3]  ...
 [4]  [4]  ...
 ...  ...

在测试如果一个节点是一个潜在的父节点的后代，取其特里preFIX，查找第一个字符的第一个preFIX阵列（见上文），如果是present，查找第二preFIX字符的第二个preFIX阵等中，即测试˚F导致：

When testing if a node is a descendant of a potential parent node, take its trie prefix, lookup the first character in the first "prefix array" (see above) and if it is present, lookup the second prefix character in the second "prefix array" and so on, i.e. testing F leads to:

 F = 1    2    1

   *[1]  [1]  ...
    [2] *[2]  ...
    [3]  [3]  ...
    [4]  [4]  ...
    ...  ...

所以是女，是C的后裔。

so yes F, is a descendant of C.

此测试似乎是最坏的情况下为O（n），其中n =最大preFIX长度=最大树深度，所以其最坏的情况是正好等于只是去了树和比较节点的明显的方式。然而，这种执行好得多，如果所测试的节点是树的底部附近与潜在的父节点是在顶部的地方。结合这两种算法将缓解这两个最坏的情况。但是，内存开销是一个问题。

This test seems to be worst case O(n), where n = maximum prefix length = maximum tree depth, so its worst case is exactly equal to the obvious way of just going up the tree and comparing nodes. However, this performs much better if the tested node is near the bottom of the tree and the potential parent node is somewhere at the top. Combining both algorithms would mitigate both worst case scenarios. However, memory overhead is a concern.

有另一种方式这样做？任何指针大大AP preciated！

Is there another way for doing that? Any pointers greatly appreciated!

推荐答案

总是静态的输入的树？如果是这样，那么你可以用最低的共同祖先算法回答是O（1）时间与O（n）的时间/空间结构后裔的问题。一个LCA查询，给出两个节点，问这是其子树包含两个节点树中的最低点。然后你就可以回答了一个LCA查询IsDescendent查询，如果LCA（A，B）== A或LCA（A，B）= = B，则一个是另一个的后代。

Are your input trees always static? If so, then you can use a Lowest Common Ancestor algorithm to answer the is descendant question in O(1) time with an O(n) time/space construction. An LCA query is given two nodes and asked which is the lowest node in the tree whose subtree contains both nodes. Then you can answer the IsDescendent query with a single LCA query, if LCA(A, B) == A or LCA(A, B) == B, then one is the descendent of the other.

这上衣codeR算法tuorial 给出了问题和一些解决方案，在各级code复杂性/效率进行了深入探讨。

This Topcoder algorithm tuorial gives a thorough discussion of the problem and a few solutions at various levels of code complexity/efficiency.