Java 深度优先问题递归遍历树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9724421/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Traversing a tree recursively in depth first problems
提问by djcmm476
I'm trying to traverse a tree using ANTLR tree commands and recursion. The code I currently have is:
我正在尝试使用 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);
}
}
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?
但是，好吧，它不起作用。我在树中得到了很多条目，但没有明显的顺序。谁能看到我哪里出错了？
Thanks.
谢谢。
EDIT:
编辑：
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));
}
}
采纳答案by David Moles
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.
确保它永远不会上升的最简单方法是确保您永远不会调用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);
}
}
}
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.
递归的全部意义在于您不需要返回。当traverseTree()这个级别结束时，前一级别的循环将继续到下一个同级。
(Note that the ifisn'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.)
（请注意，if实际上并不是必需的，除非你想在到达叶节点时做一些特别的事情。我只是把它放在那里，所以评论会让发生的事情变得很明显。从概念上讲，递归到首先弄清楚您如何知道何时停止递归。）
回答by darijan
Try this:
尝试这个：
int counter = 0;
public void traverseTree(Tree tree) {
for (int i=0; i<tree.getChildCount(); i++) {
Tree child = tree.getChild(i);
System.out.println(tree.toString() + counter++);
traverseTree(tree);
}
}
回答by Thomas
It looks like you're printing out the same nodes several times. If you just want to print out the nodes as you go down,
看起来您多次打印出相同的节点。如果您只想在下降时打印出节点，
1
2 3
4 5 6
Depth first - 1 2 4 5 3 6
Breadth first - 1 2 3 4 5 6
//For depth first
public void traverseTree(Tree tree){
System.out.println(tree.toString());
for (int x = 0; x < tree.getChildCount(); x++)
traverseTree(tree.getChild(x));
}
To switch to 4 5 6 2 3 1, just move the println to after the for loop.
要切换到 4 5 6 2 3 1，只需将 println 移动到 for 循环之后。
