以递归方式遍历树的第一个问题

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实际上并不是必需的,除非你想要在到达叶节点时做一些特别的事情.我只是把它放在那里所以注释会让它显而易见.从概念上讲,它总是一个好主意递归到首先弄清楚你怎么知道何时停止递归.)