如何枚举到任意深度元素中每个元素的路径

Question

我正在编写一些Python代码，其中数据表示为n元树，其中n由用户给定。树的算术是确定的，但我正在努力用一个算法来枚举从根到每个元素的路径。你知道吗

例如，如果我有一棵三叉树

                                      .
                                     /|\
                                    / | \
                                   /  |  \
                                  /   |   \
                                 .    .    .
                                /|\  /|\  /|\
                               a b cd . hi j k
                                     /|\
                                    e f g

由嵌套列表表示

[[a, b, c], [d, [e, f, g], h], [i, j, k]]

我想要一个元组列表，比如

[(a, 00), (b, 01), (c, 02), (d, 10), (e, 110), (f, 111), (g, 112), (h, 12), (i, 20), (j, 21), (k, 22)]

我确实在这里发现了一个类似的问题Enumerating all paths in a tree，但这并不是我所需要的，而且我不确定如何实现我正在寻找的枚举类型。你知道吗

Answer 1

下面是一个递归方法，它使用yield from和递归生成每个叶的路径。你知道吗

class Tree:
  def __init__(self, *children, data=None):
    self.data = data
    self.children = children


def find_all(root, path_to=()):
    if root is None:
        return
    if not root.children:
        yield (root.data, path_to)
    else:
        for i, node in enumerate(root.children):
            yield from find_all(node, path_to=(*path_to, i))

root = Tree(Tree(Tree(data='a'), Tree(data='b'), Tree(data='c')), Tree(Tree(data='d'), Tree(Tree(data='e'), Tree(data='f'), Tree(data='g')), Tree(data='f')), Tree(Tree(data='g'), Tree(data='h'), Tree(data='i')))

print(list(find_all(root)))
# [('a', (0, 0)), ('b', (0, 1)), ('c', (0, 2)), ('d', (1, 0)), ('e', (1, 1, 0)), ('f', (1, 1, 1)), ('g', (1, 1, 2)), ('f', (1, 2)), ('g', (2, 0)), ('h', (2, 1)), ('i', (2, 2))]

Answer 2

我认为实际的树和它的表示不匹配。
如果我没有弄糟这张照片，应该是：

repr = [["a", "b", "c"], ["d", ["e", "f", "g"], "h"], ["i", "j", "k"]]

如果您的数据由repr这样的列表组成，您可以使用如下递归函数：

def tree(l, ind=""):
    for i, x in enumerate(l):
        if isinstance(x, list):
            yield from tree(x, ind + str(i))
        else:
            yield x, ind + str(i)

>>> print(list(tree(repr))
[('a', '00'), ('b', '01'), ('c', '02'), ('d', '10'), ('e', '110'), ('f', '111'), ('g', '112'), ('h', '12'), ('i', '20'), ('j', '21'), ('k', '22')]