[[387073]]

3 月 12 號(hào)，是全國(guó)的重大節(jié)日：植樹(shù)節(jié)。記得小時(shí)候就跟隨老師一起植過(guò)樹(shù)?，F(xiàn)在參加工作了，雖然沒(méi)有植過(guò)樹(shù)，但是學(xué)到過(guò)很多樹(shù)的結(jié)構(gòu)，比如二叉樹(shù)、B+ 樹(shù)，紅黑樹(shù)。每次面試必問(wèn)，恰逢植樹(shù)節(jié)，本來(lái)是想講解 B 樹(shù)，但發(fā)現(xiàn)必須要理解了二叉樹(shù)之后才能更好地講解 B 樹(shù)，所以先給大家講下二叉樹(shù)是什么，后面文章再更新 B 樹(shù)。

大白話講解二叉樹(shù)

比如現(xiàn)在有個(gè)數(shù)組，存放了很多用戶的名字，需要從這個(gè)數(shù)組中找到包含指定的用戶名，最快的方式是什么?

我們會(huì)想到二分查找，雖然這種方式很快，但要達(dá)到最快還需要有個(gè)條件：數(shù)組有序。

如果我們能把插入用戶名的時(shí)候直接給他排序，那最后的結(jié)構(gòu)就是有序結(jié)構(gòu)。

因此有人設(shè)計(jì)了一種數(shù)據(jù)結(jié)構(gòu)：二叉查找樹(shù)，也叫做二叉樹(shù)。

如下圖所示：這是一種二叉樹(shù)結(jié)構(gòu)。

二叉樹(shù)

根據(jù)上文中的例子的，假定 Herry 在最上面，下面有 Alice，Mike，Ivy，Tom，從左到右，從上到下來(lái)看的話，最后的排序是：Alice->Herry->Ivy->Mike->Tom，確實(shí)是按照字母順序排的。

名字排序說(shuō)明

其中有四個(gè)術(shù)語(yǔ)需要說(shuō)明：節(jié)點(diǎn)、左節(jié)點(diǎn)、右節(jié)點(diǎn)、根節(jié)點(diǎn)。

其中每個(gè)紅色圓球都算一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)左下邊相連接的節(jié)點(diǎn)叫做左節(jié)點(diǎn)，而右邊相連的叫做右節(jié)點(diǎn)。比如 Alice 被稱作 Herry 節(jié)點(diǎn)的左節(jié)點(diǎn)，Mike 被稱作 Herry 的右節(jié)點(diǎn)。而根節(jié)點(diǎn)只會(huì)有一個(gè)，屬于最上面的節(jié)點(diǎn)，上圖中的 Herry 就是根節(jié)點(diǎn)。

對(duì)于其中每個(gè)節(jié)點(diǎn)，左子節(jié)點(diǎn)的值都比它小，而右子節(jié)點(diǎn)的值都比它大。比如 Alice < Herry < Mike。

假設(shè)現(xiàn)在我們想要查找 Ivy，首先檢查根節(jié)點(diǎn)，發(fā)現(xiàn)比 Herry 大，所以往下繼續(xù)找，找到了根節(jié)點(diǎn)的右節(jié)點(diǎn) Mike，再繼續(xù)找，比 Mike 小，所以找 Mike 的左節(jié)點(diǎn)，正好找到 Ivy。

二叉查找樹(shù)中查找節(jié)點(diǎn)時(shí)，平均運(yùn)行時(shí)間是 O(logn)，最糟糕的情況下所需時(shí)間為 O(n); 而在有序數(shù)組中查找時(shí)，及時(shí)最糟糕的情況，二分查找最多也是 O(logn)，所以你可能會(huì)覺(jué)得，二分查找比二叉查找要快很多。但是二叉查找樹(shù)的插入和刪除操作的速度是要快很多的。這里我們做一個(gè)對(duì)比：

二叉樹(shù)與二分查找算法對(duì)比

但是二叉樹(shù)也有缺點(diǎn)：

• 不能隨機(jī)訪問(wèn)。比如想要查找第 10 個(gè)元素，是不能返回第十個(gè)元素的，但是數(shù)組就可以通過(guò)下標(biāo)索引找到。
• 二叉樹(shù)存在不平衡的情況，比如以根節(jié)點(diǎn)為中間的界限，發(fā)現(xiàn)右邊的節(jié)點(diǎn)數(shù)遠(yuǎn)超左邊的節(jié)點(diǎn)數(shù)，那么左右不平衡，查找的效率就很低了。如下圖所示：

右邊節(jié)點(diǎn)數(shù)遠(yuǎn)大于左邊節(jié)點(diǎn)數(shù)

那有沒(méi)有平衡的二叉樹(shù)呢?當(dāng)然有，那就是紅黑樹(shù)，限于篇幅和側(cè)重點(diǎn)，這個(gè)放到下篇再講吧

二叉樹(shù)中的含義

二叉樹(shù)定義

大白話說(shuō)二叉樹(shù)就是每個(gè)節(jié)點(diǎn)只能有兩顆子樹(shù)，且有左右之分。

來(lái)看看專業(yè)定義：二叉樹(shù)是 n(n>=0 ) 個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹(shù))，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)組成。

二叉樹(shù)有 5 種形態(tài)

空二叉樹(shù)。

只有一個(gè)根節(jié)點(diǎn)的二叉樹(shù)。

只有左子樹(shù)

只有右子樹(shù)。

完全二叉樹(shù)。

節(jié)點(diǎn)的度

定義：節(jié)點(diǎn)擁有的子樹(shù)數(shù)目稱為節(jié)點(diǎn)的度。

我們來(lái)看下圖就一目了然了。

mark

比如節(jié)點(diǎn) B 的度為 2，節(jié)點(diǎn) E 的度 為 1.

而樹(shù)的度就是所有節(jié)點(diǎn)的度的最大值，也就是 2。

節(jié)點(diǎn)層次

如下圖所示：根節(jié)點(diǎn)為第一層，依次類推。

二叉樹(shù)的特點(diǎn)

每個(gè)節(jié)點(diǎn)最多有顆子樹(shù)，所以二叉樹(shù)中不存在度大于 2 的節(jié)點(diǎn)。

左右子樹(shù)是有順序的，次序不能任意顛倒。

即使某個(gè)節(jié)點(diǎn)只有一顆子樹(shù)，也是需要區(qū)分它是左子樹(shù)還是右子樹(shù)。

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷：從二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都能被訪問(wèn)一次，且僅被訪問(wèn)一次。

二叉樹(shù)的訪問(wèn)次序可以分為四種：

• 前序遍歷。
• 中序遍歷。
• 后續(xù)遍歷。
• 層序遍歷。

前序遍歷：通俗的說(shuō)就是從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谝淮蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左再向右的方向訪問(wèn)。

中序遍歷：就是從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)诙蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左再向右的方向訪問(wèn)。

后序遍歷：就是從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谌蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左再向右的方向訪問(wèn)。

層次遍歷：就是按照樹(shù)的層次自上而下的遍歷二叉樹(shù)。

mark

按照前序遍歷的結(jié)果就是 BADCE。

按照中序遍歷的結(jié)果就是 ABCDE。

按照后續(xù)遍歷的結(jié)果就是 ACEDB。

按照層次遍歷的結(jié)果就是 BADCE。

巨人的肩膀：

《算法圖解》

本文轉(zhuǎn)載自微信公眾號(hào)「悟空聊架構(gòu)」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系悟空聊架構(gòu)公眾號(hào)。