二叉树的DFS （深度优先遍历）算法 Java 实现

刺骨的言语ヽ痛彻心扉 2023-02-14 10:56 51阅读 0赞

#### 深度优先遍历简介和实现 ####

`深度优先遍历（Depth First Search）简介：`

先从根节点沿着（左或者右）分支走到底，当再也没有叶子节点之后，返回上一节点，如果上一个节点还有另外一个子节点，那么遍历这个节点分支直至再也没有叶子节点，之后重复上面的过程

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NjMxNzk3_size_16_color_FFFFFF_t_70]  
例如上图按照先遍历左分支再遍历右分支的深度优先遍历顺序就是：  
A B D E C F G

不难发现其实就是前序遍历

`实现：`

深度优先遍历的实现方式一般分为递归式和非递归式

`递归式：`

递归实现比较简单，由于是前序遍历，所以我们依次遍历当前节点，左节点，右节点即可，对于左右节点来说，依次遍历它们的左右节点即可，依此不断递归下去，直到叶节点（递归终止条件），代码如下

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。所以我们重点看下非递归实现

`非递归式：`

仔细观察深度优先遍历的特点，对二叉树来说，由于是先序遍历（先遍历当前节点，再遍历左节点，再遍历右节点），所以我们有如下思路

1.  对于每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点（这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求）
2.  弹栈，拿到栈顶的节点，如果节点不为空，重复步骤 1， 如果为空，结束遍历。

package search;
    
    import java.util.Stack;
    
    /** * @author huchenfei * @version 1.0 * @className DeepFirstSearch * @description 二叉树深度遍历算法 * @date 2020/6/2 15:38 **/
    public class DepthFirstSearch { 
    
        private static class Node { 
            /** * 节点值 */
            public int value;
            /** * 左节点 */
            public Node left;
            /** * 右节点 */
            public Node right;
    
            public Node(int value) { 
                this.value = value;
            }
    
        }
    
        public static void main(String... args) { 
            Node head = new Node(1);
            Node second = new Node(2);
            Node three = new Node(3);
            Node four = new Node(4);
            Node five = new Node(5);
            Node six = new Node(6);
            Node seven = new Node(7);
    
            head.right = three;
            head.left = second;
            second.right = five;
            second.left = four;
            three.right = seven;
            three.left = six;
            System.out.println("非递归方式 -> 深度优先遍历结果: ");
            unRecursiveDfs(head);
            System.out.println();
        }
    
        /** * 非递归的使用栈来实现 DFS * 依据栈的先进后出特性 * 1. 将二叉树的头结点放入栈中 * 2. 将头结点 1 从栈中弹出，并查看头结点是否有左右节点，将右节点和左节点压入栈中【3，2】 * 3. 将头结点 2 从栈中弹出，并查看 2 节点是否有左右节点，将右节点和左节点压入栈中【3，5，4】 * 4. 将头结点 4 从栈中弹出，无左右节点【3，5】 * 5. 将头结点 5 从栈中弹出，无左右节点【3】 * 6. 将头结点 3 从栈中弹出，并查看 3 节点是否有左右节点，将右节点和左节点压入栈中【7，6】 * 7. 将头结点 6 从栈中弹出，无左右节点【7】 * 8. 将头结点 7 从栈中弹出，无左右节点 * * @param head 二叉树 */
        public static void unRecursiveDfs(Node head) { 
            if (head == null) { 
                return;
            }
    
            Stack<Node> stack = new Stack<>();
            // 先将根结点压入栈中
            stack.push(head);
            while (!stack.isEmpty()) { 
                Node node = stack.pop();
                System.out.print(node.value);
                System.out.print(" ");
    
                // 将节点右边的压入栈中
                if (node.right != null) { 
                    stack.push(node.right);
                }
    
                // 压入左边的栈中
                if (node.left != null) { 
                    stack.push(node.left);
                }
            }
        }
    }

#### 拓展： ####

[二叉树的 BFS （广度优先遍历）算法 Java 实现][BFS _ Java]

--------------------

参考：

[二叉树的广度优先遍历和深度优先遍历(Java实现)][Java]  
[图文详解 DFS 算法 和 BFS 算法][DFS _ _ BFS]  
[二叉树的深度优先搜索和广度优先搜索（java实现）][java]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NjMxNzk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602185749106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NjMxNzk3,size_16,color_FFFFFF,t_70
[BFS _ Java]: https://blog.csdn.net/qq_27631797/article/details/106502909
[Java]: https://blog.csdn.net/weixin_39912556/article/details/82852749
[DFS _ _ BFS]: https://mp.weixin.qq.com/s/PD1IYUhpRpbop4LkDnaAJA
[java]: https://blog.csdn.net/double_sweet1/article/details/89297846