樹(shù)在數(shù)據(jù)結(jié)構(gòu)中占據(jù)了非常重要的位置，尤其是二叉樹(shù)。經(jīng)常是在java面試中必問(wèn)的一個(gè)環(huán)節(jié)，而且二叉樹(shù)的應(yīng)用場(chǎng)景真的非常普遍，需要重點(diǎn)掌握好。

[[323923]]

但是一直以來(lái)，很多同學(xué)對(duì)于二叉樹(shù)的掌握都是不太全面。今天我就來(lái)談?wù)劧鏄?shù)，希望你喜歡這個(gè)Java數(shù)據(jù)結(jié)構(gòu)與算法這個(gè)專題，認(rèn)真看完后你會(huì)對(duì)二叉樹(shù)會(huì)有一個(gè)比較完整的了解。

本文作者：陳睿|mikechen 優(yōu)知學(xué)院創(chuàng)始人

重點(diǎn)會(huì)談到以下幾點(diǎn)：

• 二叉樹(shù)
• 二叉樹(shù)的遍歷方式
• 二叉樹(shù)有哪些種類
• 滿二叉樹(shù)
• 完全二叉樹(shù)
• 二叉搜索樹(shù)
• 平衡二叉樹(shù)(AVL)
• 左旋與右旋

1.什么是二叉樹(shù)

二叉樹(shù)：就是每個(gè)節(jié)點(diǎn)都只能有兩個(gè)子節(jié)點(diǎn)的樹(shù)結(jié)構(gòu)，俗稱 “大褲衩”，特別形象。

通常子樹(shù)被稱作“左子樹(shù)”(left subtree)和“右子樹(shù)”(right subtree)。

下圖你一看就秒懂了。

2.二叉樹(shù)遍歷方式

2.1二叉樹(shù)的遍歷主要有三種：

1)先(根)序遍歷(根左右)

2)中(根)序遍歷(左根右)

3)后(根)序遍歷(左右根)

2.2 先序遍歷(根左右)

我先從第一種先序遍歷開(kāi)始談起，主要的遍歷順序如下：

1)先訪問(wèn)根結(jié)點(diǎn)

2)然后先序遍歷左子樹(shù)

3)然后先序遍歷右子樹(shù)

還是舉例說(shuō)明，先序遍歷下圖

如果按照先序(根左右)遍歷，結(jié)果將為： ABDFECGHI

2.3 中序遍歷(左根右)

1)先中序遍歷左子樹(shù)

2)然后是根結(jié)點(diǎn)

3)然后中序遍歷右子樹(shù)

還是舉例說(shuō)明，中序遍歷同一顆二叉樹(shù)

按照中序遍歷(左根右)，結(jié)果為： DBEFAGHCI

2.4 后序遍歷

1)后序遍歷左子樹(shù)

2)后序遍歷右子樹(shù)

3)然后訪問(wèn)根節(jié)點(diǎn)

還是舉例說(shuō)明，后序遍歷同一顆二叉樹(shù)

按照后序遍歷(左右根)結(jié)果為：DEFBHGICA

3.二叉樹(shù)的種類

基本包含:

• 滿二叉樹(shù)
• 完全二叉樹(shù)
• 二叉搜索樹(shù)
• 平衡AVL樹(shù)
• 紅黑樹(shù)也屬于AVL樹(shù)

我先從滿二叉樹(shù)談起。

3.1滿二叉樹(shù)

1)滿二叉樹(shù)

一棵樹(shù)深度為k，2^k-1個(gè)節(jié)點(diǎn)的樹(shù)是滿二叉樹(shù)

2)滿二叉樹(shù)的形態(tài)

3)滿二叉樹(shù)的特征

所有內(nèi)部節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，最底一層是葉子節(jié)點(diǎn)。

如果一顆樹(shù)深度為h，最大層數(shù)為k，且深度與最大層數(shù)相同，即k=h;

第k層的結(jié)點(diǎn)數(shù)是：2^(k-1)

總結(jié)點(diǎn)數(shù)是：2^k-1 (2的k次方減一)

總節(jié)點(diǎn)數(shù)一定是奇數(shù)。

樹(shù)高：h=log2(n+1)

3.2.完全二叉樹(shù)

1)完全二叉樹(shù)

若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

2)完全二叉樹(shù)的形態(tài)

3)完全二叉樹(shù)的特征

深度為k的完全二叉樹(shù)，至少有2^(k-1)個(gè)節(jié)點(diǎn)，至多有2^k-1個(gè)節(jié)點(diǎn)。

樹(shù)高h(yuǎn)=log2n + 1

滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)

3.3.二叉查找/搜索/排序樹(shù)-BST

1)二叉搜索樹(shù)

