這篇文章主要為大家展示了“java集合之TreeMap源碼的示例分析”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“java集合之TreeMap源碼的示例分析”這篇文章吧。

十年的禮縣網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整禮縣建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)公司從事“禮縣網(wǎng)站設(shè)計”,“禮縣網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

二叉樹的遍歷

我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、后序遍歷。

（1）前序遍歷，先遍歷我，再遍歷我的左子節(jié)點，最后遍歷我的右子節(jié)點；

（2）中序遍歷，先遍歷我的左子節(jié)點，再遍歷我，最后遍歷我的右子節(jié)點；

（3）后序遍歷，先遍歷我的左子節(jié)點，再遍歷我的右子節(jié)點，最后遍歷我；

這里的前中后都是以“我”的順序為準(zhǔn)的，我在前就是前序遍歷，我在中就是中序遍歷，我在后就是后序遍歷。

下面讓我們看看經(jīng)典的中序遍歷是怎么實現(xiàn)的：

public class TreeMapTest {

    public static void main(String[] args) {
        // 構(gòu)建一顆10個元素的樹
        TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
                .insert(6).insert(3).insert(5).insert(9)
                .insert(7).insert(8).insert(4).insert(10);

        // 中序遍歷，打印結(jié)果為1到10的順序
        node.root().inOrderTraverse();
    }
}

/**
 * 樹節(jié)點，假設(shè)不存在重復(fù)元素
 * @param <T>
 */
class TreeNode<T extends Comparable<T>> {
    T value;
    TreeNode<T> parent;
    TreeNode<T> left, right;

    public TreeNode(T value, TreeNode<T> parent) {
        this.value = value;
        this.parent = parent;
    }

    /**
     * 獲取根節(jié)點
     */
    TreeNode<T> root() {
        TreeNode<T> cur = this;
        while (cur.parent != null) {
            cur = cur.parent;
        }
        return cur;
    }

    /**
     * 中序遍歷
     */
    void inOrderTraverse() {
        if(this.left != null) this.left.inOrderTraverse();
        System.out.println(this.value);
        if(this.right != null) this.right.inOrderTraverse();
    }

    /**
     * 經(jīng)典的二叉樹插入元素的方法
     */
    TreeNode<T> insert(T value) {
        // 先找根元素
        TreeNode<T> cur = root();

        TreeNode<T> p;
        int dir;

        // 尋找元素應(yīng)該插入的位置
        do {
            p = cur;
            if ((dir=value.compareTo(p.value)) < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        } while (cur != null);

        // 把元素放到找到的位置
        if (dir < 0) {
            p.left = new TreeNode<>(value, p);
            return p.left;
        } else {
            p.right = new TreeNode<>(value, p);
            return p.right;
        }
    }
}

TreeMap的遍歷

從上面二叉樹的遍歷我們很明顯地看到，它是通過遞歸的方式實現(xiàn)的，但是遞歸會占用額外的空間，直接到線程棧整個釋放掉才會把方法中申請的變量銷毀掉，所以當(dāng)元素特別多的時候是一件很危險的事。

（上面的例子中，沒有申請額外的空間，如果有聲明變量，則可以理解為直到方法完成才會銷毀變量）

那么，有沒有什么方法不用遞歸呢？

讓我們來看看java中的實現(xiàn)：

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    // 遍歷前的修改次數(shù)
    int expectedModCount = modCount;
    // 執(zhí)行遍歷，先獲取第一個元素的位置，再循環(huán)遍歷后繼節(jié)點
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        // 執(zhí)行動作
        action.accept(e.key, e.value);

        // 如果發(fā)現(xiàn)修改次數(shù)變了，則拋出異常
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

是不是很簡單？！

（1）尋找第一個節(jié)點；

從根節(jié)點開始找最左邊的節(jié)點，即最小的元素。

    final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        // 從根節(jié)點開始找最左邊的節(jié)點，即最小的元素
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

（2）循環(huán)遍歷后繼節(jié)點；

尋找后繼節(jié)點這個方法我們在刪除元素的時候也用到過，當(dāng)時的場景是有右子樹，則從其右子樹中尋找最小的節(jié)點。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        // 如果當(dāng)前節(jié)點為空，返回空
        return null;
    else if (t.right != null) {
        // 如果當(dāng)前節(jié)點有右子樹，取右子樹中最小的節(jié)點
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果當(dāng)前節(jié)點沒有右子樹
        // 如果當(dāng)前節(jié)點是父節(jié)點的左子節(jié)點，直接返回父節(jié)點
        // 如果當(dāng)前節(jié)點是父節(jié)點的右子節(jié)點，一直往上找，直到找到一個祖先節(jié)點是其父節(jié)點的左子節(jié)點為止，返回這個祖先節(jié)點的父節(jié)點
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

讓我們一起來分析下這種方式的時間復(fù)雜度吧。

首先，尋找第一個元素，因為紅黑樹是接近平衡的二叉樹，所以找最小的節(jié)點，相當(dāng)于是從頂?shù)降琢?，時間復(fù)雜度為O(log n)；

其次，尋找后繼節(jié)點，因為紅黑樹插入元素的時候會自動平衡，最壞的情況就是尋找右子樹中最小的節(jié)點，時間復(fù)雜度為O(log k)，k為右子樹元素個數(shù)；

最后，需要遍歷所有元素，時間復(fù)雜度為O(n)；

所以，總的時間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。

雖然遍歷紅黑樹的時間復(fù)雜度是O(n)，但是它實際是要比跳表要慢一點的，啥？跳表是啥？安心，后面會講到跳表的。

以上是“java集合之TreeMap源碼的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

分享題目：java集合之TreeMap源碼的示例分析
文章路徑：http://aaarwkj.com/article26/iioicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、響應(yīng)式網(wǎng)站、標(biāo)簽優(yōu)化、靜態(tài)網(wǎng)站、虛擬主機、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)