Java实现二分搜索树的示例代码

下面我将详细讲解“Java实现二分搜索树的示例代码”的完整攻略。

什么是二分搜索树？

首先，我们需要明确什么是二分搜索树(BST)。

二分搜索树是一种二叉树，其中每个节点都有一个键值，且每个节点的键值都大于左子树中任意一个节点的键值，小于右子树中任意一个节点的键值。这种性质使得查找、插入、删除节点的操作都可以在时间复杂度为O(logN)的时间内完成，非常适合用于存储需要快速查询的数据。

思路分析

了解了二分搜索树的概念之后，接下来我们就可以思考如何实现它。

思路大致如下：

• 首先定义二分搜索树节点类BSTNode，包含key值和左右节点引用。
• 再定义二分搜索树类BST，包含根节点引用和查找、插入、删除等操作。

示例代码

下面是示例代码具体实现。

BSTNode类

public class BSTNode {
    // 键值
    public int key;
    // 左节点
    public BSTNode left;
    // 右节点
    public BSTNode right;

    public BSTNode(int key) {
        this.key = key;
    }
}

BST类

public class BST {
    // 根节点
    private BSTNode root;

    // 查找
    public BSTNode search(int key) {
        return search(root, key);
    }

    private BSTNode search(BSTNode node, int key) {
        if (node == null || node.key == key) {
            return node;
        }
        if (key < node.key) {
            return search(node.left, key);
        }
        return search(node.right, key);
    }

    // 插入
    public void insert(int key) {
        root = insert(root, key);
    }

    private BSTNode insert(BSTNode node, int key) {
        if (node == null) {
            return new BSTNode(key);
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        return node;
    }

    // 删除
    public void delete(int key) {
        root = delete(root, key);
    }

    private BSTNode delete(BSTNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                BSTNode temp = node.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                node.key = temp.key;
                node.right = delete(node.right, node.key);
            }
        }
        return node;
    }
}

我们可以在main函数中测试生成二分搜索树并进行相关的操作。

public static void main(String[] args) {
    BST bst = new BST();
    bst.insert(5);
    bst.insert(3);
    bst.insert(8);
    bst.insert(1);
    bst.insert(4);
    bst.insert(6);
    bst.insert(9);

    System.out.println(bst.search(4));

    bst.delete(4);

    System.out.println(bst.search(4));
}

运行结果为：

BSTNode@3fee733d
null

其中，注释已经比较详细，相信你已经可以看懂代码及其实现原理了。如果有任何疑问可以随时提出，我会为你解答。