Java实现二叉树前序遍历_二叉树前序遍历java

在 Java 中，可以通过递归或使用栈来实现二叉树的前序遍历。下面分别给出这两种方法的实现示例：

递归实现前序遍历：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class BinaryTreeTraversal {

    // 前序遍历递归函数
    public void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " "); // 先访问根节点
        preOrderTraversal(root.left); // 递归遍历左子树
        preOrderTraversal(root.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);

        // 创建 BinaryTreeTraversal 对象
        BinaryTreeTraversal traversal = new BinaryTreeTraversal();

        // 调用前序遍历方法
        System.out.print("前序遍历结果: ");
        traversal.preOrderTraversal(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

使用栈实现前序遍历：

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class BinaryTreeTraversal {

    // 使用栈实现前序遍历
    public void preOrderTraversal(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);

        // 创建 BinaryTreeTraversal 对象
        BinaryTreeTraversal traversal = new BinaryTreeTraversal();

        // 调用前序遍历方法
        System.out.print("前序遍历结果: ");
        traversal.preOrderTraversal(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
52
53
54
55
56

无论使用递归还是栈，前序遍历都是先访问根节点，再访问左子树，最后访问右子树。以上两种方法都可以实现二叉树的前序遍历。