引子
繼線性表與鏈表的概念篇與源碼剖析篇之后，本來(lái)這篇打算剖析一下HashMap，因?yàn)槊看蚊嬖囍谐霈F(xiàn)率最高的數(shù)據(jù)結(jié)構(gòu)就是HashMap。 但是忽然發(fā)現(xiàn)， 1.8之前的JDK的HashMap基于數(shù)組和鏈表組合實(shí)現(xiàn)，到了1.8之后完全變了，至于它是怎么實(shí)現(xiàn)的，這里賣個(gè)關(guān)子，透漏一下就是跟樹有關(guān)。因此本篇起開始樹系列。
在數(shù)據(jù)結(jié)構(gòu)中，樹和圖是兩種比較復(fù)雜的結(jié)構(gòu)之一；里面涉及各種概念， 各種類型以及不同的算法實(shí)現(xiàn)， 希望想學(xué)習(xí)的小伙伴可以跟著我的節(jié)奏，一起克服這些困難。而且重要的是， 樹在面試中出現(xiàn)的次數(shù)僅次于HashMap， 所以，打起精神來(lái)吧！
樹
先來(lái)說(shuō)說(shuō)普通的樹
樹是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋?lái)像一棵倒掛的樹，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：
1.每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；
2.沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
3.每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
4.除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；
自然中的樹
數(shù)據(jù)結(jié)構(gòu)中的樹
再來(lái)看一下百度的解釋， 我們發(fā)現(xiàn)確實(shí)是一顆倒著的樹，哈哈！重點(diǎn)看圖2，我們總結(jié)一下樹的特點(diǎn)：
- 有且僅有一個(gè)跟節(jié)點(diǎn)A（理解為樹根），也可以沒有（空樹）
- 每個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)除外）只能有一個(gè)父節(jié)點(diǎn)，可以有多個(gè)子節(jié)點(diǎn)
- 層次結(jié)構(gòu)A | BC | DE | ####
- 從任意節(jié)點(diǎn)來(lái)看， 樹是一對(duì)多的關(guān)系
- 樹是節(jié)點(diǎn)的有窮集（節(jié)點(diǎn)數(shù)不是無(wú)限的）
對(duì)照著上圖，來(lái)看一下，是否符合上面說(shuō)的特點(diǎn)！看完上面的描述，大體應(yīng)該對(duì)樹結(jié)構(gòu)有一個(gè)直觀的了解了。 那么來(lái)科普一下關(guān)于樹的概念
1.每個(gè)元素稱為結(jié)點(diǎn)（node）
2.節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；
3.葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)；
4.非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)；
5.雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
6.孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
7.兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
8.樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
9.節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
10.樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；
11.堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；
12.節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
13.子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
14.森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
以上概念都是根據(jù)社會(huì)中的家譜與自然中的事物命名的，結(jié)合家譜應(yīng)該很好理解。先給一個(gè)簡(jiǎn)單的樹的圖，說(shuō)明一下
- 樹的單位是節(jié)點(diǎn)， （線性表的單位是什么？ 元素； 鏈表的單位也是節(jié)點(diǎn)； 圖的單位是頂點(diǎn)）
A-F本身不算節(jié)點(diǎn)，A-F所在的小球是節(jié)點(diǎn)； 節(jié)點(diǎn)包含兩個(gè)信息： 與其他節(jié)點(diǎn)的關(guān)系， 節(jié)點(diǎn)的值（A, B, C）
- 節(jié)點(diǎn)的度
一個(gè)節(jié)點(diǎn)所包含的子樹（子節(jié)點(diǎn)）的個(gè)數(shù)，比如A,B的度都是2（包含兩個(gè)子節(jié)點(diǎn)）； C的度是1（僅包含子節(jié)點(diǎn)F）； D, E, F的度是0（無(wú)子節(jié)點(diǎn)）
- 根節(jié)點(diǎn)與葉節(jié)點(diǎn)
把一顆樹倒過(guò)來(lái)就是樹結(jié)構(gòu)， 那么A就是樹根，稱為根節(jié)點(diǎn)， 根節(jié)點(diǎn)沒有父節(jié)點(diǎn)， 像樹的根。D,E,F就是葉節(jié)點(diǎn)， 葉節(jié)點(diǎn)沒有子節(jié)點(diǎn)，像樹的葉子。
- 父節(jié)點(diǎn)， 子節(jié)點(diǎn)， 兄弟節(jié)點(diǎn)
關(guān)系都是相對(duì)的。 A的子節(jié)點(diǎn)是B和C, 則B和C的父節(jié)點(diǎn)就是A。如果學(xué)過(guò)DNA，可以根據(jù)DNA的圖進(jìn)行關(guān)系認(rèn)定。B和C具有同一個(gè)父親（父節(jié)點(diǎn)）， 那么B和C必然是兄弟（互為兄弟節(jié)點(diǎn)）。
- 堂兄弟節(jié)點(diǎn)， 祖先節(jié)點(diǎn)
現(xiàn)實(shí)中的堂兄弟必然是父輩是親兄弟。 那么B和C具有相同的父節(jié)點(diǎn)，是親兄弟。 所以B的孩子和C的孩子就是堂兄弟。也即D,E,F互為堂兄弟節(jié)點(diǎn)。祖先節(jié)點(diǎn)， 一個(gè)節(jié)點(diǎn)所有的先輩節(jié)點(diǎn)，如F的祖先節(jié)點(diǎn)，C（父節(jié)點(diǎn)）， A（祖父節(jié)點(diǎn)）。
- 節(jié)點(diǎn)的層次
從根節(jié)點(diǎn)開始， 每一層的節(jié)點(diǎn)的所有子節(jié)點(diǎn)算一層。如A是第一層， A的子節(jié)點(diǎn)BC是第二層， BC的子節(jié)點(diǎn)DEF是第三層，以此類推。
- 樹的高度或深度
節(jié)點(diǎn)的最大層次，上圖樹的高度是3； 如果F節(jié)點(diǎn)還有一個(gè)子節(jié)點(diǎn)G, 那么高度就是4。
8.森林
一顆樹，只能有一個(gè)根節(jié)點(diǎn)； 如果一個(gè)圖中，有N個(gè)節(jié)點(diǎn)是沒有父節(jié)點(diǎn)的， 那么整個(gè)圖就是森林。
樹的分類
樹
二叉樹
滿二叉樹 與 完全二叉樹
二叉查找樹（二叉搜索樹或二叉排序樹）
平衡二叉樹（AVL樹）
紅黑樹
二叉樹： 每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)就是二叉樹； 可以沒有子節(jié)點(diǎn)（葉子節(jié)點(diǎn)）， 可以只有一個(gè)子節(jié)點(diǎn)，也可以有兩個(gè)子節(jié)點(diǎn)。上圖就是一個(gè)二叉樹， 它的每個(gè)節(jié)點(diǎn)最多都只有兩個(gè)子節(jié)點(diǎn)
滿二叉樹： 我們知道二叉樹的每個(gè)節(jié)點(diǎn)最多只有2個(gè)子節(jié)點(diǎn)， 那就是它可以允許節(jié)點(diǎn)有一個(gè)或沒有子節(jié)點(diǎn)的。比如上圖的C節(jié)點(diǎn)只有一個(gè)右孩子F。 那么滿二叉樹就是滿的二叉樹，什么是滿的？ 除了葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)必須都要2個(gè)子節(jié)點(diǎn)，不允許一個(gè)子節(jié)點(diǎn)的存在。如果上圖C節(jié)點(diǎn)添加一個(gè)左孩子G , 那么這就是一個(gè)滿二叉樹了。
二叉查找樹，或稱為二叉搜索樹， 二叉排序樹： 首先它是一個(gè)二叉樹，如果不明白二叉樹，看上面。其次它要滿足一定的條件（如果每個(gè)節(jié)點(diǎn)的值是一個(gè)整數(shù)為例）：
- 如果它的左子樹不為空，那么左孩子的值一定小于根節(jié)點(diǎn)的值
- 如果它的右子樹不為空，那么右孩子的值一定大于根節(jié)點(diǎn)的值
看上面兩條其實(shí)很好理解， 我們總結(jié)一下就是：二叉搜索樹的節(jié)點(diǎn)的值是有序的； 它總是符合一個(gè)規(guī)律： 左孩子的值 < 父節(jié)點(diǎn)的值 < 右孩子的值。 還是不好理解？ 那么上個(gè)圖看一下
我們可以看到，每個(gè)節(jié)點(diǎn)的左子樹的值，都小于根節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)的右子樹的值，都大于根節(jié)點(diǎn)。以根節(jié)點(diǎn)12為例， 左子樹是5， 2， 9； 右子樹是18， 15， 19， 17， 16。 拿出任意節(jié)點(diǎn)5， 左孩子節(jié)點(diǎn)是2 < 5, 右孩子節(jié)點(diǎn)是9 > 5。二叉排序樹就是每個(gè)節(jié)點(diǎn)都符合這標(biāo)準(zhǔn)的二叉樹。
在面試或?qū)W習(xí)中， 二分法是極其常用的，它可以在一定程度上大幅度提高查詢效率； 那么對(duì)比一下二叉排序樹， 是不是發(fā)現(xiàn)， 二分法和二叉排序樹的思想是一樣的？
平衡二叉樹，又稱AVL樹： 首先，它還是一個(gè)二叉樹。 其次是平衡， 那么平衡的是什么呢？ 子樹的高度。 它是一顆二叉樹， 滿足任一節(jié)點(diǎn)的左右子樹高度差不會(huì)大于1。 高度是怎么定義的還有印象嗎？
紅黑樹： 這是一種自平衡二叉樹， 后文中會(huì)說(shuō)到。
被動(dòng)的接受永遠(yuǎn)是學(xué)習(xí)的障礙， 接下來(lái)布置一個(gè)小練習(xí)
1. 自己嘗試著畫一下樹的結(jié)構(gòu)，包括二叉樹， 二叉排序樹， 二叉平衡樹，森林等
2. 參考下圖，用代碼實(shí)現(xiàn)一顆樹（因?yàn)榻酉聛?lái)要將遞歸以及如何遍歷二叉樹）
