目录
1.概念
2.图解:
3.元素插入操作
1.思路分析:
2.代码展示:
4.元素查找操作
1.前提根节点不为空
2.代码展示:
5.查找BST中的最大最小值
代码展示:
6.删除BST中的最大最小值
代码展示:
7.删除BST中的任意元素
代码展示:
文章来源地址https://www.toymoban.com/news/detail-408345.html
1.概念
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
文章来源:https://www.toymoban.com/news/detail-408345.html
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;
}
}
}
到了这里,关于【数据结构】二叉搜索树BST的实现(递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!