高阶-二叉搜索树详解

1.二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
（1）若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
（2）若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
（3）它的左右子树也分别为二叉搜索树

2.二叉搜索树的实现

class BSNode {
    
    public int val;
    public BSNode left;
    public BSNode right;

    public BSNode() {
    
    }

    public BSNode(int val) {
    
        this.val = val;
    }
    public BSNode root = null;

    public boolean insert(int val) {
    
        BSNode node = new BSNode(val);
        if(root == null) {
    
            root = node;
            return true;
        }
        BSNode cur = root;
        BSNode par = null;
        while (cur != null) {
    
            if(cur.val == val) {
    
                return false;
            } else if (cur.val > val){
    
                par = cur;
                cur = cur.left;
            } else {
    
                par = cur;
                cur = cur.right;
            }
        }
        if(par.val > val) {
    
            par.left = node;
        } else {
    
            par.right = node;
        }
        return true;
    }

    public boolean search(int val) {
    
        if(root == null) return false;
        BSNode cur = root;
        while (cur != null) {
    
            if(cur.val == val) {
    
                return true;
            } else if(cur.val > val) {
    
                cur = cur.left;
            } else {
    
                cur = cur.right;
            }
        }
        return false;
    }
    public void remove(int val) {
    
        if(root == null) return;
        BSNode cur = root;
        BSNode pre = null;
        while (cur != null) {
    
            if(cur.val == val) {
    
                //删除操作
                removeNode(val,pre,cur);
            } else if (cur.val > val) {
    
                pre = cur;
                cur = cur.left;
            } else {
    
                pre = cur;
                cur = cur.right;
            }
        }
    }
    public void removeNode(int val, BSNode pre, BSNode cur) {
    
        if(cur.left == null) {
    
            if (root == cur) {
    
                root = cur.right;
            } else if(cur == pre.left){
    
                pre.left = cur.right;
            } else if (cur == pre.right) {
    
                pre.right = cur.right;
            }
        } else if (cur.right == null) {
    
            if(root == cur) {
    
                root = cur.left;
            } else if(cur == pre.left) {
    
                pre.left = cur.left;
            } else if (cur == pre.right) {
    
                pre.right = cur.left;
            }
        } else {
    
            BSNode targetParent = cur;
            BSNode target = cur.right;
            while (target.left != null) {
    
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }
}

public class BST1 {
    
    public static void preOrder(BSNode root) {
    
        if(root != null) {
    
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public static void inOrder(BSNode root) {
    
        if(root != null) {
    
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
    }
    public static void postOrder(BSNode root) {
    
        if(root != null) {
    
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }
    }
    public static void main(String[] args) {
    
        BSNode bsNode = new BSNode();
        bsNode.insert(4);
        bsNode.insert(3);
        bsNode.insert(1);
        bsNode.insert(15);
        preOrder(bsNode.root);
        System.out.println();
        System.out.println(bsNode.search(3));
        System.out.println(bsNode.search(2));
        bsNode.remove(1);
        preOrder(bsNode.root);
    }
}