二叉排序樹又稱為二叉查找樹，具備以下性質(zhì)：
①若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
②若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
③它的左、右子樹也分別為二叉排序樹；

二叉排序樹使用鏈?zhǔn)酱鎯Γ迦牒蛣h除的效率較好，又可以較高效的實(shí)現(xiàn)查找某個元素的功能。

中序遍歷二叉排序樹時能夠得到一個有序序列。

測試二叉排序樹.png

二叉排序樹結(jié)點(diǎn)類

/**
* @author Shaw
* @version 創(chuàng)建時間：2018年12月9日 下午3:33:43 
* 類說明:二叉排序樹結(jié)點(diǎn)類
 */
class BiTNode {
    //數(shù)據(jù)域
    private int data;
    //左右結(jié)點(diǎn)域
    private BiTNode lchild, rchild;
    
    public BiTNode(int data) {
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public BiTNode getLchild() {
        return lchild;
    }
    public void setLchild(BiTNode lchild) {
        this.lchild = lchild;
    }
    public BiTNode getRchild() {
        return rchild;
    }
    public void setRchild(BiTNode rchild) {
        this.rchild = rchild;
    }
    
    @Override
    public String toString() {
        return "BiTNode [data=" + data + ", lchild=" + lchild + ", rchild=" + rchild + "]";
    }   
}

二叉排序樹核心類

二叉排序樹的建立就是不斷執(zhí)行插入操作的過程。

二叉排序樹的刪除分為三種情況討論：
①當(dāng)刪除結(jié)點(diǎn)僅有左子樹時，只需將此結(jié)點(diǎn)的左孩子替換它自己，就相當(dāng)于刪除了該結(jié)點(diǎn)。
②當(dāng)刪除結(jié)點(diǎn)僅有右子樹時，只需將此結(jié)點(diǎn)的右孩子替換它自己即可。
③當(dāng)刪除結(jié)點(diǎn)左右子樹都不為空時，可以在左子樹中找到小于但最接近該值的結(jié)點(diǎn)替換它，即找到中序遍歷中的前驅(qū)；也可以在右子樹中找到大于但最接近該值的結(jié)點(diǎn)替換，即中序遍歷中的后驅(qū)。
本例中采用的是前驅(qū)替換。

/**
 * 
 * @author Shaw
 * @version 創(chuàng)建時間：2018年12月9日 下午3:34:11 
 * 類說明:二叉排序樹類
 */
class BinarySortTree {
    public BiTNode root;

    public BinarySortTree() {
        root = null;
    }

    // 中序遍歷
    public void InOrderTraverse(BiTNode node) {
        if (node == null) {
            return;
        }
        InOrderTraverse(node.getLchild());
        System.out.print(node.getData() + " ");
        InOrderTraverse(node.getRchild());
    }

    // 二叉排序樹查找
    public BiTNode search_BST(int key) {
        BiTNode current = root;
        while (current != null) {
            // 查找成功返回對應(yīng)結(jié)點(diǎn)
            if (key == current.getData()) {
                return current;
            } else if (key < current.getData()) {
                current = current.getLchild();
            } else {
                current = current.getRchild();
            }
        }
        return null;
    }

    // 二叉排序樹插入
    public void insert_BST(int key) {
        // 空樹情況
        if (root == null) {
            root = new BiTNode(key);
            return;
        }
        // 結(jié)點(diǎn)已在樹中存在時
        if (search_BST(key) != null) {
            return;
        }
        BiTNode node = new BiTNode(key);
        BiTNode current = root;
        BiTNode parent = null;
        // 循環(huán)獲取待插入結(jié)點(diǎn)的父結(jié)點(diǎn)位置
        while (current != null) {
            parent = current;
            if (key < current.getData()) {
                current = current.getLchild();
            } else if (key > current.getData()) {
                current = current.getRchild();
            } else {
                break;
            }
        }
        // 判斷插入的是左結(jié)點(diǎn)還是右結(jié)點(diǎn)
        if (key < parent.getData()) {
            parent.setLchild(node);
        } else {
            parent.setRchild(node);
        }
    }

