Алгоритм обхода дерева

Обновление:
Я нашел еще один пример того, что пытаюсь реализовать: Управление иерархическими данными в MySQL. Я хочу сделать это, но на JavaScript, потому что я создаю приложение, которое принимает комментарии, которые находятся в иерархической структуре, а точнее на reddit.com. Если у вас есть расширение Pretty JSON в вашем браузере Chrome, перейдите на Reddit и нажмите на комментарии к темам, а затем добавьте .json к URL-адресу, чтобы увидеть, что я анализирую.
Я получаю данные JSON в порядке, это просто парсинг через комментарии и добавив соответствующий HTML-код, чтобы показать, что он вложен.
Идеи для решений?

СТАРЫЙ вопрос:
Я работаю над программой и дошел до того, что мне нужно выяснить логику, прежде чем писать код. Я беру данные в формате дерева, но с возможностью наличия нескольких дочерних узлов для каждого родительского узла, и единственное дерево, в котором я могу найти данные, - это дерево с весами или дерево, где максимум у каждого узла есть два дочерних узла. Итак, я пытаюсь выяснить алгоритм для оценки каждого узла дерева следующим образом:

startingParent[15] // [# of children]
    child1[0]
    child2[5]
       child2ch1[4]
       ...
       child2ch5[7]
    child3[32]
    ...
    child15[4]

Теперь, когда я пытаюсь написать, как будет работать мой алгоритм, я в конечном итоге пишу вложенные циклы for / while, но в итоге я пишу цикл для каждого уровня высоты дерева, который для динамических данных и деревьев неизвестной высоты с неизвестным числом детей на узел это не работает. Я знаю, что в какой-то момент я научился пересекать такое дерево, но сейчас это полностью ускользает от меня. Кто-нибудь знает, как это делается с точки зрения петель?


algorithm tree multiway-tree
person HuXu7    schedule 27.01.2011    source источник

Ответы (4)


arrow_upward
17
arrow_downward

Если вы не собираетесь использовать рекурсию, вам понадобится вспомогательная структура данных. Очередь предоставит вам обход в ширину, тогда как стек предоставит вам обход в глубину. В любом случае это выглядит примерно так:

structure <- new stack (or queue)
push root onto structure
while structure is not empty
  node <- pop top off of structure
  visit(node)
  for each child of node
     push child onto structure
loop

Ссылки на Википедию

person Mark Peters    schedule 27.01.2011

arrow_upward
8
arrow_downward

Используйте рекурсию, а не циклы.
Поиск в ширину
Глубокий поиск
Они должны помочь вам начать работу с тем, чего вы пытаетесь достичь.

person Jean-Bernard Pellerin    schedule 27.01.2011
comment
Если это не домашнее задание, и он определенно хочет DFS. Однако он специально спросил, как это сделать с помощью петель. В любом случае BFS плохо справляется с рекурсией. - person Mark Peters; 27.01.2011
comment
Да, это не домашнее задание, это для приложения, которое я создаю, и я пытаюсь заполнить список, который похож на страницу комментариев, поэтому есть уровни ответов. Основной комментарий, ответ, ответ на этот ответ и т. Д. Итак, я искал способ проанализировать комментарии и создать соответствующий HTML-код для структуры. - person HuXu7; 01.02.2011

arrow_upward
1
arrow_downward

Просто используйте рекурсию, например

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)
person Elalfer    schedule 27.01.2011
comment
Просто небольшая настройка, но обычно она намного чище, если что-то делать вне этого цикла. Таким образом упускается корневой узел. - person Mark Peters; 27.01.2011

arrow_upward
1
arrow_downward

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

person Jerry Coffin    schedule 27.01.2011