Каков наиболее эффективный способ обхода дерева в Python?

Question

Предположим, у меня есть список объектов со следующими полями

родитель

значение

и это определяет древовидную структуру, аналогичную дереву каталогов.

Я хочу просмотреть список в порядке предварительного заказа. Какой самый эффективный способ?

Обычно в других (более императивных) языках я бы повторял значения, находя значения без родителей, затем для каждого, повторяя снова для каждого объекта, чьим родителем является тот, на которого я сейчас смотрю, и так далее, но Есть ли более умный способ сделать это в Python?

Answer 1

Сначала я бы создал более подходящую структуру данных - захватывая ссылку от родителя на его потомков:

children = {}
for obj in tree:
    children.setdefault(obj.parent, []).append(obj)

def preorder(root, children):
    yield root.value
    for child in children.get(root, []):
        for value in preorder(child, children):
            yield value

for root in children[None]:
    for value in preorder(root, children):
        print value

Вы также можете использовать collections.defaultdict здесь.