java 如何在java中的二叉树上实现深度优先搜索（DFS）？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15237431/
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
How to implement depth-first search (DFS) on a binary tree in java?
提问by Accessdenier
According to what is explained in the wikipedia article about depth-first search, I think DFS on a binary tree is identical to a preorder traversal root--left--right (am I right?).
根据维基百科关于深度优先搜索的文章的解释，我认为二叉树上的 DFS 与前序遍历根 - 左 - 右（对吗？）相同。
But I just did a little search and got this code, the author of which claims that DFS needs a tree to record if the node has been visited before (or do we need this in the case of a graph?).
但我只是做了一点搜索并得到了这段代码，其作者声称 DFS 需要一棵树来记录之前是否访问过该节点（或者我们是否需要在图形的情况下使用它？）。
// copyright belongs to the original author
public void dfs() {
// DFS uses Stack data structure
Stack stack = new Stack();
stack.push(this.rootNode);
rootNode.visited=true;
printNode(rootNode);
while(!stack.isEmpty()) {
Node node = (Node)s.peek();
Node child = getUnvisitedChildNode(n);
if(child != null) {
child.visited = true;
printNode(child);
s.push(child);
}
else {
s.pop();
}
}
// Clear visited property of nodes
clearNodes();
}
Could anybody explain this?
有人可以解释一下吗？
回答by bruce_ricard
Yes it is preorder. But, I don't really like to say that its a traversal since you might not traverse the tree, you stop as soon as you find your element. The program that you printed is not a search, it's a traversal : you're printing everything. A search function to search in a binary tree would be :
是的，它是预购。但是，我真的不想说它是遍历，因为您可能不会遍历树，一旦找到元素就停止。您打印的程序不是搜索，而是遍历：您正在打印所有内容。在二叉树中搜索的搜索函数是：
public boolean search(Tree t, int i) {
if(t == null)
return false;
elif(t.value() == i)
return true;
else
for(child in t.children()) {
if(search(child,i))
return true;
}
return false;
//return search(t.leftTree(), i) or search(t.rightTree(),i) binary tree case
}
回答by user207421
I think dps on a binary tree is the same one with preorder traversal root--left--right.(am i right?)
我认为二叉树上的 dps 与前序遍历 root--left--right 相同。（我对吗？）
Depth-first search can be pre-, in-, or post-order traversal. You don't need a stack: it's easier to implement it recursively, in which case you don't need to mark nodes as visited either.
深度优先搜索可以是前序、内序或后序遍历。您不需要堆栈：递归实现它更容易，在这种情况下，您也不需要将节点标记为已访问。
