【搜索】二叉搜索树

/**
 * 搜索二叉树
 * @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 + "]";
        }
    }
}