二叉排序树（二叉查找树）

若它的左子树不空，则左子树上所有节点的值小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值大于它的根节点的值；
它的左右子树也分别是二叉排序树。

初始化：

    private static class BinarySearchNode {
        private int data;
        private BinarySearchNode left;
        private BinarySearchNode right;
        public BinarySearchNode() {
        }

        public BinarySearchNode(int data) {
            this.data = data;
        }

    }

    //根节点
    private BinarySearchNode root;

查询：

    public BinarySearchNode search(int key) {
        BinarySearchNode startNode = root;
        while (startNode != null) {

            if (startNode.data == key) {
                return startNode;
            } else if (startNode.data < key) {
                startNode = startNode.right;
            } else {
                startNode = startNode.left;
            }
        }

        return null;
    }

插入：

      public void insert(int key) {
        BinarySearchNode newNode = new BinarySearchNode(key);

        if(root == null){
            root = newNode;
            return;
        }

        BinarySearchNode current = root;
        while (current !=null) {

            if (current.data < key) {

                if (current.right != null) {
                    current = current.right;
                } else {
                    current.right = newNode;

                    return;
                }

            } else if (current.data > key) {
                if (current.left != null) {
                    current = current.left;
                } else {
                    current.left = newNode;
                    return;
                }

            }
        }

    }

删除：

    public void delete(int val){
        //从根节点遍历查找要删除的结点，以及其双亲结点
       BinarySearchNode deleteNode = root;
       BinarySearchNode parentNode = null;
       while (deleteNode !=null && deleteNode.data != val){
           parentNode = deleteNode;
           if(deleteNode.data > val){
               deleteNode = deleteNode.left;
           }else {
               deleteNode = deleteNode.right;
           }
       }

       if(deleteNode == null){
           System.out.println("没有找到要删除数据结点");
           return;
       }

       //存在左右子节点，则找到右子树的最小节点，与要删除节点交换。再删除这个最小节点。
       if(deleteNode.right != null && deleteNode.left !=null){
           BinarySearchNode minNode = deleteNode.right;
           BinarySearchNode minParentNode = deleteNode;
           while (minNode.left !=null){
               minParentNode = minNode;
               minNode = minNode.left;
           }

           deleteNode.data = minNode.data;
           deleteNode = minNode;
           parentNode = minParentNode;

       }


       //如果要删除的左节点不为空，则孩子节点为其左节点，右节点不为空，孩子节点为其右节点。找个替代的结点
       BinarySearchNode childNode ;
       if(deleteNode.left !=null){
           childNode =deleteNode.left;
       }else if(deleteNode.right !=null){
           childNode = deleteNode.right;
       }else {
           childNode = null;
       }


       //父节点为空，则未删除根节点。将对应孩子结点数据赋值给该结点。
       if(parentNode == null){
           root = childNode;
       }else if(parentNode.left ==deleteNode){
           parentNode.left = childNode;
       }else {
           parentNode.right = childNode;
       }

    }

查找最小节点：

    public BinarySearchNode getMin(){
        if(root == null){
            return null;
        }

        BinarySearchNode leftNode = root;
        while (leftNode.left != null){
            leftNode = leftNode.left;
        }
        return leftNode;
    }

查找最大节点：

    public BinarySearchNode getMax(){
        if(root == null){
            return null;
        }

        BinarySearchNode rightNode = root;
        while (rightNode.right !=null){
            rightNode = rightNode.right;
        }

        return rightNode;


    }