带有索引叶子的树的路径

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

如果您的树是一棵完美的M-ary树，则可以重复使用已经为叶子找到的公式。

我们需要知道的树的

：

• 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  )
]

...division( /(是整数 - 范围，而套件( ^(是指数。

因此，在伪代码中，您会(再次使用整数除法和指控(：

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)