快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實(shí)現(xiàn)

更新時(shí)間：2022年01月22日 14:07:59 作者：劉Java

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。本文詳細(xì)介紹了二叉排序樹的原理，并且提供了Java代碼的完全實(shí)現(xiàn)。需要的可以參考一下

1 二叉排序樹的概述

本文沒有介紹一些基礎(chǔ)知識(shí)。對(duì)于常見查找算法，比如順序查找、二分查找、插入查找、斐波那契查找還不清楚的，可以看這篇文章：常見查找算法詳解以及Java代碼的實(shí)現(xiàn)。

假設(shè)查找的數(shù)據(jù)集是普通的順序存儲(chǔ)，那么插入操作就是將記錄放在表的末端，給表記錄數(shù)加一即可，刪除操作可以是刪除后，后面的記錄向前移，也可以是要?jiǎng)h除的元素與最后一個(gè)元素互換，表記錄數(shù)減一，反正整個(gè)數(shù)據(jù)集也沒有什么順序，這樣的效率也不錯(cuò)。應(yīng)該說，插入和刪除對(duì)于順序存儲(chǔ)結(jié)構(gòu)來說，效率是可以接受的，但這樣的表由于無序造成查找的效率很低。

如果查找的數(shù)據(jù)集是有序線性表，并且是順序存儲(chǔ)的，查找可以用折半、插值、斐波那契等查找算法來實(shí)現(xiàn)，可惜，因?yàn)橛行?，在插入和刪除操作上，為了維持順序，需要移動(dòng)大量元素，就需要耗費(fèi)大量的時(shí)間。

有沒有一種即可以使得插入和刪除效率不錯(cuò)，又可以比較高效率地實(shí)現(xiàn)查找的算法呢？這就是二叉排序樹。

二叉排序樹（Binary Sort Tree），又稱為二叉查找樹/二叉搜索樹（binary search tree）。它是具有下列性質(zhì)的二叉樹：

若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；
若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
它的左、右子樹也分別為二叉排序樹；
二叉排序樹也可以是一個(gè)空樹。

構(gòu)造一棵二叉排序樹的目的，其主要目的并不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度，用以提升數(shù)據(jù)結(jié)構(gòu)的綜合能力。不管怎么說，在一個(gè)有序數(shù)據(jù)集上的查找，速度總是要快于無序的數(shù)據(jù)集的，而二叉排序樹這種非線性的結(jié)構(gòu)，也有利于插入和刪除的實(shí)現(xiàn)。

2 二叉排序樹的構(gòu)建

2.1 類架構(gòu)

首先，最簡單的節(jié)點(diǎn)對(duì)象還是需要一個(gè)數(shù)據(jù)域和兩個(gè)引用域。

另外還需要一個(gè)比較器的引用，因?yàn)樾枰獙?duì)元素進(jìn)行排序，自然需要比較元素的大小，如果外部傳遞了比較器，那么就使用用戶指定的比較器進(jìn)行比較，否則，數(shù)據(jù)類型E必須是Comparable接口的子類，否則因?yàn)椴荒鼙容^而報(bào)錯(cuò)。

另外，還需要提供中序遍歷的方法，該遍歷方法對(duì)于二叉排序樹的結(jié)果將會(huì)順序展示。

public class BinarySearchTree<E> {
    /**
     * 外部保存根節(jié)點(diǎn)的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 自定義比較器
     */
    private Comparator<? super E> cmp;


    /**
     * 樹節(jié)點(diǎn)的數(shù)量
     */
    private int size;

    /**
     * 內(nèi)部節(jié)點(diǎn)對(duì)象
     *
     * @param <E> 數(shù)據(jù)類型
     */
    public static class BinaryTreeNode<E> {

