树遍历算法

更新：
我发现更多的例子，我试图拉开：Managing Hierarchical Data in MySQL。我想这样做，但在JavaScript中，因为我正在构建一个应用程序，该应用程序需要处于层次结构中的注释才能成为更具体的reddit.com。如果你的chrome web浏览器上有漂亮的JSON扩展，请转到reddit并单击一个线索评论，然后将.json添加到该URL以查看我正在解析的内容。
我得到的JSON数据很好，它只是解析通过评论，并添加适当的HTML来显示它的嵌套。
解决方案的想法？树遍历算法

老问题：
我工作的一个程序，我都来，我需要找出逻辑之前我写的代码的一部分。我正在采取树形格式的数据，但每个父节点可能有几个子节点，而且我可以在树上查找具有权重或树的数据，而每个节点至多有两个子节点。所以我想弄清楚的算法来评估这样的树的每个节点：当我尝试写出来我的算法是如何工作的我写出来嵌套的

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

现在/ while循环，但我最终为树的高度的每个级别写一个循环，对于未知高度的动态数据和树，每个节点的子节点数量未知，这是行不通的。我知道在某个时候我学会了如何遍历这样一棵树，但现在它完全逃脱了我。任何人都知道这是如何完成循环？

来源

2011-01-27 HuXu7

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

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

来源

2011-01-27 17:33:51

使用递归，而不是循环。
Breadth first search
Depth first search
这些应该可以帮助你开始你要完成

来源

2011-01-27 17:31:25

如果不是功课，他希望一个DFS，绝对。不过他确实特别要求采用循环方法。 BFS用递归方式做得不好。 – 2011-01-27 17:37:51

是的，这不是家庭作业，这是为我正在建立的应用程序，我试图填充一个列表，好像评论页面，所以有回复的级别。主要评论，回复，回复该回复等所以我一直在寻找一种解析评论的方法，并为结构构建适当的HTML。 – HuXu7 2011-02-01 15:53:11

只需使用递归像

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

来源

2011-01-27 17:31:30 Elalfer

对于大多数树的遍历的最简单的代码通常是递归的。对于像你这样的多路树，通常最简单的方法是查看每个指向子节点的指针，然后使用该节点作为参数调用其所有子节点。

来源

2011-01-27 17:33:27

回答

相关问题