什么是二叉排序树

二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 它的左、右子树也分别为二叉排序树。

public class BinarySearchTree<T extends Comparable> {
    private Node<T> root;

    public Node<T> getRoot() {
        return root;
    }

    public void setRoot(Node<T> root) {
        this.root = root;
    }
//...
}

查找

在排序树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：

2. 若x等于b的根节点的数据域之值，则查找成功；否则：

3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：

4. 查找右子树。

 /**
     * 查找
     * @param root
     * @param data
     * @return
     */
    public Node<T> searchBST(Node root, T data) {
        if (root == null) {
            return root;
        } else {
            if (root.getValue().compareTo(data) == 0) {
                return root;
            } else if (root.getValue().compareTo(data) < 0) {
                return searchBST(root.getLeft(), data);
            } else {
                return searchBST(root.getRight(), data);
            }
        }
    }

删除

 /**
     * 删除二叉查找树上的某一个节点
     * 1. 若是叶子节点，对此节点删除不影响整体树的结构，只需修改双亲节点即可
     * 2. 若是只有左子树或只有右子树的节点
     * 3. 若是左子树和右子树都在的节点
     */
    public boolean deleteBST(T data) {
        Node currentNode = root;//所删节点
        Node parentNode = root;//所删除节点的父节点
        boolean isLeft = false; //是否是父节点的左子树
        //查找
        while (currentNode != null && currentNode.getValue() != data) {
            parentNode = currentNode;
            int cResult = data.compareTo(currentNode.getValue());
            if (cResult > 0) {
                currentNode = currentNode.getRight();
                isLeft = false;
            } else if (cResult < 0) {
                currentNode = currentNode.getLeft();
                isLeft = true;
            }
        }
        if (currentNode == null) {
            System.out.println("delete err: not found this node");
            return false;
        }
        //假设是叶子节点
        if (currentNode.getLeft() == null && currentNode.getRight() == null) {
            if (currentNode == root) {
                root = null;
            } else if(isLeft){
                parentNode.setLeft(null);
            }else{
                parentNode.setRight(null);
            }
            return true;
        }
        if (currentNode.getRight() == null) {
            if (currentNode == root) {
                root = currentNode.getLeft();
            } else if (isLeft) {
                parentNode.setLeft(currentNode.getLeft());
            } else {
                parentNode.setRight(currentNode.getLeft());
            }
        } else if (currentNode.getLeft() == null) {
            if (currentNode == root) {
                root = currentNode.getRight();
            } else if (isLeft) {
                parentNode.setLeft(currentNode.getRight());
            } else {
                parentNode.setRight(currentNode.getRight());
            }
        } else if (currentNode.getLeft() != null && currentNode.getRight() != null) {
            //都不为空的情况,找到前驱或后继(该节点左子树的最大数、右子树的最小树)
            //1.先找到前驱或后继节点 赋值 删除
            //2.移动位置
            Node tmpNode = currentNode.getRight();//后继
            Node tmpParentNode = tmpNode;
            while (tmpNode.getLeft() != null) {
                tmpParentNode = tmpNode;
                tmpNode = tmpNode.getLeft();
            }
            if(tmpNode != currentNode.getRight()){
                tmpParentNode.setLeft(tmpNode.getRight());
            }else{
                currentNode.setRight(tmpNode.getRight());
            }
            currentNode.setValue(tmpParentNode.getValue());
        }
        return true;
    }