Search Binary Tree - find nodes, insert nodes, delete nodes

Trees

public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;
}

One ： Looking for nodes

1. requirement ： public TreeNode search(int key) lookup key Whether in

2. Ideas ： Search binary trees —— The values on the left side of the node are all less than The value of the root , The values on the right side of the node are greater than Value of root node You can use this point to judge - The value of the root node is less than key- Look to the right of the root node （ The value of the root node is greater than key- Look to the left of the root node ）

3. Code ：

 public TreeNode search(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;
    }

Two ： Insert node

1. requirement ：public boolean insert(int key) Insert a data into it key

2. Ideas ：

            Look at the picture below ： If you are given a tree to insert nodes , Think about it , You have to plug in the nodes in the original tree ？—— Leaf position —— So you have to find the original tree node .left/.right==null The point of

           First of all - This tree is Empty tree - The empty tree directly makes this data the root second - Find a location to use cur=root,p=null, When cur!=null- Judge its and key Of size ( Big or small p=cur,cur=cur.left / right)( equal Then return to false Can't have the same data )- until cur==null-key And p.val By comparison, it is inserted p Left or right

3. Code ：

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

4. Look at the picture and walk again ：

3、 ... and ： Delete node

1. requirement ： public void remove(int key)  The deletion value is key The node of

2. Ideas ：

                 Whether the node can be found cur—— The left side of the deleted node is empty 、 The right side of the deleted node is empty 、 The left and right sides of the deleted node are not empty

                Deleted nodes cur Left is empty ——cur==root -> root = cur.right 、cur==p.left ->p.left=cur.right 、cur==p.right

                Deleted nodes cur The right side is empty —— It's similar to the one above

                 The left and right sides of the deleted node are not empty —— It's time for you to choose Find the minimum value on the right ,( Find the maximum value on the left )—— Found his value cur Give the node you want to delete —— Judge cur yes p.left / p.right—— And then =cur.right

3. Code ：

    public void remove(int key){
        TreeNode cur = root;
        TreeNode p = null;
        while(cur != null){
            if (cur.val > key){
                p = cur;
                cur = cur.left;
            }else if(cur.val < key){
                p = cur;
                cur = cur.right;
            }else {
                removeNode(cur,p);
                return;
            }
        }
    }
    private void removeNode(TreeNode cur,TreeNode p){
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(cur == p.left){
                p.left = cur.right;
            }else {
                p.right = cur.right;
            }

        }
        else if(cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if(cur == p.right){
                p.right = cur.left;
            }else {
                p.left = cur.left;
            }
        }
        else {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            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 inorderNode(TreeNode root){
        if(root == null) return;
        inorderNode(root.left);
        System.out.print(root.val+" ");
        inorderNode(root.right);
    }

4. Look at the picture and walk again