在二叉树上进行深度优先搜索
我有以下深度优先搜索算法的实现:
public static void printDFS(Node root) {
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while(!stack.isEmpty()) {
Node curr = stack.pop();
System.out.println(curr.getValue()) ;
if (curr.getLeft() != null) {
stack.push(curr.getLeft());
}
if (curr.getRight() != null) {
stack.push(curr.getRight());
}
}
}
当我在一棵看起来像这样的树上运行它时:
0
/
6 7
/ /
5 4 3 2
我得到访问输出为:0 - > 7 - > 2 - > 3 - > 6 - > 4 - > 5
这是一个'正确的'DFS排序? 我会期望输出是一个预序遍历(即0 - > 6 - > 5 - > 4 - > 7 - > 3 - > 2),我知道我可以通过首先推动右节点每个子树。 但是我想知道的是DFS算法中正确的访问顺序是什么?
正如在另一个答案中已经提到的,访问 - >遍历顺序是“反转”的原因在于,您正在使用堆栈来跟踪“当前节点”。
让我引导你通过你的示例树:
0
/
6 7
/ /
5 4 3 2
stack.push(root)
导致以下堆栈状态:
0: 0 <-- (root) and Top of stack
你弹出堆栈并放入curr
。 在遍历方面,你现在处于这种状态:
0 <--
/
6 7
/ /
5 4 3 2
然后继续将curr.getLeft()
添加到堆栈,然后添加curr.getRight()
。 这导致以下堆栈状态:
1: 7 <--(curr.getRight()) <-- Top of stack
0: 6 <--(curr.getLeft())
重复同样的步骤,我们得到以下遍历状态:
0
/
6 7<--
/ /
5 4 3 2
并添加节点后:
2: 2 <-- Top of stack
1: 3
0: 6 <-- (initial getLeft())
因为两个节点都没有孩子,从堆栈弹出它们并输出它们让我们看到下面的遍历状态:
0
/
-->6 7
/ /
5 4 3 2
其余的是历史;)
正如你专门询问DFS的“正确”方式(或排序):没有。 你首先定义你穿过的深度。
没有这种“正确的DFS排序”。 DFS的主要想法是深入; 在兄弟姐妹之前访问任何给定节点的孩子。 一旦你深入图表并且遇到了一片叶子,就会以相同的方式回溯并检查最近的同胞。
您选择首先检查哪个孩子的方式会导致不同的遍历命令(或树)。 不用说,所有遍历方法都会在图上生成一棵生成树。 预订遍历,你正在比较的,可能是最知名的DFS订单(或者至少这是我所见过的)。 其他人是有效的,但不太受欢迎。
这是一个堆栈。 你最后推动的将首先弹出
链接地址: http://www.djcxy.com/p/82651.html