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

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) 
} 

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

Breadth First Search

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

Вот действительно нерекурсивен подход: нет стеки, постоянное пространство. Этот код 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 

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