当前位置：首页 > Java

java如何实现二叉树

2026-03-04 03:22:20Java

实现二叉树的基本结构

在Java中实现二叉树需要定义一个节点类（TreeNode）和二叉树类（BinaryTree）。节点类包含数据、左子节点和右子节点的引用。

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

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

class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }
}

插入节点

通过递归或迭代的方式插入节点。以下是一个递归实现的示例：

java如何实现二叉树

public void insert(int val) {
    root = insertRec(root, val);
}

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

遍历二叉树

常见的遍历方式包括前序遍历、中序遍历和后序遍历。

// 前序遍历（根-左-右）
public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

// 中序遍历（左-根-右）
public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

// 后序遍历（左-右-根）
public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

查找节点

通过递归或迭代查找特定值的节点。

java如何实现二叉树

public TreeNode search(int val) {
    return searchRec(root, val);
}

private TreeNode searchRec(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return searchRec(root.left, val);
    }
    return searchRec(root.right, val);
}

删除节点

删除节点时需要处理三种情况：节点无子节点、有一个子节点、有两个子节点。

public void delete(int val) {
    root = deleteRec(root, val);
}

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

private int minValue(TreeNode root) {
    int min = root.val;
    while (root.left != null) {
        min = root.left.val;
        root = root.left;
    }
    return min;
}

测试二叉树

创建一个二叉树实例并测试插入、遍历和删除功能。

public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);

    System.out.println("Inorder traversal:");
    tree.inOrder(tree.root);

    System.out.println("\nDelete 20:");
    tree.delete(20);
    tree.inOrder(tree.root);
}