树遍历算法

Question

更新：
我找到了一个更好的例子来说明我的问题：在MySQL中管理分层数据。我想用JavaScript来实现这个，因为我正在构建一个应用程序，它接收以分层结构形式呈现的评论，具体来说是reddit.com。如果你在Chrome浏览器上安装了Pretty JSON扩展程序，请转到reddit并点击一个线程的评论，然后将.url后面加上.json，就可以看到我正在解析的内容。
我已经成功获取了JSON数据，但只是通过评论进行解析并添加适当的HTML代码以显示其嵌套关系。
有什么解决方案吗？

---

旧问题：
我正在开发一个程序，遇到了需要在编写代码之前确定逻辑的部分。
我正在处理一种树形格式的数据，但每个父节点可能会有多个子节点，并且我能找到的唯一的树形数据要么带权值，要么最多每个节点只有两个子节点。所以我正在尝试找出评估此类树的每个节点的算法：

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

现在，当我试图写出我的算法如何工作时，我最终会写出嵌套的for/while循环，但是对于动态数据和高度未知且每个节点具有未知数量的子节点的树，我需要为每个高度级别编写一个循环，这并不可行。我知道在某个时候我学过如何遍历这样的树，但现在完全逃脱了我的记忆。有人知道如何使用循环来完成吗？

- HuXu7

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

维基百科参考资料

• 队列
• 栈

- Mark Peters

Answer 2

使用递归而不是循环。
广度优先搜索
深度优先搜索
这些应该能帮助您开始实现您的目标。

- Jean-Bernard Pellerin

---

如果这不是作业而且他想要深度优先搜索，那肯定可以。不过他确实要求用循环实现。广度优先搜索也不适合使用递归。 - Mark Peters

是的，这不是作业，而是我正在构建一个应用程序，我正在尝试填充一个列表，就像评论页面一样，因此有回复级别。主要评论、回复、在该回复上的回复等等。因此，我正在寻找一种方法来解析评论并为结构构建适当的HTML。 - HuXu7

Answer 3

只需像递归一样使用即可

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

- Elalfer

---

只是一个小调整，但通常将“做某事”的部分放在循环之外会更加清晰。这样做会避免错过根节点。 - Mark Peters

Answer 4

大多数树遍历的最简单代码通常是递归的。对于像你这样的多路树，通常最容易的方法是使用一个循环来查看每个指向子节点的指针，并将该节点作为参数调用自身，以处理所有子节点。

- Jerry Coffin