Java函数实现二叉查找树的代码
一、二叉查找树的定义
二叉查找树（Binary Search Tree）是一种二叉树，它满足以下两个性质：
1. 左子树中所有节点的值均小于根节点的值；
2. 右子树中所有节点的值均大于根节点的值。
二叉查找树的中序遍历是升序排列的。
二、实现二叉查找树的关键操作
1. 插入操作
用递归实现插入操作，每次插入时先判断要插入的值是否比当前节点的值小（则插入到左子树），还是比当前节点的值大（则插入到右子树）。如果要插入的节点为空，则新建一个节点。
2. 查找操作
同样用递归实现查找操作。如果要查找的值比当前节点的值小，则在左子树中查找；如果比当前节点的值大，则在右子树中查找；如果等于当前节点的值，则返回该节点。
3. 删除操作
删除操作比较复杂。情况分为三种：
1. 被删除的节点为叶子节点：直接删除即可；
2. 被删除的节点只有一个子节点：将子节点移动到被删除的节点的位置上即可；
3. 被删除的节点有两个子节点：先找到被删除节点的右子树的最小节点，将该节点的值赋给被删除的节点，再删除该最小节点。
三、Java代码实现
public class BinarySearchTree {
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
private TreeNode root;
public void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
}
return node;
}
public TreeNode search(int val) {
return search(root, val);
}
private TreeNode search(TreeNode node, int val) {
if (node == null || node.val == val) {
return node;
}
if (val < node.val) {
return search(node.left, val);
} else {
return search(node.right, val);
}
}
public void delete(int val) {
root = delete(root, val);
}
private TreeNode delete(TreeNode node, int val) {
if (node == null) {
return null;
}
if (val < node.val) {
node.left = delete(node.left, val);
} else if (val > node.val) {
node.right = delete(node.right, val);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
TreeNode minNode = findMin(node.right);
node.val = minNode.val;
node.right = delete(node.right, node.val);
}
return node;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
以上就是Java函数实现二叉查找树的代码。