Как перечислить пути к каждому элементу в сколь угодно глубоком n-арном дереве

Question

Я работаю над кодом Python, в котором у меня есть представление данных в виде n-арных деревьев, где n задано пользователем.Арность дерева определена, но я борюсь с алгоритмом для перечисления пути от корня до каждого элемента.

Например, если у меня есть 3-арное дерево

                                      .
                                     /|\
                                    / | \
                                   /  |  \
                                  /   |   \
                                 .    .    .
                                /|\  /|\  /|\
                               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)]

Я нашел подобную проблему здесь Перечисление всех путей вдерево но это не совсем то, что мне нужно, и я не уверен, как мне добиться того перечисления, которое я ищу.

Answer 1

Я думаю, что существует несоответствие между фактическим деревом и его представлением.
Если я не испортил изображение, оно должно быть:

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

Answer 2

Вот рекурсивный метод для наведения пути к каждому листу, используя 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))]