java - 递归遍历树的深度优先问题

Question

我正在尝试使用 ANTLR 树命令和递归来遍历树。我目前的代码是:

public void traverseTree(Tree tree){
        int counter = 0;
        System.out.println(tree.toString());
        if (tree.getChildCount() > 0 && tree.getChild(0) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getChild(0);
            traverseTree(tree);

        }
        while (tree.getParent().getChild(tree.getChildIndex() + 1) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getParent().getChild(tree.getChildIndex() + 1);
            traverseTree(tree);

        }
    }

但是，好吧，它不起作用。我在树中得到了很多条目，但没有明显的顺序。谁能看出我哪里出错了？

谢谢。

编辑:

我在下面发表的评论应该从这里开始:

抱歉，我应该删除打印语句，它们只是用来尝试调试它的。我遇到的问题是它应该只搜索它开始的节点和该节点的任何兄弟节点，它不应该上升一个级别，但它会打印所有内容。 (我会把它编辑到主体中，它应该从那里开始，抱歉)。

我设法让代码最终像这样工作:

public void traverseTree(Tree tree){
        System.out.println(tree);
        if (tree.getChild(0) != null){
            traverseTree(tree.getChild(0));
        }
        if(tree.getParent().getChildCount() > 1){
            if(tree.getParent().getChild(tree.getChildIndex() + 1) != null)
            traverseTree(tree.getParent().getChild(tree.getChildIndex() + 1));
        }
    }

Answer 1

确保它永远不会上升的最简单方法是确保您永远不会调用 getParent()。如果你不知道还有上层，你就不能去那里。

public void traverseTree(Tree tree) {

    // print, increment counter, whatever
    System.out.println(tree.toString());

    // traverse children
    int childCount = tree.getChildCount();
    if (childCount == 0) {
        // leaf node, we're done
    } else {
        for (int i = 0; i < childCount; i++) {
            Tree child = tree.getChild(i);
            traverseTree(child);
        }
    }
}

递归的全部意义在于你不需要返回。当这一层的 traverseTree() 结束时，上一层的循环将继续到下一个兄弟。

(请注意，if 实际上不是必需的，除非您想在到达叶节点时做一些特殊的事情。我只是把它放在那里，以便注释可以清楚地表明发生了什么. 从概念上讲，在递归中首先弄清楚你如何知道何时停止递归总是一个好主意。)