java - DFS 一棵没有内存的树

Question

我正在尝试编写一个函数来通过深度优先搜索遍历树。

我目前的算法是这样的:

If children
 go to first child

If no children
 go to next sibling

If no siblings
 go to parent

我遇到的问题是我无法将树上的节点标记为已访问过，所以当我转到父节点时，循环会重置并再次转到子节点，陷入循环.有谁知道我该如何解决这个问题？

(它在 java 中使用 ANTLR 插件)

编辑:

按照我写的其中一条建议:

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());
    }
}

Root node 是根节点的名称，但我收到堆栈溢出错误。有人知道为什么吗？

谢谢。

Answer 1

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

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);
}