Java函数实现二叉查找树的增删改查操作
1. 二叉查找树简介
二叉查找树是一种常用的数据结构，它由根节点、左子树和右子树组成，其中左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值。这样的结构使得二叉查找树非常适用于查找、插入、删除等操作。
2. 增加操作
增加操作就是插入一个元素为key的节点到二叉查找树中，可以使用递归或者非递归的方式实现。
递归实现：
public Node insert(Node root, int key){
if(root == null){
root = new Node(key);
return root;
}
if(key < root.key)
root.left = insert(root.left, key);
else if(key > root.key)
root.right = insert(root.right, key);
return root;
}
非递归实现：
public Node insert(Node root, int key){
if(root == null){
root = new Node(key);
return root;
}
Node curr = root;
while(true){
if(key < curr.key){
if(curr.left == null){
curr.left = new Node(key);
return root;
}
else
curr = curr.left;
}
else if(key > curr.key){
if(curr.right == null){
curr.right = new Node(key);
return root;
}
else
curr = curr.right;
}
else
return root;
}
}
3. 删除操作
删除操作就是从二叉查找树中删除节点，对于二叉查找树中的一个节点，它有三种情况：没有子节点、只有一个子节点、有两个子节点。
- 对于没有子节点的节点，直接删除即可。
- 对于只有一个子节点的节点，把该节点的父节点指向子节点即可。
- 对于有两个子节点的节点，把该节点的左子树中最大的节点或者右子树中最小的节点代替删除的节点，再从子树中删除这个节点。
public Node delete(Node root, int key){
if(root == null)
return null;
if(key < root.key)
root.left = delete(root.left, key);
else if(key > root.key)
root.right = delete(root.right, key);
else{
if(root.left == null && root.right == null)
root = null;
else if(root.left == null)
root = root.right;
else if(root.right == null)
root = root.left;
else{
Node temp = findMin(root.right);
root.key = temp.key;
root.right = delete(root.right, temp.key);
}
}
return root;
}
private Node findMin(Node root){
while(root.left != null)
root = root.left;
return root;
}
4. 修改操作
修改操作就是更改二叉查找树中节点的值，它的实现非常简单，先删除要修改节点，再插入新节点即可。
public Node update(Node root, int oldKey, int newKey){
if(root == null)
return null;
root = delete(root, oldKey);
root = insert(root, newKey);
return root;
}
5. 查找操作
查找操作就是查找二叉查找树中值为key的节点，它的查找方式也是递归或非递归的。
递归实现：
public Node search(Node root, int key){
if(root == null || root.key == key)
return root;
if(key < root.key)
return search(root.left, key);
else
return search(root.right, key);
}
非递归实现：
public Node search(Node root, int key){
if(root == null)
return null;
Node curr = root;
while(curr != null){
if(key == curr.key)
return curr;
else if(key < curr.key)
curr = curr.left;
else
curr = curr.right;
}
return null;
}
结语：
二叉查找树是一种简单、快速的数据结构，可以进行插入、删除、修改、查找等多种操作。以上是Java函数实现二叉查找树的增删改查操作的代码，大家可以根据自己的需求进行修改。