9

更新：
我发现了更多我想要实现的示例：Managing Hierarchical Data in MySQL。我想这样做，但在 JavaScript 中，因为我正在构建一个应用程序，它接受分层结构的评论，更具体地说是 reddit.com。如果您的 chrome Web 浏览器上有 Pretty JSON 扩展，请转到 reddit 并单击线程评论，然后将 .json 添加到 url 以查看我正在解析的内容。
我得到 JSON 数据就好了，它只是解析注释并添加适当的 HTML 以显示它的嵌套。
解决方案的想法？

旧问题：
我正在编写一个程序，并且在编写代码之前我需要弄清楚逻辑。我正在接受树格式的数据，但每个父节点可能有几个子节点，我似乎可以找到的唯一树是具有权重的树或树，其中每个节点最多有两个子节点。所以我试图找出算法来评估树的每个节点，如下所示：

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

现在，当我尝试写出我的算法将如何工作时，我最终编写了嵌套的 for/while 循环，但我最终为树的每个高度级别编写了一个循环，该循环用于动态数据和高度未知且数量未知的树每个节点的孩子这不起作用。我知道在某个时候我学会了如何像这样遍历一棵树，但它现在完全逃离了我。任何人都知道这是如何在循环方面完成的？

4

4 回答 4

17

如果您不打算使用递归，则需要一个辅助数据结构。队列将为您提供广度优先遍历，而堆栈将为您提供深度优先遍历。无论哪种方式，它看起来大致是这样的：

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

维基百科参考

于 2011-01-27T17:33:51.980 回答
8

使用递归，而不是循环。
广度优先搜索
深度优先搜索
这些应该可以帮助您开始尝试完成的工作

于 2011-01-27T17:31:25.413 回答
1

只需使用递归

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)
于 2011-01-27T17:31:30.767 回答
1

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

于 2011-01-27T17:33:27.530 回答