深度优先问题递归遍历树 [英] 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屋！