數(shù)組和鏈表都是用來解決一對(duì)一問題的，而一對(duì)多問題則需要樹來解決。這里，我們重點(diǎn)關(guān)注二叉排序樹，所以只會(huì)介紹一些必需了解的概念，關(guān)于樹的更多知識(shí)，大家可以查看相關(guān)書籍進(jìn)行系統(tǒng)的學(xué)習(xí)。

樹的定義

樹(Tree)是n(n≥0) 個(gè)結(jié)點(diǎn)的有限集。n=0 時(shí)稱為空樹。在任意一棵非空樹中:
1. 有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；
2. 當(dāng)n>1 時(shí)，其余結(jié)點(diǎn)可分為m (m>0) 個(gè)互不相交的有限集T1 、T2、……、Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。

下圖就是一棵樹：

樹示意圖

與現(xiàn)實(shí)中的樹不同，數(shù)據(jù)結(jié)構(gòu)里的樹的根在最上方，并且只有一個(gè)根，就像一棵倒置的樹。樹的每個(gè)結(jié)點(diǎn)往下都是一棵子樹，且這些子樹不能相交，如下所示就不是一棵正確的樹：

樹的錯(cuò)誤示例

相關(guān)概念

結(jié)點(diǎn)分類

樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度(Degree) 。度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)(Leaf) 或終端結(jié)點(diǎn)；度不為0 的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。除根結(jié)點(diǎn)之外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。

如下圖所示，A結(jié)點(diǎn)為根節(jié)點(diǎn)，G、H、I、J、F為葉節(jié)點(diǎn)，其余節(jié)點(diǎn)則為內(nèi)部節(jié)點(diǎn)，此樹的度為3。

度

結(jié)點(diǎn)間關(guān)系

結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子(Child)，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parent)。同一個(gè)雙親的孩子之間互稱兄弟(Sibling)。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。

關(guān)系示意圖

深度

結(jié)點(diǎn)的層次(LeveI)從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第L層，則其子樹的根就在第L+1 層。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Depth)或高度 。

深度示意圖

有序樹，無序樹

如果將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。

二叉樹

二叉樹(Binary Tree)是n(n ≥ 0) 個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

下圖就是一個(gè)二叉樹，二叉樹就是每個(gè)結(jié)點(diǎn)的度≤2的樹。

二叉樹示意圖

二叉樹有許多有用的性質(zhì)，還有一些詳細(xì)的分類，相關(guān)知識(shí)大家可以自行查閱資料。

二叉樹遍歷

二叉樹的遍歷(traversing binary tree)是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次旦僅被訪問一次。

前序遍歷

規(guī)則是若二叉樹為空，則空操作返回，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹， 再前序遍歷右子樹。

如下圖所示，遍歷結(jié)果為：ABDGHCEIF。

前序遍歷

中序遍歷

規(guī)則是若樹為空，則空操作返回，否則從根結(jié)點(diǎn)開始(注意并不是先訪問根結(jié)點(diǎn)) ，中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。

如下圖所示，遍歷結(jié)果為：GDHBAEICF。

中序遍歷

后序遍歷

規(guī)則是若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后是訪問根結(jié)點(diǎn)。

如下圖所示，遍歷結(jié)果為：GHDBIEFCA。

后序遍歷

上一篇：Java集合源碼分析之基礎(chǔ)（二）：哈希表

下一篇：Java集合源碼分析之基礎(chǔ)（四）：二叉排序樹

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長(zhǎng)。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。