二分搜索树的增删查

二分搜索树首先是一个二叉树，什么是二叉树，二叉树是这个树的节点最多有两个

二分搜索树的根节点大于左节点而小于右节点，而每一个节点所产生的子树也是一个二分搜索树

由此可以推断最小值一定在左子树中，最大值一定在右子树中。

由此可以用递归算法来实现插入和遍历二分搜索树。

插入新数据

 //向二分搜索树中添加新元素e
    public void add(E e) {
        root = add(root, e)
    }

    //向以node为根的二分搜索树中插入元素E，递归算法
    //返回插入新节点之后的二分搜索树的根
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

查询数据

    //查看二叉搜索树中是否包含元素e
    public boolean contains(E e) {
        return contains(root, e);
    }

    //看以node为根的二分搜索树中是否包含元素e，递归算法
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        }else {
            return contains(node.right,e);
        }
    }

删除最大值或者最小值

//删除最小值所在节点，返回最小值
	public E removemin() {
		E rey = mininum();
		removemin(root);
		return rey;
	}
	//删除掉以node为根的二分搜索树中的最小节点
	//返回删除及诶单后新的二分搜索树的根
	private Node removemin(Node node) {
		if(node.left==null) {
			Node rnode = node.right;
			node.right = null;
			size--;
			return rnode;
		}
		node.left = removemin(node.left);
		return node;
	}
	public E removemax() {
		E rey = maxnum();
		removemax(root);
		return rey;
	}
	private Node removemax(Node node) {
		if(node.right==null) {
			Node lnode = node.left;
			node.left = null;
			size--;
			return node;
		}
		node.right = removemax(node.right);
		return node;
	}

删除任意值

//删除元素为e的节点
	public void remove(E e) {
		root = remove(root,e);
	}
	private Node remove(Node node,E e) {
		if(node==null) {
			return null;
		}
		if(e.compareTo(node.e)<0) {
			node.left = remove(node.left,e);
			return node;
		}
		else if(e.compareTo(node.e)>0) {
			node.right = remove(node.right,e);
			return node;
		}
		else {//e==node.e
			if(node.left==null) {//待删除节点左子树为空
				Node rightNode = node.right;
				node.right = null;
				size--;
				return rightNode;
			}
			if(node.right==null) {//待删除节点右子树为空
				Node leftNode = node.left;
				node.left=null;
				size--;
				return leftNode;
			}
			//左右子树都不为null
			//找到比待删除节点大的最小节点，即待删除节点右子树的最小节点，用这个节点顶替待删除节点的位置
			Node successor = mininum(node.right);//右子树中的最小节点
			successor.right = removemin(node.right);
			
			successor.left = node.left;
			
			node.left = node.right = null;
			
			return successor;
			
		}
	}