        //數(shù)據(jù)域
        E data;
        //左子節(jié)點(diǎn)
        BinaryTreeNode<E> left;
        //右子節(jié)點(diǎn)
        BinaryTreeNode<E> right;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }

    }

    /**
     * 指定比較器
     *
     * @param cmp 比較器
     */
    public BinarySearchTree(Comparator<? super E> cmp) {
        this.cmp = cmp;
    }

    /**
     * 空構(gòu)造器
     */
    public BinarySearchTree() {
    }

    /**
     * 是否是空樹
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回節(jié)點(diǎn)數(shù)
     *
     * @return 節(jié)點(diǎn)數(shù)
     */
    public int size() {
        return size;
    }


    /**
     * 對(duì)元素進(jìn)行比較大小的方法,如果傳遞了自定義比較器,則使用自定義比較器,否則則需要數(shù)據(jù)類型實(shí)現(xiàn)Comparable接口
     *
     * @param e1 被比較的第一個(gè)對(duì)象
     * @param e2 被比較的第二個(gè)對(duì)象
     * @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
     */
    private int compare(E e1, E e2) {
        if (cmp != null) {
            return cmp.compare(e1, e2);
        } else {
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }


    /**
     * 保存遍歷出來的節(jié)點(diǎn)數(shù)據(jù)
     */
    List<BinaryTreeNode<E>> str = new ArrayList<>();

    /**
     * 中序遍歷,提供給外部使用的api
     *
     * @return 遍歷的數(shù)據(jù)
     */
    public String toInorderTraversalString() {

        //如果是空樹,直接返回空
        if (isEmpty()) {
            return null;
        }
        //從根節(jié)點(diǎn)開始遞歸
        inorderTraversal(root);
        //獲取遍歷結(jié)果
        String s = str.toString();
        str.clear();
        return s;
    }

    /**
     * 中序遍歷 內(nèi)部使用的遞歸遍歷方法,借用了棧的結(jié)構(gòu)
     *
     * @param root 節(jié)點(diǎn),從根節(jié)點(diǎn)開始
     */
    private void inorderTraversal(BinaryTreeNode<E> root) {

        BinaryTreeNode<E> left = getLeft(root);
        if (left != null) {
            //如果左子節(jié)點(diǎn)不為null,則繼續(xù)遞歸遍歷該左子節(jié)點(diǎn)
            inorderTraversal(left);
        }
        //添加數(shù)據(jù)節(jié)點(diǎn)
        str.add(root);
        //獲取節(jié)點(diǎn)的右子節(jié)點(diǎn)
        BinaryTreeNode<E> right = getRight(root);
        if (right != null) {
            //如果右子節(jié)點(diǎn)不為null,則繼續(xù)遞歸遍歷該右子節(jié)點(diǎn)
            inorderTraversal(right);
        }
    }

    /**
     * 獲取左子節(jié)點(diǎn)
     *
     * @param parent 父節(jié)點(diǎn)引用
     * @return 左子節(jié)點(diǎn)或者null--表示沒有左子節(jié)點(diǎn)
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 獲取右子節(jié)點(diǎn)
     *
     * @param parent 父節(jié)點(diǎn)引用
     * @return 右子節(jié)點(diǎn)或者null--表示沒有右子節(jié)點(diǎn)
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }

    /**
     * 獲取根節(jié)點(diǎn)
     *
     * @return 根節(jié)點(diǎn) ;或者null--表示空樹
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

}

2.2 查找的方法

查找的方法很簡單：

若根節(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功，返回true；
否則，若小于根節(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹；
若大于根節(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹；
最終查找到葉子節(jié)點(diǎn)還是沒有數(shù)據(jù)，那么查找失敗，則返回false。

/**
 * 查找,開放給外部使用的api
 */
public boolean contains(E e) {
    return contains(e, root);
}

/**
 * 查找,內(nèi)部調(diào)用的方法,從根節(jié)點(diǎn)開始查找
 *
 * @param e    要查找的元素
 * @param root 節(jié)點(diǎn)
 * @return false 不存在 true 存在
 */
private boolean contains(E e, BinaryTreeNode<E> root) {
    /*null校驗(yàn)*/
    if (root == null) {
        return false;
    }
    /*調(diào)用比較的方法*/
    int i = compare(e, root.data);
    /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
    if (i > 0) {
        return contains(e, root.right);
        /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
    } else if (i < 0) {
        return contains(e, root.left);
    } else {
        /*如果等于0，則說明e=root.date 即查詢成功*/
        return true;
    }
}

2.3 插入的方法

有了二叉排序樹的查找函數(shù)，那么所謂的二叉排序樹的插入，其實(shí)也就是將關(guān)鍵字放到樹中的合適位置而已，插入操作就好像在調(diào)用查找的操作，如果找到了那么什么都不做，返回false，如果沒找到，則將要插入的元素插入到遍歷的路徑的最后一點(diǎn)上：

若二叉樹為空。則單獨(dú)生成根節(jié)點(diǎn)，返回true。
執(zhí)行查找算法，找出被插節(jié)點(diǎn)的父親節(jié)點(diǎn)。
判斷被插節(jié)點(diǎn)是其父親節(jié)點(diǎn)的左、右兒子。將被插節(jié)點(diǎn)作為葉子節(jié)點(diǎn)插入，返回true。如果原節(jié)點(diǎn)存在那么什么都不做，返回false。注意：新插入的節(jié)點(diǎn)總是葉子節(jié)點(diǎn)。

/**
 * 插入,開放給外部使用的api
 *
 * @param e 要插入的元素
 */
public void insert(E e) {
    //返回root,但此時(shí)新的節(jié)點(diǎn)可能已經(jīng)被插入進(jìn)去了
    root = insert(e, root);
}

/**
 * 插入,開放給外部使用的api
 *
 * @param es 要插入的元素的數(shù)組,注意,數(shù)組元素的順序存儲(chǔ)的位置將會(huì)影響二叉排序樹的生成
 */
public void insert(E[] es) {
    //返回root,但此時(shí)新的節(jié)點(diǎn)可能已經(jīng)被插入進(jìn)去了
    for (E e : es) {
        root = insert(e, root);
    }

}

/**
 * 插入,內(nèi)部調(diào)用的方法,先從根節(jié)點(diǎn)開始遞歸查找要插入的位置,然后插入
 *
 * @param e    要插入的數(shù)據(jù)
 * @param root 節(jié)點(diǎn)
 * @return 原節(jié)點(diǎn)或者新插入的節(jié)點(diǎn)
 */
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
    /*沒有查找到,那么直接構(gòu)建新的節(jié)點(diǎn)返回,將會(huì)在上一層方法中被賦值給其父節(jié)點(diǎn)的某個(gè)引用,這個(gè)插入的位置肯定是該遍歷路徑上的最后一點(diǎn)
     * 即插入的元素節(jié)點(diǎn)肯定是屬于葉子節(jié)點(diǎn)*/
    if (root == null) {
        size++;
        return new BinaryTreeNode<>(e);
    }
    /*調(diào)用比較的方法*/
    int i = compare(e, root.data);
    /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
    if (i > 0) {
        //重新賦值
        root.right = insert(e, root.right);
        /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
    } else if (i < 0) {
        //重新賦值
        root.left = insert(e, root.left);
    } else {
        /*如果等于0，則說明e=root.date 即存在節(jié)點(diǎn) 什么都不做*/
    }
    //沒查詢到最底層,則返回該節(jié)點(diǎn)
    return root;
}

