DFS没有内存的树

我正在尝试编写一个函数来遍历深度优先搜索的树。DFS没有内存的树

我现在的算法进行类似：

If children 
go to first child 

If no children 
go to next sibling 

If no siblings 
go to parent

我遇到的问题是，我不能标记的树节点被访问了已经，所以当我去到父的周期只是重新设置，然后再次回到孩子身上，陷入循环。有没有人有任何想法可以解决这个问题？

（它使用ANTLR插件是在Java）

编辑：

继我写这个的建议之一：

public void traverseTree(Tree tree){ 

    if (tree.getChildCount() > 0){ 
     tree = tree.getChild(0); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
    if (tree.getParent().getChild(tree.getChildIndex() + 1) != null){ 
     tree = tree.getParent().getChild(tree.getChildIndex() + 1); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
    if (!tree.getParent().toString().contains("ROOT_NODE")){ 
     tree = tree.getParent(); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
}

根节点为根节点的名称，但我收到堆栈溢出错误。任何人有任何想法为什么？

谢谢。

来源

2012-03-15 djcmm476

如果你不需要担心周期或其他问题，那么最简单的方法就是像@PeterLawrey所建议的那样使用递归方法。清洁和简单。如果你不能使用递归，你仍然可以使用一个单独的堆栈来维护相同的信息，包括返回的链接列表，如果节点没有反向链接的话。 – 2012-03-15 15:46:05

会在这种情况下使用递归。

class Node { 
    public List<Node> getChildren() { .... } 

    public void traverse(Visitor<Node> visitor) { 
     // If children 
     // go to first child - by traversing the children first. 
     for(Node kid: getChildren()) 
      kid.traverse(visitor); 
      // If no children 
      // go to next sibling, - by continuing the loop. 

     visitor.visit(this); 
     // If no siblings 
     // go to parent - by returning and letting the parent be processed 
    } 
} 


interface Vistor<N> { 
    public void visit(N n); 
}

来源

2012-03-15 15:43:12

这看起来不错，我不知道我100％理解它。你能解释一下它在做什么吗？（对不起，我只是读代码非常糟糕）。 – djcmm476 2012-03-15 15:52:21

我已添加评论。您可能会发现在调试器中遍历代码以确切查看它在做什么很有用。 – 2012-03-15 15:56:12

嗯，我试过把它写在一个java文件中来理解它，但是我很难让它运行，它不识别Visitor或getChildren（）（尽管我认为我只需要改变它到奇怪的ANTLR格式）。 – djcmm476 2012-03-15 16:08:01

使用hash_table地图中的每个顶点表示布尔无论我参观与否

来源

2012-03-15 15:42:59

在树形搜索中，这不是必需的。 – 2012-03-15 15:44:13

编写一个深度优先的迭代器，用于在内部跟踪访问节点。这样树不需要改变就知道它正在被监视。

来源

2012-03-15 15:48:33 duffymo

如果“不记得”可以解释为O（1）内存，那么改变可能会帮助：

记住不仅是当前节点，也是节点，在你
导线孩子们又来到只有当你不是来自其中一个人时

来源

2012-03-15 15:54:47 maxim1000

DFS没有内存的树

回答

相关问题