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

Question

Обновление:
Я нашел еще один пример того, что я пытаюсь осуществить: Управление иерархическими данными в 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]

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

Answer 1

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

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

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

• Queue
• Stack

Answer 2

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

Answer 3

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

Answer 4

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

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)