2.3.1 測(cè)試

現(xiàn)在我們想要構(gòu)建如下一顆排序二叉樹：

首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16、73，然后是第三層的節(jié)點(diǎn)1、24、59、88，然后是第四層的節(jié)點(diǎn)20、35、62、77。每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的大順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出，但是樹的結(jié)構(gòu)不能保證。

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void insert() {
        //首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16,73，然后是第三層的節(jié)點(diǎn)1,24,59,88，然后是第四層的節(jié)點(diǎn)20,35,62,77。
        // 每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出,但是樹的結(jié)構(gòu)不能保證。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍歷輸出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找某個(gè)數(shù)據(jù)是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));
    }
}

在System.out處打上斷點(diǎn)，Debug，可以看到樹結(jié)構(gòu)和我們預(yù)想的一致，如果改變層間的大順序，那么使用Debug會(huì)發(fā)現(xiàn)樹結(jié)構(gòu)不如預(yù)期。

2.4 查找最大值和最小值

很簡單，最左邊的節(jié)點(diǎn)一定是最小的，最右邊的節(jié)點(diǎn)一定是最大的。因此查找最小的節(jié)點(diǎn)只需要向左遞歸查找，查找最大的節(jié)點(diǎn)只需要向右遞歸查找。

/**
 * 查找最小的節(jié)點(diǎn)
 *
 * @param root 根節(jié)點(diǎn)
 * @return 最小的節(jié)點(diǎn)
 */
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果該節(jié)點(diǎn)沒有左右子節(jié)點(diǎn)，那么該節(jié)點(diǎn)就是最小的節(jié)點(diǎn)，返回*/
    } else if (root.left == null) {
        return root;
    }
    /*如果該節(jié)點(diǎn)存在左子節(jié)點(diǎn)，那么繼續(xù)向左遞歸查找*/
    return findMin(root.left);
}

/**
 * 查找最大的節(jié)點(diǎn)
 *
 * @param root 根節(jié)點(diǎn)
 * @return 最大的節(jié)點(diǎn)
 */
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果該節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，那么該節(jié)點(diǎn)就是最大的節(jié)點(diǎn)，返回*/
    } else if (root.right == null) {
        return root;
    }
    /*如果該節(jié)點(diǎn)存在右子節(jié)點(diǎn)，那么繼續(xù)向右遞歸查找*/
    return findMax(root.right);
}

2.5 刪除的方法

對(duì)于二叉排序樹的刪除，就不是那么容易，我們不能因?yàn)閯h除了節(jié)點(diǎn)，而讓這棵樹變得不滿足二叉排序樹的特性，所以刪除需要考慮多種情況。一共有三種情況需要考慮：

