有效的方法来遍历对象树？

Question

我有一组TreeNodes，每个TreeNode都有一个id，一组父节点和一组子节点。

对于给定的节点ID，我正在寻找一种有效的方式来生成所有通过该节点的链接。简而言之，从节点开始，遍历所有子节点。如果一个节点有多个孩子，为每个孩子创建一个链接。遍历孩子等。

我也希望能够通过父节点在'向上'的方向做到这一点。

有没有一个简单的算法来做到这一点？

编辑：哦，我想能够输出在给定链中的所有节点的ID的...

Answer 1

你正在寻找一个Breadth First或Depth First Search。起初它不超过以下内容（这是深度优先搜索）。

Visit(Node node) 
{ 
    foreach (Node childNode in node.Children) 
    { 
     Visit(childNode); 
    } 

    DoStuff(node); 
} 

问题是该图可能包含循环，因此该算法将进入无限循环。为了解决这个问题，你必须记住访问过的节点，方法是将它们放在一个集合中。如果图形没有循环 - 例如如果它是一棵树 - 这个简短的算法已经可以工作。

顺便说一句，如果TreeNode有多个父节点，它不是一棵树，而是一个图节点。

Answer 2

嘛，如果节点对其父的引用，它的简单如果没有这样的引用，比你可以使用宽度优先的搜索，为了获得父节点（一旦在树中，每个节点只有一个（或根本没有，如果它是一个根目录的话）parent。

例如，初始设置您的父节点集合。

- 编辑 -

一旦一个节点可能有多个父节点，那么你正在处理一个图。也有graph traversal algorithms（见旁边的表格）。

确保，如果你的图有一个周期，你会不会落得具有无限循环

Answer 3

你可能想看看depthFirstEnumeration()和breadthFirstEnumeration()在DefaultMutableTreeNode。然而，这并不能解决你想以自下而上的方式浏览树的问题。