40節(jié)介紹了HashMap,41節(jié)介紹了HashSet,它們的共同實(shí)現(xiàn)機(jī)制是哈希表,一個共同的限制是沒有順序,我們提到,它們都有一個能保持順序的對應(yīng)類TreeMap和TreeSet,這兩個類的共同實(shí)現(xiàn)基礎(chǔ)是排序二叉樹,為了更好的理解TreeMap/TreeSet,本節(jié)我們先來介紹排序二叉樹的一些基本概念和算法。

基本概念

先來說樹的概念,現(xiàn)實(shí)中,樹是從下往上長的,樹會分叉,在計算機(jī)程序中,一般而言,與現(xiàn)實(shí)相反,樹是從上往下長的,也會分叉,有個根節(jié)點(diǎn),每個節(jié)點(diǎn)可以有一個或多個孩子節(jié)點(diǎn),沒有孩子節(jié)點(diǎn)的節(jié)點(diǎn)一般稱為葉子節(jié)點(diǎn)。

二叉樹是一個樹,但,每個節(jié)點(diǎn)最多有兩個孩子節(jié)點(diǎn),一左一右,左邊的稱為左孩子,右邊的稱為右孩子,我們看兩個例子,如下所示:

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)
這兩棵樹都是二叉樹,左邊的根節(jié)點(diǎn)為5,除了葉子節(jié)點(diǎn)外,每個節(jié)點(diǎn)都有兩個孩子節(jié)點(diǎn),右邊的根節(jié)點(diǎn)為7,有的節(jié)點(diǎn)有兩個孩子節(jié)點(diǎn),有的只有一個。

網(wǎng)友評論