深度优先遍历

1. 引言

在图和树等数据结构中，遍历是一个基本的操作。遍历的目的是按照某种顺序访问数据结构中的每个元素。对于树或图这样的层次性结构，深度优先遍历（Depth-First Search，简称 DFS）是一种非常常用的遍历方式，它通过优先深入到每一个子节点或邻接节点，直到不能再深入为止，然后回退并继续遍历。

在本节课中，我们将深入了解深度优先遍历的基本概念、实现方式及其在树和图中的应用。通过代码案例，我们将展示如何使用深度优先遍历来解决实际问题。

2. 深度优先遍历的基本概念

深度优先遍历的核心思想是“深度优先”，即在遍历的过程中，尽量先访问一个节点的子节点，直到没有子节点可以访问时，再回退到父节点，继续遍历其他子节点。可以通过栈或递归来实现这一过程。

2.1 递归与栈

递归：深度优先遍历的递归实现比较直观，递归会自动帮我们处理回退过程。当遍历到一个节点时，递归会深入到该节点的子节点，直到子节点没有未访问的节点为止，然后再返回到父节点，继续遍历。
栈：如果使用栈来实现深度优先遍历，首先将根节点或起始节点压入栈中，随后依次出栈并访问该节点的子节点，再将未被访问的子节点压入栈中，直到栈为空为止。

2.2 深度优先遍历的基本步骤

从根节点（或任意起始节点）开始，访问当前节点。
对当前节点的每一个子节点（或邻接节点）进行递归（或栈式）遍历。
如果一个节点的所有子节点都已经遍历完，则回退到父节点，继续遍历其它未访问的子节点。
遍历直到所有节点都被访问过。

3. 深度优先遍历在树和图中的应用

3.1 深度优先遍历在树中的应用

树是一种典型的层次性数据结构，在树的遍历中，深度优先遍历是非常常用的一种方式。树的遍历可以分为几种类型：

前序遍历：先访问根节点，再遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

这些遍历方式都可以通过深度优先遍历来实现。

3.2 深度优先遍历在图中的应用

深度优先遍历不仅在树结构中有广泛的应用，在图的遍历中也有着重要的作用。图是由节点和边构成的复杂数据结构，通常有多个路径可以从一个节点到达其他节点。深度优先遍历可以帮助我们找到图中的路径、连通分量等信息，广泛用于图的搜索、路径寻找等算法中。

4. 深度优先遍历的实现

4.1 栈实现深度优先遍历

首先，我们通过栈来实现深度优先遍历。栈实现的深度优先遍历主要步骤是：

将根节点压入栈中。
每次从栈中弹出一个节点，访问该节点。
将该节点的未访问过的子节点依次压入栈中，继续弹出栈中的节点，直到栈为空。

4.1.1 Java 代码实现 - 栈实现深度优先遍历

import java.util.Stack;

class TreeNode {
    int value;
    TreeNode left, right;

    public TreeNode(int value) {
        this.value = value;
        this.left = this.right = null;
    }
}

class BinaryTree {
    TreeNode root;

    // 非递归的深度优先遍历（前序遍历）
    public void depthFirstTraversal() {
        if (root == null) return;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);  // 将根节点压入栈
        
        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();  // 从栈中弹出节点
            System.out.print(currentNode.value + " ");  // 访问节点
            
            // 先将右子节点压入栈，因为栈是后进先出，先访问左子树
            if (currentNode.right != null) {
                stack.push(currentNode.right);
            }
            // 将左子节点压入栈
            if (currentNode.left != null) {
                stack.push(currentNode.left);
            }
        }
    }

    // 插入节点
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }
        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }
        return root;
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        
        // 插入节点
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
        
        System.out.println("深度优先遍历结果：");
        tree.depthFirstTraversal();  // 输出：50 30 20 40 70 60 80
    }
}

4.2 代码解释

在这段代码中，我们使用了栈来实现深度优先遍历。首先，我们创建了一个 Stack 来保存待访问的节点。我们将根节点压入栈中，然后开始循环，当栈非空时，我们从栈中弹出一个节点，访问它，并将它的右子节点和左子节点依次压入栈中。这样就能够按照深度优先的顺序遍历整个树。

4.3 递归实现深度优先遍历

递归是实现深度优先遍历的另一种方法。通过递归，我们可以简化代码，并且使得逻辑更加直观。

4.3.1 Java 代码实现 - 递归实现深度优先遍历

class BinaryTree {
    TreeNode root;

    // 递归的深度优先遍历（前序遍历）
    public void depthFirstTraversal() {
        depthFirstRec(root);
    }

    private void depthFirstRec(TreeNode node) {
        if (node == null) return;  // 如果节点为空，返回
        System.out.print(node.value + " ");  // 访问当前节点
        depthFirstRec(node.left);  // 递归遍历左子树
        depthFirstRec(node.right);  // 递归遍历右子树
    }
}

在这个递归实现中，递归方法 depthFirstRec 处理每个节点，访问节点后递归调用左子树和右子树。这种方式相比栈实现更加简洁，因为递归能够自动处理栈的压入和弹出。

5. 深度优先遍历的复杂度分析

时间复杂度：深度优先遍历的时间复杂度为 O(n)，其中 n 是树或图中节点的数量。因为每个节点都会被访问一次。
空间复杂度：空间复杂度主要取决于栈的使用情况。在最坏的情况下（树形结构非常不平衡），空间复杂度为 O(n)。如果树是平衡的，空间复杂度为 O(log n)，因为递归深度为树的高度。