以递归方式遍历树的第一个问题 [英] Traversing a tree recursively in depth first problems

问题描述

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

I'm trying to traverse a tree using ANTLR tree commands and recursion. The code I currently have is:

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

        }
    }

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

But, well, it's not working. I'm getting a lot of the entries in the tree, but in no obvious order. Can anyone see where I'm going wrong?

谢谢。

编辑：

我在下面做的评论应该是从这里开始的：

Comment I made below that should have been here to begin with:

抱歉，我应该删除打印声明，它们只是那里尝试调试它。我遇到的问题是它应该只搜索它启动的节点和该节点的任何兄弟节点，它不应该上升到一个级别，但确实如此，它会打印所有内容。 （我会把它编辑成主要内容，应该一直在那里开始，抱歉）。

Sorry, I should have removed the print statements, they were just there to try and debug it. The problem I'm encountering is that it should only search the node it starts on and any siblings of that node, it shouldn't go up a level, but it does, it prints everything. (I'll edit this into the main, it should have been there to begin with, sorry).

我设法让代码最终正常工作：

I managed to get the code working eventually like so:

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

推荐答案

确保它永远不会升级的最简单方法是确保你永远不会调用 getParent（）。如果你不知道有一个上层，你就不能去那里。

The easiest way to ensure it never goes up a level is to ensure you never call getParent(). If you have no idea there's an upper level, you can't go there.

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（）结束时，上一级别的循环将继续到下一个兄弟。

The whole point of recursion is that you don't need to go back up. When traverseTree() at this level finishes, the loop in the previous level will continue on to the next sibling.

（注意 if 实际上并不是必需的，除非你想要在到达叶子节点时做一些特别的事情。我只是把它放在那里所以注释会使它成为显而易见的是，从概念上讲，通过弄清楚你何时知道何时停止递归，在递归中总是一个好主意。）

(Note that the if isn't actually necessary, unless you want to do something special when you reach a leaf node. I just put it there so the comment would make it obvious what's going on. Conceptually, it's always a good idea in recursion to start by figuring out how you know when to stop recursing.)

这篇关于以递归方式遍历树的第一个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！