algorithm - 具有索引叶的树中的路径

Question

我想弄清楚如何在树中生成路径，其中节点标记为 (position relative to parent,height) 并且叶子从 0 开始索引。现在我遍历整棵树，这可能是一种愚蠢的做法。例如，下面树中叶子 2 的路径为:root/(1,1)/(0,0)

            root
           /   \
        (0,1) (1,1)
         / \   /  \
        0   1  2   3

我知道如何获取路径中的最后一项:(叶索引 % 分支率，0)。但现在我被困在如何走完剩下的路了。必须有一种不遍历整棵树的方法吗？

Answer 1

如果你的树是 perfect m-ary tree ，那么您可以重复使用已经为叶子找到的公式。

我们需要知道的树:

• m:分支因子，即所有内部节点的子节点数。
• h:树的高度，即根节点的高度。

设 k 是要查找其路径的叶的从零开始的索引。那么路径是:

[
    root,
    ((k / m^(h-1)) % m, h-1),
    ((k / m^(h-2)) % m, h-2),
    ...
    ((k / m^2    ) % m, 2  ),
    ((k / m      ) % m, 1  ),
    (k             % m, 0  )
]

... 其中除法 (/) 是整数除法，插入符号 (^) 是求幂。

所以在伪代码中，你会这样做(再次使用整数除法和求幂):

get_path(m, h, k):
    path = ["root"]
    denom = m^h
    while h > 0:
        h = h - 1
        denom = denom / h
        path.append( ((k / denom) % m, h) )
    return path

反过来可能更容易一些:

get_path(m, h, k):
    path = []
    for height = 0 to h-1:
        path.append( (k % m, height) )
        k = k / m
    path.append("root")
    return reversed(path)