Прогулка по дереву, родитель первым

Question

Каков наилучший способ посетить все узлы связанного дерева (все узлы имеют ссылки на родительский и все дочерние узлы, корневые узлы имеют нулевое значение в качестве родительского), чтобы ни один из узлов не посещался раньше, чем его предки? Очки Брауни для нерекурсивных.

Answer 1

Псевдокод:

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

Редактировать : рекурсивно или нет?
Чтобы быть технически правильным, и как указано AndreyT и другими в этом посте, этот подход форма рекурсивного алгоритма, в котором вместо стека ЦП используется явно управляемый стек, а рекурсия происходит на уровне цикла While.Тем не менее, он отличается от рекурсивной реализации per se несколькими тонкими, но значительными способами:

• Только «переменные» помещаются в стек;в стеке нет «стекового фрейма» и связанного с ним адреса возврата, единственный «адрес возврата» неявен для цикла while, и есть только один его экземпляр.
• Можно использовать «стек»в виде списка, в котором следующий «кадр» можно взять в любом месте списка, не нарушая логику.

Answer 2

Поиск в ширину

Answer 3

Если у вас есть ссылки на всех потомков, а также на родителя, то нерекурсивный алгоритм довольно тривиален. Просто забудь, что у тебя есть дерево. Представьте, что это лабиринт, в котором каждая связь родитель-ребенок представляет собой обычный двунаправленный коридор от одного перекрестка к другому. Все, что вам нужно сделать, чтобы пройти весь лабиринт, это повернуть в следующий коридор слева на каждом перекрестке. (В качестве альтернативы, подумайте о том, чтобы ходить лабиринтом левой рукой, всегда касаясь стены с левой стороны). Если вы начнете с корневого узла (и будете двигаться в любом направлении), вы пройдете по всему дереву, всегда навещая родителей перед детьми. Каждый «коридор» в этом случае будет проходить дважды (в одном направлении и в другом), и каждый «узел» (узел) будет посещаться столько раз, сколько к нему присоединяется «коридоров».

Answer 4

Вы ищете обход предзаказа. Я думаю, что вы можете сделать это не рекурсивно с очередь:. В псевдокоде:

Создайте пустую очередь, затем протолкните корневой узел.

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

Answer 5

Вот действительно нерекурсивный подход: без стека, с постоянным пространством. В этом коде Python предполагается, что каждый узел содержит список дочерних элементов и что объекты узла не определяют равенство, поэтому функция «индекс» сравнивает тождества:

def walkTree(root, visit_func):
    cur  = root
    nextChildIndex = 0

    while True:
        visit_func(cur)

        while nextChildIndex >= len(cur.children) and cur is not root:
            nextChildIndex = cur.parent.children.index(cur) + 1
            cur  = cur.parent

        if nextChildIndex >= len(cur.children):
            break

        cur = cur.children[nextChildIndex]
        nextChildIndex = 0

Я уверен, что его можно немного отточить, сделать более кратким и легким для чтения, но в этом суть.

Answer 6

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

Ссылка: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 7

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

Будет работать любой вид обхода, сначала глубина (рекурсивно / основанный на стеке), ширина сначала (основанная на очереди), ограниченная глубина или просто извлечение их из неупорядоченного набора.

«Лучший» метод зависит от дерева. Ширина сначала будет хорошо работать для очень высокого дерева с несколькими ветвями. Глубина сначала будет хорошо работать для деревьев со многими ветвями.

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

Answer 8

в псевдокоде:

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

Answer 9

Использовать набор узлов. Поставь рут в комплекте для начала. Затем в цикле вытащите узел из набора, посетите его, а затем поместите его дочерние элементы в набор. Когда набор пуст, все готово.

Answer 10

Создайте список узлов в корне (уровень 0), итерируйте по каждому узлу по очереди и ищите прямых потомков (родительский узел которых является узлом, из которого мы в данный момент ищем) (уровень 1), когда закончите с уровнем 0 переходите к итерации уровня 1 и так далее, пока у вас не останется не посещенных узлов.