二叉搜索树是一种特殊的二叉树
左子树中的值都小于根节点,右子树中的值都大于根节点
故:中序遍历结果就会得到一个有序序列
最大的特点:就是能够高效的进行查找元素
查找过程类似于二分查找:先从根节点出发开始比较,看待查找元素是小于根节点还是大于根节点,进一步决定是去左子树中找,还是右子树
查找的时间复杂度:O(N) (单支树)
解决方案:采取更加平衡的二叉搜索树,AVL树(绝对平衡),红黑树
其实和查找非常相似,需要先找到待插入元素的合适位置
若树为空树,直接插入为根节点即可
对于二叉搜索树来说,插入元素的时候,元素都是被插入到叶子节点上的
也很简单,简单画图理解即可~
需要考虑很多种不同的情况:
直接让父节点的左子树,指向待删除元素的右子树即可
直接让父节点的右子树,指向待删除节点的右子树即可
直接将父节点的左子树,指向待删除结点的左子树即可
直接将父节点的右子树,指向待删除结点的左子树即可
代码实现:
public class BinarySearchTree {
public static class Node{
int key;
Node left;
Node right;
public Node(int key) {
this.key = key;
}
}
// 根节点 root 为null,表示为空树
private Node root = null;
//查找操作
public Node find(int key){
// 查找 key 是否存在
// 若存在,返回对应的Node
// 若不存在,返回null
Node cur = root;
while (cur != null){
if(key < cur.key){
//此时去左子树中找
cur = cur.left;
}
else if(key > cur.key){
// 此时去右子树找
cur = cur.right;
}
else{
// 找到了
return cur;
}
}
// key 不存在
return null;
}
//插入操作
public boolean insert(int key){
// 二叉搜索树中 是不允许存在相同 key 的元素的
// 若新插入的 key 重复,就插入失败,返回 false
// 插入成功 返回 true
// 空树判断
if(root == null){
root = new Node(key);
return true;
}
//先找到合适的位置,再去插入元素
Node cur = root;
// 让 parent 始终指向 cur 的父节点
Node parent = null;
while (cur != null){
if(key < cur.key){
parent = cur;
cur = cur.left;
}
else if(key > cur.key){
parent = cur;
cur = cur.right;
}
else{
// 某个元素和待插入元素值相同
return false;
}
}
// 循环结束,cur 指向 null
// 当前元素就要插到 parent 子树的位置上
if(key < parent.key){
parent.left = new Node(key);
}
else{
parent.right = new Node(key);
}
return true;
}
//删除操作
public boolean remove(int key){
// 先找到 待删除节点的位置,再进行删除
// 找到待删除元素后,再来判断是那种情况
Node cur = root;
Node parent = null;
while (cur != null){
if(key < cur.key){
parent = cur;
cur = cur.left;
}
else if(key > cur.key){
parent = cur;
cur = cur.right;
}
else{
// 找到了 待删除元素,就是 cur 指向的元素
removeNode(parent,cur);
return true;
}
}
return false;
}
private void removeNode(Node parent, Node cur) {
// 1.待删除元素左子树为空
if(cur.left == null){
//1.1 若要删除节点为 root
if(cur == root){
root = cur.right;
}
//1.2 cur 是 parent 的左子树
else if(cur == parent.left){
parent.left = cur.right;
}
//1.3 cur 是 parent 的右子树
else{
parent.right = cur.right;
}
}
// 2.待删除元素右子树为空
else if(cur.right == null){
//2.1 若要删除节点为 root
if(cur == root){
root = cur.left;
}
//2.2 cur 是 parent 的左子树
else if(cur == parent.left){
parent.left = cur.left;
}
//2.3 cur 是 parent 的右子树
else{
parent.right = cur.left;
}
}
// 3.待删除节点有两个子树
else{
// ①找到右子树的最小元素 / 左子树的最大元素(替罪羊)
Node goatParent = cur;
Node scapeGoat = cur.right;
while (scapeGoat.left != null){
goatParent = scapeGoat;
scapeGoat = scapeGoat.left;
}
// 当循环结束时,scapeGoat 指向了右子树中的最小值
// ②将找到的元素,赋值给待删除节点
cur.key = scapeGoat.key;
// ③删除替罪羊节点
// 替罪羊节点一定没有左子树
if(scapeGoat == goatParent.left){
goatParent.left = scapeGoat.right;
}
else{
goatParent.right = scapeGoat.right;
}
}
}
}
插入测试:
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(9);
tree.insert(5);
tree.insert(2);
tree.insert(7);
tree.insert(3);
tree.insert(6);
tree.insert(8);
//为了查看树的结构,可以打印树的先序和中序遍历结果
tree.preOrder(tree.root);
System.out.println();
tree.inOrder(tree.root);
}
// 先序遍历
public void preOrder(Node root){
if(root == null){
return;
}
System.out.print(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(Node root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.key + " ");
inOrder(root.right);
}
输出结果:
根据先 、中序遍历结果,来还原二叉树,得到:
调试代码:
得到的结果和我们图上还原的结果一样
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/m0_47988201/article/details/121077554
内容来源于网络,如有侵权,请联系作者删除!