当前位置:   article > 正文

二叉树DFS详细教程_二叉树 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的变体有助于更好地理解二叉树的结构和性质,并在算法和数据结构中应用它们。

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号