在二叉树上进行深度优先搜索

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

 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

上一篇: Depth First Search on a Binary Tree

下一篇: CORS enabled Web API fails to add header