什么是二叉排序樹

二叉排序樹：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

1. 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

2. 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

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的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；否則：

3. 若x小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹；否則：

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);
            }
        }
    }

刪除

 /**
     * 刪除二叉查找樹上的某一個(gè)節(jié)點(diǎn)
     * 1. 若是葉子節(jié)點(diǎn)，對(duì)此節(jié)點(diǎn)刪除不影響整體樹的結(jié)構(gòu)，只需修改雙親節(jié)點(diǎn)即可
     * 2. 若是只有左子樹或只有右子樹的節(jié)點(diǎn)
     * 3. 若是左子樹和右子樹都在的節(jié)點(diǎn)
     */
    public boolean deleteBST(T data) {
        Node currentNode = root;//所刪節(jié)點(diǎn)
        Node parentNode = root;//所刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
        boolean isLeft = false; //是否是父節(jié)點(diǎn)的左子樹
        //查找
        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;
        }
        //假設(shè)是葉子節(jié)點(diǎn)
        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) {
            //都不為空的情況,找到前驅(qū)或后繼(該節(jié)點(diǎn)左子樹的最大數(shù)、右子樹的最小樹)
            //1.先找到前驅(qū)或后繼節(jié)點(diǎn) 賦值 刪除
            //2.移動(dòng)位置
            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;
    }