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

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

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

1 二叉排序樹的概述

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

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

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

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

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

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

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

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

2.1 類架構(gòu)

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

另外還需要一個比較器的引用，因為需要對元素進行排序，自然需要比較元素的大小，如果外部傳遞了比較器，那么就使用用戶指定的比較器進行比較，否則，數(shù)據(jù)類型E必須是Comparable接口的子類，否則因為不能比較而報錯。

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

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

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


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

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

        //數(shù)據(jù)域
        E data;
        //左子節(jié)點
        BinaryTreeNode<E> left;
        //右子節(jié)點
        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é)點數(shù)
     *
     * @return 節(jié)點數(shù)
     */
    public int size() {
        return size;
    }


    /**
     * 對元素進行比較大小的方法,如果傳遞了自定義比較器,則使用自定義比較器,否則則需要數(shù)據(jù)類型實現(xiàn)Comparable接口
     *
     * @param e1 被比較的第一個對象
     * @param e2 被比較的第二個對象
     * @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é)點數(shù)據(jù)
     */
    List<BinaryTreeNode<E>> str = new ArrayList<>();

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

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

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

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

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

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

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

}

2.2 查找的方法

查找的方法很簡單：

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

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

/**
 * 查找,內(nèi)部調(diào)用的方法,從根節(jié)點開始查找
 *
 * @param e    要查找的元素
 * @param root 節(jié)點
 * @return false 不存在 true 存在
 */
private boolean contains(E e, BinaryTreeNode<E> root) {
    /*null校驗*/
    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ù)，那么所謂的二叉排序樹的插入，其實也就是將關(guān)鍵字放到樹中的合適位置而已，插入操作就好像在調(diào)用查找的操作，如果找到了那么什么都不做，返回false，如果沒找到，則將要插入的元素插入到遍歷的路徑的最后一點上：

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

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

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

}

/**
 * 插入,內(nèi)部調(diào)用的方法,先從根節(jié)點開始遞歸查找要插入的位置,然后插入
 *
 * @param e    要插入的數(shù)據(jù)
 * @param root 節(jié)點
 * @return 原節(jié)點或者新插入的節(jié)點
 */
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
    /*沒有查找到,那么直接構(gòu)建新的節(jié)點返回,將會在上一層方法中被賦值給其父節(jié)點的某個引用,這個插入的位置肯定是該遍歷路徑上的最后一點
     * 即插入的元素節(jié)點肯定是屬于葉子節(jié)點*/
    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é)點 什么都不做*/
    }
    //沒查詢到最底層,則返回該節(jié)點
    return root;
}

2.3.1 測試

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

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

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

    @Test
    public void insert() {
        //首先要插入根節(jié)點47，然后是第二層的節(jié)點16,73，然后是第三層的節(jié)點1,24,59,88，然后是第四層的節(jié)點20,35,62,77。
        // 每一層內(nèi)部節(jié)點的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結(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());

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

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

2.4 查找最大值和最小值

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

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

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

2.5 刪除的方法

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

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

例如，刪除20之后：

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

例如，刪除59之后：

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

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

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

完整的代碼如下：

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

    /**
     * 刪除,內(nèi)部調(diào)用的方法,刪除分為三種情況: 1、該節(jié)點沒有子節(jié)點 2、該字節(jié)僅有一個子節(jié)點 3、該節(jié)點具有兩個子節(jié)點
     *
     * @param e    要刪除的數(shù)據(jù)
     * @param root 根節(jié)點
     * @return 該節(jié)點
     */
    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í)行刪除*/
            /*如果兩個子節(jié)點都不為null*/
            if (root.left != null && root.right != null) {
                /*方法1、遞歸查找最小的節(jié)點，然后遞歸刪除  該方法不推薦使用*/
                //root.data = findMin(root.right).data;
                //root.right = delete(root.data, root.right);
                /*方法2、遞歸查找并刪除最小的節(jié)點 推薦*/
                root.data = findAndDeleteMin(root.right, root);
                size--;
            } else {
                /*如果一個子節(jié)點不為null，則返回該子節(jié)點；或者兩個子節(jié)點都為null，則返回null
                 * 此時該root節(jié)點已經(jīng)被"繞過了"*/
                root = (root.left != null) ? root.left : root.right;
                size--;
            }
        }
        //沒查詢到最底層,則返回該節(jié)點
        return root;
    }

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

2.5.1 測試

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

    @Test
    public void test() {
        //首先要插入根節(jié)點47，然后是第二層的節(jié)點16,73，然后是第三層的節(jié)點1,24,59,88，然后是第四層的節(jié)點20,35,62,77。
        // 每一層內(nèi)部節(jié)點的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結(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é)

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

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

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

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

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

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

您可能感興趣的文章: