教你如何用Java实现二叉搜索树的插入函数

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：

1. 左子树上所有节点的值均小于它的根节点的值；

2. 右子树上所有节点的值均大于它的根节点的值；

3. 没有任何重复的节点。

因为这些性质，BST可以快速地查找、插入和删除节点。

在Java中实现BST的插入函数，可以定义一个BinarySearchTree类来表示BST。该类包含了一个内部类TreeNode表示BST中的节点，以及插入函数insert()。

首先，定义TreeNode类。它包含三个成员变量，分别是节点的值value、左子节点left和右子节点right。TreeNode类还包含一个构造函数，用来初始化节点的值和左右子节点。

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

接下来，定义BinarySearchTree类。它有一个成员变量root表示BST的根节点。insert()函数用于插入一个值为value的节点到BST中。

class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        root = insertNode(root, value);
    }

    private TreeNode insertNode(TreeNode node, int value) {
        if (node == null) {
            node = new TreeNode(value);
        } else if (value < node.value) {
            node.left = insertNode(node.left, value);
        } else if (value > node.value) {
            node.right = insertNode(node.right, value);
        }

        return node;
    }
}

在insert()函数中，首先判断BST是否为空，如果是，直接创建一个根节点。如果不是，使用递归方式从根节点开始查找插入位置。如果value比当前节点的值小，递归插入到左子树中；如果value比当前节点的值大，递归插入到右子树中。如果value等于当前节点的值，不插入。

最后，在main函数中测试插入函数：

public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree();
    bst.insert(8);
    bst.insert(3);
    bst.insert(10);
    bst.insert(1);
    bst.insert(6);
    bst.insert(14);
    bst.insert(4);
    bst.insert(7);
    bst.insert(13);

    // 打印BST
    printBST(bst.root);
}

private static void printBST(TreeNode node) {
    if (node != null) {
        System.out.print(node.value + " ");
        printBST(node.left);
        printBST(node.right);
    }
}

运行结果：

8 3 1 6 4 7 10 14 13 

可以看到，根据插入的顺序，BST的中序遍历结果是按从小到大的顺序排列的，符合BST的定义。

通过以上的代码，我们成功地实现了二叉搜索树的插入函数。