算法【Java】—— 二叉树的深搜

二叉树是数据结构中的一种重要形式，它由节点（Node）组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。深度优先搜索（Depth First Search, DFS）是一种遍历二叉树的方式，能够在树的每个分支上尽可能深入地进行搜索。本文将介绍如何用 Java 实现二叉树的深度优先搜索，并提供相应的代码示例。

深度优先搜索的基本思想

深度优先搜索可以通过递归或栈的方式来实现。其基本思想是在访问某个节点后，优先访问该节点的左子节点，直到没有左子节点为止，然后再回溯到父节点，访问右子节点。这个过程可以用递归简单地实现。

二叉树结构的定义

在开始前，我们先定义一个二叉树节点的类 TreeNode：

class TreeNode {
    int val; // 节点的值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点

    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

递归实现深度优先搜索

接下来，我们可以实现一个递归的 DFS 方法。这个方法将在遍历过程中打印出每个节点的值。

public class BinaryTreeDFS {

    // 深度优先搜索
    public void dfs(TreeNode node) {
        if (node == null) {
            return; // 基本情况：如果节点为空，直接返回
        }
        // 访问当前节点
        System.out.print(node.val + " "); // 打印当前节点值
        // 递归访问左子树
        dfs(node.left);
        // 递归访问右子树
        dfs(node.right);
    }

    // 测试主程序
    public static void main(String[] args) {
        // 创建一个简单的二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        BinaryTreeDFS treeDFS = new BinaryTreeDFS();
        System.out.println("深入优先搜索的结果为：");
        treeDFS.dfs(root); // 输出：1 2 4 5 3
    }
}

以上代码中，我们定义了一个二叉树的结构，并创建了一颗简单的二叉树。dfs 方法用于递归遍历树的每个节点。在 main 方法中，我们创建了一棵树并调用 dfs 方法来执行深度优先搜索。

非递归实现深度优先搜索

除了递归方法外，我们还可以使用栈来实现 DFS。下面是非递归实现的代码示例：

import java.util.Stack;

public class BinaryTreeDFSNonRecursive {

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(node); // 将根节点推入栈

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop(); // 弹出栈顶节点
            System.out.print(current.val + " "); // 打印当前节点值

            // 注意：先推入右子节点，再推入左子节点，这样左子节点会被优先访问
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }

    // 测试主程序
    public static void main(String[] args) {
        // 创建一个简单的二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        BinaryTreeDFSNonRecursive treeDFS = new BinaryTreeDFSNonRecursive();
        System.out.println("深入优先搜索的结果为：");
        treeDFS.dfs(root); // 输出：1 2 4 5 3
    }
}

在这个非递归的实现中，我们利用 Stack 数据结构来保存需要遍历的节点。首先将根节点入栈，然后在循环中弹出和访问节点，再将右子节点和左子节点依次入栈，以保证左子节点优先被访问。

总结

深度优先搜索是遍历二叉树的基本方法之一，可以用递归和非递归两种方式实现。在大多数情况下，递归实现更为简洁和易于理解，而非递归实现则在某些情况下（如避免栈溢出）可能更有优势。无论是使用哪种方式，理解 DFS 的工作原理都是学习数据结构和算法的重要一步。