掌握Java树结构（从零开始的Java树算法教程）

二叉树简介

在众多树结构中，二叉树是最基础也最常用的一种。它的特点是：每个节点最多有两个子节点，分别称为左子节点和右子节点。

用Java定义二叉树节点

首先，我们需要定义一个表示树节点的类：

public class TreeNode {    int val;    TreeNode left;    TreeNode right;    // 构造函数    public TreeNode(int val) {        this.val = val;        this.left = null;        this.right = null;    }}

二叉树的三种遍历方式

遍历是树算法中最基本的操作。常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。它们的区别在于访问根节点的顺序不同。

• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右
• 后序遍历：左 → 右 → 根

1. 前序遍历（递归实现）

public void preorderTraversal(TreeNode root) {    if (root == null) {        return;    }    System.out.print(root.val + " "); // 访问根节点    preorderTraversal(root.left);     // 遍历左子树    preorderTraversal(root.right);    // 遍历右子树}

2. 中序遍历（递归实现）

public void inorderTraversal(TreeNode root) {    if (root == null) {        return;    }    inorderTraversal(root.left);      // 遍历左子树    System.out.print(root.val + " "); // 访问根节点    inorderTraversal(root.right);     // 遍历右子树}

3. 后序遍历（递归实现）

public void postorderTraversal(TreeNode root) {    if (root == null) {        return;    }    postorderTraversal(root.left);    // 遍历左子树    postorderTraversal(root.right);   // 遍历右子树    System.out.print(root.val + " "); // 访问根节点}

完整示例：构建一棵树并遍历

下面是一个完整的 Java 程序，演示如何构建一棵简单的二叉树并执行三种遍历：

public class BinaryTreeExample {    static class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode(int val) {            this.val = val;        }    }    public static void preorder(TreeNode root) {        if (root == null) return;        System.out.print(root.val + " ");        preorder(root.left);        preorder(root.right);    }    public static void inorder(TreeNode root) {        if (root == null) return;        inorder(root.left);        System.out.print(root.val + " ");        inorder(root.right);    }    public static void postorder(TreeNode root) {        if (root == null) return;        postorder(root.left);        postorder(root.right);        System.out.print(root.val + " ");    }    public static void main(String[] args) {        // 构建如下树：        //       1        //      / \        //     2   3        //    / \        //   4   5        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.print("前序遍历: ");        preorder(root); // 输出: 1 2 4 5 3        System.out.println();        System.out.print("中序遍历: ");        inorder(root);  // 输出: 4 2 5 1 3        System.out.println();        System.out.print("后序遍历: ");        postorder(root); // 输出: 4 5 2 3 1    }}

总结

通过本教程，你已经掌握了Java树结构的基本概念、节点定义以及三种核心遍历方法。这些是学习更高级树算法（如二叉搜索树、AVL树、红黑树等）的基础。

记住，理解二叉树遍历的关键在于递归思维。多动手写代码、画图分析，你会越来越熟练！

希望这篇Java数据结构入门教程对你有所帮助。继续加油，成为算法高手吧！