【搜索】二叉搜索树

概念：二叉搜索树可以是空树，也可以是满足一个节点的左子节点逻辑上小于该节点且右子节点逻辑上大于等于该节点的二叉树，同时其左右子树也满足这个条件。

查询原理：从根节点开始查询，如果节点为null则查询失败，如果目标值小于节点值，则查询左子树，如果目标值大于节点值，则查询右子树，如果目标值等于节点值，则查询成功。

添加原理：从根节点开始查询，如果节点为null，则把新节点添加到该处，如果目标值小于节点值，则查询左子树，如果目标值大于节点值，则查询右子树。

删除原理：待删除节点分三中情况

　　　　　　1）没有子节点：只需将待删除节点的父节点指向待删除节点的引用赋值为null

　　　　　　2）只有一个子节点：只需将待删除节点的父节点指向待删除节点的引用赋值为待删除节点的子节点的引用

　　　　　　3）有两个节点：需要将待删除节点替换为待删除节点中序遍历的后继节点

 

/**
 * 搜索二叉树
 * @author qqx
 *
 * @param <t>
 */
public class binarysearchtree<t> {
    //根节点
    private treenode root;

    /**
     * 查询一个值是否存在
     * @param value
     * 待查询的值
     * @return
     */
    public boolean exist(t value) {
        treenode currentnode = root;
        if (currentnode == null)
            return false;
        else {
            while (((comparable<t>) currentnode.value).compareto(value) != 0) {
                if (((comparable<t>) currentnode.value).compareto(value) > 0)
                    currentnode = currentnode.leftnode;
                else
                    currentnode = currentnode.rightnode;
                if (currentnode == null)
                    return false;
            }
        }
        return true;
    }

    /**
     * 添加一个值到搜索二叉树
     * @param value
     * @return
     */
    public binarysearchtree<t> add(t value) {
        treenode currentnode = root;
        treenode newnode = new treenode(value);
        if (currentnode == null)
            root = newnode;
        else {
            while (true) {
                if (((comparable<t>) currentnode.value).compareto(value) > 0) {
                    if (currentnode.leftnode != null)
                        currentnode = currentnode.leftnode;
                    else {
                        currentnode.leftnode = newnode;
                        break;
                    }
                } else {
                    if (currentnode.rightnode != null)
                        currentnode = currentnode.rightnode;
                    else {
                        currentnode.rightnode = newnode;
                        break;
                    }
                }
            }
        }
        return this;
    }

    /**
     * 删除搜索二叉树中一个值
     * @param value
     * @return
     * @throws exception
     */
    public binarysearchtree<t> delete(t value) throws exception {
        //待删除的节点
        treenode currentnode = root;
        //待删除节点的父节点
        treenode parentnode = root;
        //待删除节点是否为待删除节点的父节点的左节点
        boolean isleftnode = false;

        if (root == null)
            throw (new exception("空树删除异常"));
        //计算待删除节点的父节点，待删除节点是否为待删除节点的父节点的左节点
        while (((comparable<t>) currentnode.value).compareto(value) != 0) {
            parentnode=currentnode;
            if (((comparable<t>) currentnode.value).compareto(value) > 0) {
                currentnode = currentnode.leftnode;
                isleftnode=true;
            }
            else {
                currentnode = currentnode.rightnode;
                isleftnode=false;
            }
            if (currentnode == null)
                throw (new exception("删除节点不存在异常"));
        }
        //待删除节点没有子节点
        if((currentnode.leftnode==null)&&(currentnode.rightnode==null)) {
            if(currentnode==parentnode)
                root=null;
            else if(isleftnode)
                parentnode.leftnode=null;
            else
                parentnode.rightnode=null;
        }
        //待删除节点只有一个子节点
        else if((currentnode.leftnode==null)||(currentnode.rightnode==null)) {
            //待删除节点是根节点
            if(currentnode==parentnode) {
                if(currentnode.leftnode==null)
                    root=currentnode.rightnode;
                else
                    root=currentnode.leftnode;
            }
            else if(isleftnode) {
                if(currentnode.leftnode==null)
                    parentnode.leftnode=currentnode.rightnode;
                else
                    parentnode.leftnode=currentnode.leftnode;
            }
            else {
                if(currentnode.leftnode==null)
                    parentnode.rightnode=currentnode.rightnode;
                else
                    parentnode.rightnode=currentnode.leftnode;
            }
        }
        //待删除节点有两个子节点
        else {
            //待删除节点在中序遍历中的后继节点
            treenode sequencenode=currentnode.rightnode;
            //待删除节点在中序遍历中的后继节点的父节点
            treenode sequenceparentnode=currentnode;
            //计算待删除节点在中序遍历中的后继节点，待删除节点在中序遍历中的后继节点的父节点
            while(sequencenode.leftnode!=null) {
                sequenceparentnode=sequencenode;
                sequencenode=sequencenode.leftnode;
            }
            //待删除节点在中序遍历中的后继节点不是待删除节点的右子节点
            if(sequenceparentnode!=currentnode) {
                sequenceparentnode.leftnode=sequencenode.rightnode;
                sequencenode.rightnode=currentnode.rightnode;
            }
            if(currentnode==root) {
                root=sequencenode;
                root.leftnode=currentnode.leftnode;
            }
            else if(isleftnode) {
                parentnode.leftnode=sequencenode;
                sequencenode.leftnode=currentnode.leftnode;
            }
            else {
                parentnode.rightnode=sequencenode;
                sequencenode.leftnode=currentnode.leftnode;
            }
        }
        return this;
    }
    
    @override
    public string tostring() {
        stringbuilder stringbuilder=new stringbuilder();
        inordertraversal(stringbuilder,root);
        return stringbuilder.tostring();
    }

    /**
     * 二叉树的中序遍历
     */
    private void inordertraversal(stringbuilder stringbuilder,treenode node) {
        if(node!=null) {
            inordertraversal(stringbuilder,node.leftnode);
            stringbuilder.append(node.value);
            stringbuilder.append("    ");
            inordertraversal(stringbuilder,node.rightnode);
        }
    }

    private class treenode {
        private t value;
        private treenode leftnode;
        private treenode rightnode;

        public treenode() {
            super();
        }

        public treenode(t value) {
            this.value = value;
        }

        public treenode(t value, treenode leftnode, treenode rightnode) {
            super();
            this.value = value;
            this.leftnode = leftnode;
            this.rightnode = rightnode;
        }

        @override
        public string tostring() {
            return "treenode [value=" + value + ", leftnode=" + leftnode.value + ", rightnode=" + rightnode.value + "]";
        }
    }
}