【数据结构】二叉搜索树BST的实现（递归）
目录
1.概念
2.图解：
3.元素插入操作
1.思路分析：
2.代码展示：
4.元素查找操作
1.前提根节点不为空
2.代码展示：
5.查找BST中的最大最小值
代码展示：
6.删除BST中的最大最小值
代码展示：
7.删除BST中的任意元素
代码展示：
1.概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
2.图解：
以下数组为例 ：int [] arr = [5,3,4,1,7,8,6]
3.元素插入操作
1.思路分析：
- 如果树为空树，即根 == null，直接插入
- 如果树不是空树，按照查找逻辑确定插入位置，插入新结点
2.代码展示：
//在二分搜索树中添加元素
public void add(int val){
root = add(root,val);
}
private Node add(Node root, int val){
if(root == null){
Node node = new Node(val);
userSize++;
return node;
}else if(val < root.val){
root.left = add(root.left, val);
return root;
}else{
root.right = add(root.right,val);
return root;
}
}4.元素查找操作
1.前提根节点不为空
- root.val == key 返回true;
- key > root.val root= root.right;继续查找
- key < root.val root= root.left;继续查找
2.代码展示：
//判断某元素是否在二叉搜索树中
public boolean contains(int val){
return contains(root,val);
}
private boolean contains(Node root, int val){
if(root == null){
return false;
}else if (root.val == val){
return true;
}else if(val < root.val){
return contains(root.left,val);
}else {
return contains(root.right,val);
}
}
5.查找BST中的最大最小值
- 最大值一定在最右边，且右子树为空，顺着右子树往下寻找即可
- 最小值一定在最左边，且左子树为空，顺着左子树往下寻找即可
代码展示：
public int min(){
return findMin(root).val;
}
public int max(){
return findMax(root).val;
}
private Node findMin(Node root){
if(root == null){
throw new NoSuchElementException("没有元素哇~~");
}
Node x = root;
while(x.left != null){
x = x.left;
}
return x;
}
private Node findMax(Node root){
if(this.root == null){
throw new NoSuchElementException("没有元素哇~~");
}
Node x = this.root;
while(x.right != null){
x = x.right;
}
return x;
}6.删除BST中的最大最小值
- 删除最大值，找到最大值所在的节点，将其左子树记录下来，将最大值所在节点和其左子树置空，返回记录下来的左子树给其父节点
- 删除最小值，找到最小值所在的节点，将其右子树记录下来，将最小值所在节点和其右子树置空，返回记录下来的右子树给其父节点
代码展示：
//删除最大值
public void removeMax(){
removeMax(root);
}
private Node removeMax(Node root){
if(root == null){
return null;
}
if(root.right == null){
Node left = root.left;
root.right = root = null;
userSize--;
return left;
}
root.right = removeMax(root.right);
return root;
}
//删除最小值
public void removeMin(){
removeMin(root);
}
private Node removeMin(Node root) {
if(root == null){
return null;
}
if(root.left == null){
Node right = root.right;
root.left = root = null;
userSize--;
return right;
}
root.left = removeMin(root.left);
return root;
}7.删除BST中的任意元素
- 先在二叉搜索树中寻找需要被删除的元素，不存在返回null
- 判断被删除的元素是否左右子树有为空的情况，有则按照删除最大最小值的操作来删除当前元素
- 若左右子树都不为空，则需要在BST中寻找一个新节点，将其右边连接删除新节点后的右子树，
- 左边链接左子树，最后将root,root.left.root.right全部置空，返回新节点即可
代码展示：
//在二叉搜索树中删除元素
public void remove(int val){
root = remove(root,val);
}
private Node remove(Node root, int val) {
if(root == null){
return root;
}else if(val < root.val){
root.left = remove(root.left,val);
return root;
}else if(val > root.val){
root.right = remove(root.right,val);
return root;
}else {
//当前节点就是被删除的节点
if(root.right == null){
//删除最小值的操作一样
Node left = root.left;
root.left = root = null;
userSize--;
return left;
}else if(root.left == null){
Node right = root.right;
root.right = root = null;
userSize--;
return right;
}else {
//左右两边都有子树
Node prev = findMin(root.right);
prev.right = removeMin(root.right);
prev.left = root.left;
root.right = root.left = root = null;
return prev;
}
}
}