二叉搜索樹(shù)BST(Binary Search/ Sort Tree)，也稱為二叉查找樹(shù)，二叉排序樹(shù)

備注：下面我就以二叉搜索樹(shù)來(lái)統(tǒng)稱，但是你要知道二叉搜索樹(shù)、二叉查找樹(shù)、二叉排序樹(shù)，其實(shí)是同一種樹(shù)。

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

左子樹(shù)上所有結(jié)點(diǎn)的值均小于等于它的根結(jié)點(diǎn)的值

右子樹(shù)上所有結(jié)點(diǎn)的值均大于等于它的根結(jié)點(diǎn)的值

3)二叉搜索樹(shù)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：查找速度快，二叉查找樹(shù)比普通樹(shù)查找更快

缺點(diǎn)：出現(xiàn)平衡問(wèn)題

二叉搜索樹(shù)在經(jīng)過(guò)多次插入與刪除后，有可能導(dǎo)致如下右圖的結(jié)構(gòu)：

搜索性能已經(jīng)是線性的了，所以，使用二叉搜索樹(shù)還要考慮盡可能保持上面左圖的結(jié)構(gòu)，和避免上面右圖的結(jié)構(gòu)，也就是所謂的“平衡”問(wèn)題 。

4)二叉搜索樹(shù)的時(shí)間復(fù)雜度

時(shí)間復(fù)雜度

二叉查找樹(shù)比普通樹(shù)查找更快，查找、插入、刪除的時(shí)間復(fù)雜度為O(logN)。

缺點(diǎn)

二叉查找樹(shù)有一種極端的情況，就是會(huì)變成一種線性鏈表似的結(jié)構(gòu)，此時(shí)時(shí)間復(fù)雜度就變味了O(N)，為了解決這種情況，所以出現(xiàn)了下面我即將談到的二叉平衡樹(shù)。

備注：時(shí)間復(fù)雜度

• O(1)：最低的時(shí)空復(fù)雜度，也就是耗時(shí)與輸入數(shù)據(jù)大小無(wú)關(guān)，無(wú)論輸入數(shù)據(jù)增大多少倍，耗時(shí)/耗空間都不變。哈希算法就是典型的O(1)時(shí)間復(fù)雜度，無(wú)論數(shù)據(jù)規(guī)模多大，都可以在一次計(jì)算后找到目標(biāo)。
• O(n)：代表數(shù)據(jù)量增大幾倍，耗時(shí)也增大幾倍。比如常見(jiàn)的遍歷算法。
• O(logn)：當(dāng)數(shù)據(jù)增大n倍時(shí)，耗時(shí)增大logn倍(這里的log是以2為底的，比如，當(dāng)數(shù)據(jù)增大256倍時(shí)，耗時(shí)只增大8倍，是比線性還要低的時(shí)間復(fù)雜度)。二分查找就是O(logn)的算法，每找一次排除一半的可能，256個(gè)數(shù)據(jù)中查找只要找8次就可以找到目標(biāo)。

3.4.平衡二叉樹(shù)(AVL樹(shù))

1)平衡二叉樹(shù)

平衡二叉樹(shù)全稱平衡二叉搜索樹(shù)，也叫AVL樹(shù),是一種自平衡的樹(shù)，從上面二叉搜索樹(shù)升級(jí)過(guò)來(lái)的，重點(diǎn)是改進(jìn)了平衡問(wèn)題。

2)平衡二叉樹(shù)的特征

• AVL樹(shù)也規(guī)定了左結(jié)點(diǎn)小于根節(jié)點(diǎn)，右結(jié)點(diǎn)大于根節(jié)點(diǎn)。
• 并且還規(guī)定了左子樹(shù)和右子樹(shù)的高度差不得超過(guò)1，這樣保證了它不會(huì)成為線性的鏈表。

3)AVL樹(shù)怎么解決平衡

主要就是通過(guò)左旋和右旋來(lái)解決，防止特殊情況下出現(xiàn)下面的線性結(jié)構(gòu)。

所以通過(guò)下圖的左旋和右旋來(lái)解決上面的平衡問(wèn)題。

但也有對(duì)應(yīng)的缺點(diǎn)，由于要維持自身的平衡，所以進(jìn)行插入和刪除結(jié)點(diǎn)操作的時(shí)候，需要對(duì)結(jié)點(diǎn)進(jìn)行頻繁的旋轉(zhuǎn)。

4.結(jié)語(yǔ)

通過(guò)上述的介紹，已經(jīng)對(duì)于二叉樹(shù)有了初步的認(rèn)識(shí)。本篇文章介紹的基礎(chǔ)知識(shí)希望讀者能夠牢牢掌握，并且能夠在腦海中建立一棵二叉樹(shù)的模型，為后續(xù)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法打好基礎(chǔ)。