Python: алгоритм обхода дерева, который расширяется на каждом узле

Question

У меня есть словарь с идентификатором и несколькими значениями для каждого идентификатора, которые являются строками. Для каждого значения в этом для каждого Id я делаю запрос к базе данных и получаю набор результатов:

{111: Run, Jump, swim}
{222: Eat, drink}

поэтому для каждого значения, скажем, запустить, я выполняю запрос, и он возвращает другой набор данных, затем выбирает каждое значение этого набора и запускает запрос, который даст другой набор, и, наконец, я прихожу к точке, где есть только один элемент, получить вернуть. Как только я закончу получать последний элемент каждого отдельного подэлемента Run, я перехожу к Jump и продолжаю.

Я задавал этот вопрос раньше, но не получил никаких результатов, поэтому люди сказали мне удалить код и просто задать вопрос еще раз. Вот ссылка на тот же вопрос, который я задал несколько дней назад. Мне нужно реализовать что-то вроде disjoin set?

Answer 1

Вы можете рассматривать категории / подкатегории как дерево с N ветвями в каждом узле (в зависимости от того, сколько у вас категорий).Из того, что я могу собрать, вы в основном хотите создать упорядоченный список листьев дерева.

Один простой способ сделать это - с помощью генераторов (используя терминологию из исходного вопроса):

def lookup(elem):
    # do your SQL call here for a given category 'elem' and return
    # a list of it's subcategories
    return []

def leaves(lst):
    if lst:
        for elem in lst:                          # for every category
            for sublist in leaves(lookup(elem)):  # enumerate it's sub categories
                yield sublist                     # and return it
            yield elem                            # once lookup(elem) is [] return elem

d = { 111: [Run, Jump, swim] , 222: [Eat, drink] }

for key, lst in d.items():
    print key, [elem for elem in leaves(lst)]

Если вы не знакомы с генераторами, они просто конструкции итераторов, которые «дают»значения вместо того, чтобы возвращать их.Разница в том, что выдача только приостанавливает итератор в том месте, которое будет продолжаться там, где он остановился, когда запрашивается следующее значение.

С некоторой умной рекурсией внутри генератора вы можете просто проанализировать все дерево.

[elem for elem in leaves(lst)] - это понимание списка, и оно просто создает список, содержащий elem для каждого элемента, повторяемого по leaves.

Answer 2

Это похоже на обход дерева.Вы можете использовать BFS или DFS .