如果查找到的將要被刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，那么很簡單，直接刪除父節(jié)點(diǎn)對(duì)于該節(jié)點(diǎn)的引用即可，如下圖的紅色節(jié)點(diǎn)：

例如，刪除20之后：

如果查找到的將要被刪除的節(jié)點(diǎn)具有一個(gè)子節(jié)點(diǎn)，那么也很簡單，直接繞過該節(jié)點(diǎn)將原本父節(jié)點(diǎn)對(duì)于該節(jié)點(diǎn)的引用指向該節(jié)點(diǎn)的子節(jié)點(diǎn)即可，如下圖的紅色節(jié)點(diǎn)：

例如，刪除59之后：

如果查找到的將要被刪除的節(jié)點(diǎn)具有兩個(gè)子節(jié)點(diǎn)，那么就比較麻煩了，如下圖的紅色節(jié)點(diǎn)：

比如我們需要?jiǎng)h除73，那么我們就必須要找出一個(gè)已存在的能夠替代73的節(jié)點(diǎn)，然后刪除該節(jié)點(diǎn)。實(shí)際上該73節(jié)點(diǎn)的左子樹的最大節(jié)點(diǎn)62和右子樹的最小節(jié)點(diǎn)77都能夠替代73節(jié)點(diǎn)，即它們正好是二叉排序樹中比它小或比它大的最接近73的兩個(gè)數(shù)。

一般我們選擇一種方式即可，我們這次使用右子樹的最小節(jié)點(diǎn)替代要?jiǎng)h除的節(jié)點(diǎn)，使用77替代73之后的結(jié)構(gòu)如下：

完整的代碼如下：

    /**
     * 刪除,開放給外部使用的api
     *
     * @param e 要?jiǎng)h除的元素
     */
    public void delete(E e) {
        //返回root,但此時(shí)可能有一個(gè)節(jié)點(diǎn)已經(jīng)被刪除了
        root = delete(e, root);
    }

    /**
     * 刪除,內(nèi)部調(diào)用的方法,刪除分為三種情況: 1、該節(jié)點(diǎn)沒有子節(jié)點(diǎn) 2、該字節(jié)僅有一個(gè)子節(jié)點(diǎn) 3、該節(jié)點(diǎn)具有兩個(gè)子節(jié)點(diǎn)
     *
     * @param e    要?jiǎng)h除的數(shù)據(jù)
     * @param root 根節(jié)點(diǎn)
     * @return 該節(jié)點(diǎn)
     */
    private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
        /*沒有查找到,那么什么都不做*/
        if (root == null) {
            return null;
        }
        /*調(diào)用比較的方法*/
        int i = compare(e, root.data);
        /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
        if (i > 0) {
            //從新賦值
            root.right = delete(e, root.right);
            /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
        } else if (i < 0) {
            //從新賦值
            root.left = delete(e, root.left);
        } else {
            /*如果等于0，則說明e=root.date 即查詢成功 開始執(zhí)行刪除*/
            /*如果兩個(gè)子節(jié)點(diǎn)都不為null*/
            if (root.left != null && root.right != null) {
                /*方法1、遞歸查找最小的節(jié)點(diǎn)，然后遞歸刪除  該方法不推薦使用*/
                //root.data = findMin(root.right).data;
                //root.right = delete(root.data, root.right);
                /*方法2、遞歸查找并刪除最小的節(jié)點(diǎn) 推薦*/
                root.data = findAndDeleteMin(root.right, root);
                size--;
            } else {
                /*如果一個(gè)子節(jié)點(diǎn)不為null，則返回該子節(jié)點(diǎn)；或者兩個(gè)子節(jié)點(diǎn)都為null，則返回null
                 * 此時(shí)該root節(jié)點(diǎn)已經(jīng)被"繞過了"*/
                root = (root.left != null) ? root.left : root.right;
                size--;
            }
        }
        //沒查詢到最底層,則返回該節(jié)點(diǎn)
        return root;
    }

    /**
     * 查找最小的節(jié)點(diǎn)并刪除
     * 最小的節(jié)點(diǎn)肯定不存在兩個(gè)子節(jié)點(diǎn),有可能沒有子節(jié)點(diǎn),有可能存在右子節(jié)點(diǎn)
     *
     * @param root   節(jié)點(diǎn)
     * @param parent 節(jié)點(diǎn)的父節(jié)點(diǎn)
     * @return 被刪除的最小的節(jié)點(diǎn)
     */
    private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {
        //如果節(jié)點(diǎn)為null，返回
        if (root == null) {
            return null;
            /*如果節(jié)點(diǎn)的左子節(jié)點(diǎn)為null,那么該節(jié)點(diǎn)就是最小的節(jié)點(diǎn)*/
            /*1、該最小節(jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)，因?yàn)樽笞庸?jié)點(diǎn)比父節(jié)點(diǎn)小，但是可能有右子節(jié)點(diǎn)*/
            /*2、此時(shí)該節(jié)點(diǎn)可能作為某個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)，也可能作為原父節(jié)點(diǎn)的右子節(jié)點(diǎn)（即右子樹是一顆右斜樹），這里需要分開討論*/
        } else if (root.left == null) {
            //如果該節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn),說明還沒進(jìn)行遞歸或者第一次遞歸就找到了最小節(jié)點(diǎn).
            //那么此時(shí),應(yīng)該讓該節(jié)點(diǎn)的父節(jié)點(diǎn)的右子節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn),并返回該節(jié)點(diǎn)的數(shù)據(jù)，該節(jié)點(diǎn)由于沒有了強(qiáng)引用，會(huì)被GC刪除
            if (root == parent.right) {
                parent.right = root.right;
            } else {
                //如果該節(jié)點(diǎn)不是父節(jié)點(diǎn)的右子節(jié)點(diǎn)，說明進(jìn)行了多次遞歸。
                //那么此時(shí),應(yīng)該讓該節(jié)點(diǎn)的父節(jié)點(diǎn)的左子節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn),并返回該節(jié)點(diǎn)的數(shù)據(jù)，該節(jié)點(diǎn)由于沒有了強(qiáng)引用，會(huì)被GC刪除
                parent.left = root.right;
            }
            //返回最小節(jié)點(diǎn)的數(shù)據(jù)
            return root.data;
        }
        //遞歸調(diào)用,注意此時(shí)是往左查找
        return findAndDeleteMin(root.left, root);
    }

