二叉树DFS详细教程_二叉树 dfs

当谈到二叉树DFS详细教程时，我们将涵盖从简单到深入的内容，包括递归和非递归的实现，以及深度优先搜索的不同变体。我们用Java语言实现这些示例。

首先，我们需要定义一个二叉树节点类：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11

二叉树DFS基本概念

在二叉树DFS中，我们使用深度优先搜索算法遍历树的节点。DFS有三种变体：前序遍历（先序遍历）、中序遍历和后序遍历。我们将逐个解释和实现这些变体。

前序遍历（Preorder Traversal）

前序遍历从根节点开始，先访问当前节点，然后递归地遍历左子树和右子树。

public class BinaryTreeDFS {

    // 前序遍历（先序遍历） - 递归实现
    public static void preorderTraversalRecursive(TreeNode root) {
        if (root == null) return;

        System.out.print(root.val + " ");
        preorderTraversalRecursive(root.left);
        preorderTraversalRecursive(root.right);
    }

    // 前序遍历（先序遍历） - 非递归实现
    public static void preorderTraversalIterative(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.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);

        System.out.println("Preorder traversal (recursive):");
        preorderTraversalRecursive(root);

        System.out.println("\nPreorder traversal (iterative):");
        preorderTraversalIterative(root);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

解释：
在上面的代码中，我们实现了前序遍历的两种方式：递归实现preorderTraversalRecursive和非递归实现preorderTraversalIterative。在递归实现中，我们首先检查当前节点是否为空，如果为空，则直接返回。如果节点不为空，则先访问当前节点的值，然后递归地调用preorderTraversalRecursive函数来访问左子树和右子树。在非递归实现中，我们使用一个栈来模拟递归的过程，从根节点开始，将根节点入栈，然后进入循环，直到栈为空。在循环中，我们出栈一个节点，并访问该节点的值，然后将其右子节点（如果存在）压入栈，再将左子节点（如果存在）压入栈。这样，我们就能按照前序遍历的顺序遍历二叉树。

输出结果为：

Preorder traversal (recursive): 1 2 4 5 3

Preorder traversal (iterative): 1 2 4 5 3

中序遍历（Inorder Traversal）

中序遍历从根节点开始，先递归地遍历左子树，然后访问当前节点，最后递归地遍历右子树。

public class BinaryTreeDFS {

    // 中序遍历 - 递归实现
    public static void inorderTraversalRecursive(TreeNode root) {
        if (root == null) return;

        inorderTraversalRecursive(root.left);
        System.out.print(root.val + " ");
        inorderTraversalRecursive(root.right);
    }

    // 中序遍历 - 非递归实现
    public static void inorderTraversalIterative(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            System.out.print(current.val + " ");
            current = current.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);

        System.out.println("Inorder traversal (recursive):");
        inorderTraversalRecursive(root);

        System.out.println("\nInorder traversal (iterative):");
        inorderTraversalIterative(root);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

解释：
在上面的代码中，我们实现了中序遍历的两种方式：递归实现inorderTraversalRecursive和非递归实现inorderTraversalIterative。在递归实现中，我们首先检查当前节点是否为空，如果为空，则直接返回。如果节点不为空，则先递归地调用inorderTraversalRecursive函数来访问左子树，然后访问当前节点的值，最后递归地调用inorderTraversalRecursive函数来访问右子树。在非递归实现中，我们使用一个栈来模拟递归的过程，从根节点开始，将根节点及其所有左子节点入栈，然后进入循环，直到栈为空。在循环中，我们出栈一个节点，并访问该节点的值，然后将其右子节点（如果存在）压入栈，再重复以上过程。这样，我们就能按照中序遍历的顺序遍历二叉树。

输出结果为：

Inorder traversal (recursive): 4 2 5 1 3

Inorder traversal (iterative): 4 2 5 1 3

后序遍历（Postorder Traversal）

后序遍历从根节点开始，先递归地遍历左子树和右子树，最后访问当前节点。

public class BinaryTreeDFS {

    // 后序遍历 - 递归实现
    public static void postorderTraversalRecursive(TreeNode root) {
        if (root == null) return;

        postorderTraversalRecursive(root.left);
        postorderTraversalRecursive(root.right);
        System.out.print(root.val + " ");
    }

    // 后序遍历 - 非递归实现
    public static void postorderTraversalIterative(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);

        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);

            if (node.left != null) {
                stack1.push(node.left);
            }

            if (node.right != null) {
                stack1.push(node.right);
            }
        }

        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }

    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);

        System.out.println("Postorder traversal (recursive):");
        postorderTraversalRecursive(root);

        System.out.println("\nPostorder traversal (iterative):");
        postorderTraversalIterative(root);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

解释：
在上面的代码中，我们实现了后序遍历的两种方式：递归实现postorderTraversalRecursive和非递归实现postorderTraversalIterative。在递归实现中，我们首先检查当前节点是否为空，如果为空，则直接返回。如果节点不为空，则先递归地调用postorderTraversalRecursive函数来访问左子树和右子树，最后访问当前节点的值。在非递归实现中，我们使用两个栈来模拟递归的过程，从根节点开始，将根节点及其所有子节点入栈1，然后进入循环，直到栈1为空。在循环中，我们依次出栈栈1的节点，并将其入栈栈2。当栈1为空时，栈2中的节点即按照后序遍历的顺序出栈，从而实现后序遍历。

输出结果为：

Postorder traversal (recursive): 4 5 2 3 1

Postorder traversal (iterative): 4 5 2 3 1

这就是二叉树DFS的详细教程，我们从简单到深入地涵盖了前序遍历、中序遍历和后序遍历的递归和非递归实现。DFS是解决许多与二叉树相关的问题的重要方法，掌握这些DFS的变体有助于更好地理解二叉树的结构和性质，并在算法和数据结构中应用它们。