    // 二叉排序樹刪除
    public boolean delete_BST(int key) {
        // current結(jié)點(diǎn)指向待刪除的結(jié)點(diǎn)
        BiTNode current = root;
        // parent結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的父節(jié)點(diǎn)
        BiTNode parent = null;
        // 通過循環(huán)查找確定current和parent結(jié)點(diǎn)
        while (current != null) {
            // 待刪除的結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，查找左子樹
            if (key < current.getData()) {
                parent = current;
                current = current.getLchild();
            }
            // 待刪除的結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，查找右子樹
            else if (key > current.getData()) {
                parent = current;
                current = current.getRchild();
            }
            // 查找到結(jié)點(diǎn)后退出
            else {
                break;
            }
        }
        // 空樹的情況
        if (current == null) {
            return false;
        }
        // 右子樹為空的情況
        // 待刪除結(jié)點(diǎn)的左結(jié)點(diǎn)"繼承"該結(jié)點(diǎn)的位置
        if (current.getRchild() == null) {
            // 不是空樹的情況
            if (parent != null) {
                // 待刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左結(jié)點(diǎn)
                if (parent.getLchild() == current) {
                    // 將待刪除結(jié)點(diǎn)的左結(jié)點(diǎn)設(shè)置為父結(jié)點(diǎn)的左結(jié)點(diǎn)
                    parent.setLchild(current.getLchild());
                } else {
                    // 待刪除的結(jié)點(diǎn)是父結(jié)點(diǎn)的右結(jié)點(diǎn)時將該結(jié)點(diǎn)的左結(jié)點(diǎn)設(shè)置為父結(jié)點(diǎn)的右結(jié)點(diǎn)
                    parent.setRchild(current.getLchild());
                }
            } else {
                // 空樹時將左結(jié)點(diǎn)賦值給根結(jié)點(diǎn)
                root = current.getLchild();
            }
        }
        // 左子樹為空的情況
        // 待刪除結(jié)點(diǎn)的右結(jié)點(diǎn)"繼承"該結(jié)點(diǎn)的位置
        else if (current.getLchild() == null) {
            if (parent != null) {
                if (parent.getLchild() == current) {
                    parent.setLchild(current.getLchild());
                } else {
                    parent.setRchild(current.getRchild());
                }
            } else {
                root = current.getRchild();
            }
        }
        // 左右子樹均不為空的情況
        // 在二叉排序樹中序中選擇該結(jié)點(diǎn)的前驅(qū)或者后繼替換該結(jié)點(diǎn)，
        // 也就是選擇比該結(jié)點(diǎn)小或者比它大的最接近的兩個數(shù)中的一個，本例選擇的是比該結(jié)點(diǎn)小的結(jié)點(diǎn)
        else {
            // 用于替換的結(jié)點(diǎn)
            BiTNode replaceNode = current.getLchild();
            // 替換結(jié)點(diǎn)的父節(jié)點(diǎn),初始化為待刪除的結(jié)點(diǎn)
            BiTNode replaceParentNode = current;
            // 用于替換的結(jié)點(diǎn)存在右子結(jié)點(diǎn)時，因?yàn)橛医Y(jié)點(diǎn)大于根結(jié)點(diǎn)的值，所以右子結(jié)點(diǎn)更接近被刪除的結(jié)點(diǎn)
            while (replaceNode.getRchild() != null) {
                replaceParentNode = replaceNode;
                replaceNode = replaceNode.getRchild();
            }
            // 替換結(jié)點(diǎn)不存在右子結(jié)點(diǎn)時
            // 相等時由于使用的是前驅(qū)值代替，所以需要補(bǔ)充的是左子結(jié)點(diǎn)的值
            if (replaceParentNode == current) {
                replaceParentNode.setLchild(replaceNode.getLchild());
            }
            // replaceParentNode與current不相等時
            // replaceNode肯定是大于replaceParentNode的值的,所以需要補(bǔ)充的是右子結(jié)點(diǎn)的值
            else {
                replaceParentNode.setRchild(replaceNode.getLchild());
            }
            // 替換對應(yīng)的值
            current.setData(replaceNode.getData());
        }
        return true;
    }
}

測試程序：

public class BinarySortTreeMain {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 36, 39, 42, 62 };
        BinarySortTree binarySortTree = new BinarySortTree();
        System.out.println("原始序列：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
            binarySortTree.insert_BST(a[i]);
        }
        System.out.println("\n二叉排序后的序列：");
        binarySortTree.InOrderTraverse(binarySortTree.root);
        System.out.print("\n查找37：");
        BiTNode node = binarySortTree.search_BST(37);
        if (node != null) {
            System.out.println(true);
        } else {
            System.out.println(false);
        }
        System.out.print("查找22：");
        node = binarySortTree.search_BST(22);
        if (node != null) {
            System.out.println(true);
        } else {
            System.out.println(false);
        }
        System.out.print("刪除47：");
        System.out.println(binarySortTree.delete_BST(47));
        System.out.println("刪除47后的序列：");
        binarySortTree.InOrderTraverse(binarySortTree.root);
        System.out.print("\n刪除22：");
        System.out.println(binarySortTree.delete_BST(22));
    }
}

測試結(jié)果：

二叉排序樹測試結(jié)果圖.png

總結(jié)

二叉排序樹以鏈接方式存儲，保持了鏈接存儲結(jié)構(gòu)在執(zhí)行插入或刪除操作時不用移動元素的優(yōu)點(diǎn)，插入刪除的時間性能較好。對于二叉排序樹的查找，比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹的層數(shù)。最少為1次，最多也不會超過樹的深度。

缺點(diǎn)：當(dāng)本例中的數(shù)組是{35,36,37,39,42,47,51,58,73,88,93,99}時，即數(shù)組元素從小到大有序時，此時的二叉排序樹如圖所示是一棵右斜樹。當(dāng)同樣查找99結(jié)點(diǎn)時，測試?yán)有枰?次比較，本例卻需要12次比較，二者差異很大。也就是說，二叉排序樹的查找性能主要取決于二叉排序樹的形狀，但本例中的二叉排序樹的形狀是由給定數(shù)組來構(gòu)造的，即形狀是不確定的。為此，我們需要構(gòu)造平衡二叉樹來解決這個問題。

右斜樹.png