2.5.1 測(cè)試

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void test() {
        //首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16,73，然后是第三層的節(jié)點(diǎn)1,24,59,88，然后是第四層的節(jié)點(diǎn)20,35,62,77。
        // 每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出,但是樹的結(jié)構(gòu)不能保證。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍歷輸出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));

        //移除
        binarySearchTree.delete(73);
        //中序遍歷輸出
        System.out.println(binarySearchTree.toInorderTraversalString());
    }
}

3 二叉排序樹的總結(jié)

總之，二叉排序樹是以鏈接的方式存儲(chǔ)，保持了鏈接存儲(chǔ)結(jié)構(gòu)在執(zhí)行插入或刪除操作時(shí)不用移動(dòng)元素的優(yōu)點(diǎn)，只要找到合適的插入和刪除位置后，僅需修改鏈接指針即可。

插入刪除的時(shí)間性能比較好。而對(duì)于二叉排序樹的查找，走的就是從根節(jié)點(diǎn)到要查找的節(jié)點(diǎn)的路徑，其比較次數(shù)等于給定值的節(jié)點(diǎn)在二叉排序樹的層數(shù)。極端情況，最少為1次，即根節(jié)點(diǎn)就是要找的節(jié)點(diǎn)，最多也不會(huì)超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀?？蓡栴}就在于，二叉排序樹的形狀是不確定的。

例如{47, 16, 73, 1, 24, 59, 88}這樣的數(shù)組，我們可以構(gòu)建下圖左的二叉排序樹。但如果數(shù)組元素的次序是從小到大有序，如{1, 16, 24, 47, 59, 73, 88}，則二叉排序樹就成了極端的右斜樹，注意它依然是一棵二叉排序樹，如下圖右。此時(shí)，同樣是查找節(jié)點(diǎn)88，左圖只需要3次比較，而右圖就需要7次比較才可以得到結(jié)果，二者差異很大。

也就是說，我們希望二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，均為|log2n+1|(|x|表示不大于x的最大整數(shù))，那么查找的時(shí)間復(fù)雜也就為O(logn)，近似于折半查找，事實(shí)上，上圖的左圖也不夠平衡，明顯的左重右輕。而極端情況下的右圖,則完全退化成為鏈表，查找的時(shí)間復(fù)雜度為O(n)，這等同于順序查找。

因此，如果我們希望對(duì)一個(gè)集合按二叉排序樹查找，最好是把它構(gòu)建成一棵平衡的二叉排序樹，防止極端情況的發(fā)生。這樣我們就引申出另一個(gè)問題，如何讓二叉排序樹平衡的問題。關(guān)于這個(gè)問題，在后續(xù)的平衡二叉樹（AVL樹)的部分將會(huì)詳細(xì)解釋！

以上就是Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java二叉排序樹的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: