二叉搜索树详解

大家好呀，今天我们一起学习二叉搜索树，二叉搜索树是一种基本的二叉树结构，在原有二叉树的基础上引入了新的特性，它要求每个节点的左子树只包含小于父节点的值，右子树只包含大于父节点的值。这种结构使得二叉搜索树在查找、插入和删除操作上具有较高的效率，也为我们后面学习红黑树，TreeMap打下了铺垫，作为一个过渡，二叉搜索树的学习是很有必要的。

一，二叉搜索树的性质

在树的基础上，二叉搜索树引入了下面几种性质：

1，若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2，若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3，二叉树里面的元素不能重复

这个性质也十分容易理解，简单来说，一颗二叉搜索树大概长下面这个样子

可以看到，二叉搜索树所有节点的左子树所有节点的值都是小于这个这个节点，而且，每个节点的左子树和右子树也是一个二叉搜索树

二，二叉搜索树的模拟实现

1，前置操作：主要是定义好每个树节点

class searchTree {
    class node {
        int val;
        node left;
        node right;
        node(int val) {
            this.val = val;
        }
    }
}

我们还需要一个指针指向头节点

 node root = null;

2，二叉搜索树的插入

二叉树的插入操作相对简单，每次在我们拿到一个元素时可以把他与二叉搜索树的节点作比较，如果这个值大于当前节点的值，那么他应该往此节点的右子树上，否则则在左子树上，注意二叉搜索树里的节点的值不能相等。

代码实现如下：

public void Insert(int val) {
        node newNode = new node(val);
        if (root == null) {
            root = newNode;
        }
        node cur = root;
        node Parent = null;
        while (cur != null) {
            if (cur.val > val) {
                Parent = cur;
                cur = cur.left;
            } else if (cur.val < val) {
                Parent = cur;
                cur = cur.right;
            } else {
                return;
            }
        }
        if (Parent.val > val) {
            Parent.left = newNode;
        } else {
            Parent.right = newNode;
        }
    }

3，二叉搜索树的删除操作（难点)

 二叉搜索树的删除操作较难，主要是情况太多难以考虑完全，但是通过画图，可以帮助我们很好理解每一个步骤

我们设待删除结点为 cur, 待删除结点的双亲结点为 paren，注意删除操作是一定会涉及到父母节点的操作，因此需要一个指针记录当前节点的父母节点

1. cur.left == null
1. cur 是 root，则 root = cur.right
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

2. cur.right == null
1. cur 是 root，则 root = cur.left
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

这种情况和上面类似，无非删除时，parent指向cur节点不为空的那边

3. cur.left != null && cur.right != null
这种情况需要使用替换法进行删除，主要方法就是找到它左子树的最大值或者右子树的最小值与当前节点替换，然后删除替换后的节点

代码实现如下：

public boolean Remove(int val) {
        //找到值为Val的节点
        node parent = null;
        node cur = root;
        while (cur != null) {
            if(cur.val==val){
                break;
            }else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else{
                parent = cur;
                cur = cur.right;
            }
        }
        if (cur == null) {
            return false;
        }
        //cur.left == null
        if (cur.left == null) {
            if (cur == root) {
                root = root.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } 
        //cur.right == null
        else if (cur.right == null) {
            if (cur == root) {
               root=root.left;
            } else if (parent.left == cur) {
                parent.left=cur.left;
            } else {
                parent.right=cur.left;
            }
        }
        else
            //cur.right != null&&cur.left!=null
            //找到右子树的最小值或者左子树的最大值来进行替换操作,这里找右子树的最大值
        {
            node parent1=null;
            node tmp=cur.right;
            while(tmp!=null){
                parent1=tmp;
                tmp=tmp.left;
            }
            cur.val=tmp.val;
            parent1.left=tmp.right;
        }
      return true;
    }

好啦，本期博客就到这里，谢谢大家。