深度优先搜索二叉树

Question

我有以下深度优先搜索算法的实现:

 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算法中的正确访问顺序是什么？

Answer 1

正如在另一个答案中已经提到的，您的访问 -> 遍历顺序“颠倒”的原因在于您使用 Stack 来跟踪“当前节点”。

让我带您浏览示例树：

                    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 的“正确”方式（或排序）：没有。您首先定义遍历到深度的哪一侧。