当前位置：首页 > Java

java 如何树

2026-03-20 16:41:19Java

树的基本概念

在Java中，树是一种非线性的数据结构，由节点（Node）组成，每个节点包含数据及指向子节点的引用。常见的树类型包括二叉树、二叉搜索树（BST）、AVL树、红黑树等。树的实现通常通过递归或迭代方式操作节点。

树的节点定义

树的节点通常包含数据字段和子节点引用。以二叉树为例，节点定义如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

树的遍历方法

树的遍历分为深度优先（DFS）和广度优先（BFS）：

前序遍历（根→左→右）：

void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

中序遍历（左→根→右）：

void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

后序遍历（左→右→根）：

java 如何树

void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

层序遍历（BFS，使用队列）：

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

二叉搜索树（BST）的实现

BST是一种有序树，左子树节点值均小于根节点，右子树节点值均大于根节点。

插入节点：

TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insert(root.left, val);
    else if (val > root.val) root.right = insert(root.right, val);
    return root;
}

查找节点：

java 如何树

boolean search(TreeNode root, int val) {
    if (root == null) return false;
    if (val == root.val) return true;
    return val < root.val ? search(root.left, val) : search(root.right, val);
}

平衡树（AVL树）的旋转操作

AVL树通过旋转保持平衡，分为四种情况：

左旋（RR型失衡）：

TreeNode leftRotate(TreeNode y) {
    TreeNode x = y.right;
    y.right = x.left;
    x.left = y;
    return x;
}

右旋（LL型失衡）：

TreeNode rightRotate(TreeNode x) {
    TreeNode y = x.left;
    x.left = y.right;
    y.right = x;
    return y;
}

树的常用库

Java标准库未直接提供树结构，但可通过以下方式简化操作：

集合框架：TreeSet和TreeMap基于红黑树实现，支持有序操作。
第三方库：如Apache Commons Collections或Google Guava提供树相关工具。

示例：构建并遍历二叉树

public class BinaryTreeExample {
    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);

        System.out.println("前序遍历:");
        preOrder(root); // 输出: 1 2 4 3
    }
}

以上内容涵盖了树的基本实现、遍历、BST操作及平衡树调整，适用于Java中树的常见应用场景。

标签: java