二叉搜索树的查找和插入Java函数实现

二叉搜索树是一种特殊的二叉树，它的每个节点都存储了一个数值，并且左子树上的所有节点的值都小于它的根节点值，右子树上的所有节点的值都大于它的根节点值。因此，二叉搜索树可以实现快速的查找和插入操作。下面介绍如何在Java中实现二叉搜索树的查找和插入操作。

定义二叉搜索树的Node类

首先，我们需要定义一个Node类来表示二叉搜索树中的一个节点。该类包含一个数据域和两个指向左右子节点的指针，如下所示：

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

查找操作

二叉搜索树的查找操作可以通过递归实现。如果要查找的值等于当前节点的值，则返回当前节点；如果要查找的值小于当前节点的值，则在左子树中继续查找；如果要查找的值大于当前节点的值，则在右子树中继续查找。如果没有找到对应的节点，则返回null。

public Node search(Node root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return search(root.left, val);
    }
    return search(root.right, val);
}

插入操作

二叉搜索树的插入操作同样可以通过递归实现。如果要插入的值小于当前节点的值，则在左子树中继续插入；如果要插入的值大于当前节点的值，则在右子树中继续插入。如果插入的位置为空，则创建一个新节点，并将其插入到该位置。

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

综上所述，二叉搜索树的查找和插入操作可以通过递归实现。在递归过程中，我们需要不断比较要查找或插入的值和当前节点的值，并根据其大小关系选择左子树或右子树继续查找或插入。当遇到空节点时，我们需要创建一个新节点并将其插入到该位置。