algorithm - 二叉树上的深度优先搜索

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

如 another answer 中所述您的访问 -> 遍历顺序“反转”的原因在于您正在使用 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())

因为两个节点都没有 child ，从堆栈中弹出它们并输出它们让我们进入以下遍历状态:

                    0 
                  /   \
              -->6     7
                / \   / \
               5   4 3   2

剩下的就是历史了；)

正如您特别询问 DFS 的“正确”方式(或顺序):没有。您定义首先遍历深度的一侧。