手撕二叉搜索树——模拟实现

前言：

        二叉搜索树的查找效率代表了其插入，删除的操作的性能，这次通过模拟实现二叉搜索树，增加对其底层实现的认识。

值得提到的一点：

        二叉搜索树的插入，和查找功能很易实现，本篇作为学习笔记，重点了解其删除功能的实现。（代码在最后）

删除功能：

                如何找到待删除的结点？可以通过创建一个cur指针，和一个parent指针(用来指向cur的父亲结点)，cur通过二叉搜索树的性质（左结点的值 < 根节点的值 < 右结点的值）遍历二叉搜索树，找到待删除元素后分以下三大种情况:

        1.cur.left == null; 

        满足以上条件继续分为，cur == root、cur != root即cur是否为parent的左节点或右结点；

        2.cur.right == null;

        满足以上条件继续分为，cur == root、cur != root即cur是否为parent的左节点或右结点；

        3.cur.left != null && cur.right != null;(难点)

        此时需要用替代法进行删除，替代法删除有以下两种方法：（任选一种即可，本篇代码实现选用第一种）

• 在cur的右边找到最小值，并且若能找到这个最小值，这个最小值点一定不存在左子树；
• 在cur的左边找到最大值，并且若能找到这个最大值，这个最大值点一定不存在右子树；

        最后通过target(需要被替换的结点)和targetParent(target的父亲结点)两个指针来进行删除操作。

感觉有点懵？来看下方图解：

代码实现：

public class BinarySearchTree {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }
    TreeNode root = null;
    //查找结点
    public TreeNode sreach(int key){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return cur;
            }
        }
        return null;
    }
    //插入结点
    public boolean insert(int key){
        if(root == null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = root;
        while(cur != null){
            parent = cur;
            if(cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return false;
            }
        }
        if(parent.val > key){
            parent.left = new TreeNode(key);
        }else{
            parent.right = new TreeNode(key);
        }
    return true;
    }
    //删除结点
    public void remove(int key){
        TreeNode cur = root;
        TreeNode parent = root;
        while(cur != null){
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }
            else{//找到了,并删除
                removeNode(cur,parent);
                return;
            }
        }
    }
    private void removeNode(TreeNode cur, TreeNode parent){
        //分三大种情况: 1.cur.left == null
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(parent.left == cur){
                parent.left = cur.right;
            }else if(parent.right == cur){
                parent.right = cur.right;
            }
            //第二大种情况:2.cur.right == null
        }else if(cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if(parent.left == cur){
                parent.left = cur.left;
            }else if(parent.right == cur){
                parent.right = cur.left;
            }
        }
        else{
            /**
             * 第三大种情况：cur两边都不为空
             * 可以使用替换法进行删除，有以下两种替换方式（任意一种即可）
             * 1.在cur的右边找最小值，并且若能找到这个最小值，这个最小值点一定不存在左子树
             * 2.在cur的左边找最大值，并且若能找到这个最小值，这个最大值点一定不存在右子树
             * 以下代码通过方法1实现
             * 通过target和targetParent来确定要替换的结点
             */
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            //分两种情况
            if(targetParent.left == target){
                targetParent.left = target.right;
            }else{
                targetParent.right = target.right;
            }
        }
    }
    //中序遍历打印二叉树
    public void Print(TreeNode root){
        if(root == null){
            return;
        }
        Print(root.left);
        System.out.print(root.val);
        Print(root.right);
    }
}