Java二叉树的遍历

news/2024/7/5 5:00:30

Java二叉树的遍历

大家好，我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编，也是冬天不穿秋裤，天冷也要风度的程序猿！今天，让我们一同探讨Java中二叉树的遍历，解锁这个数据结构的神秘面纱。

Java二叉树的遍历

二叉树是一种常见的数据结构，它包含每个节点最多有两个子节点，分别为左子节点和右子节点。遍历二叉树是对树中节点的有序访问，主要分为三种遍历方式：

前序遍历（Pre-order Traversal）： 先访问根节点，然后递归地前序遍历左子树和右子树。
中序遍历（In-order Traversal）： 先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
后序遍历（Post-order Traversal）： 先递归地后序遍历左子树和右子树，然后访问根节点。

Java代码示例

下面是一个简单的Java代码示例，演示了如何使用递归实现二叉树的前序、中序和后序遍历：

class TreeNode {
    int val;
    TreeNode left, right;

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

public class BinaryTreeTraversal {
    // 前序遍历
    public void preOrderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    }

    // 中序遍历
    public void inOrderTraversal(TreeNode root) {
        if (root != null) {
            inOrderTraversal(root.left);
            System.out.print(root.val + " ");
            inOrderTraversal(root.right);
        }
    }

    // 后序遍历
    public void postOrderTraversal(TreeNode root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.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);

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

        // 输出遍历结果
        System.out.println("前序遍历结果：");
        traversal.preOrderTraversal(root);

        System.out.println("\n中序遍历结果：");
        traversal.inOrderTraversal(root);

        System.out.println("\n后序遍历结果：");
        traversal.postOrderTraversal(root);
    }
}