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

[[323923]]

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

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

重點會談到以下幾點：

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

1.什么是二叉樹

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

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

下圖你一看就秒懂了。

 

 

2.二叉樹遍歷方式

2.1二叉樹的遍歷主要有三種：

 

 

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

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

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

2.2 先序遍歷(根左右)

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

1)先訪問根結(jié)點

2)然后先序遍歷左子樹

3)然后先序遍歷右子樹

還是舉例說明，先序遍歷下圖

 

 

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

2.3 中序遍歷(左根右)

1)先中序遍歷左子樹

2)然后是根結(jié)點

3)然后中序遍歷右子樹

還是舉例說明，中序遍歷同一顆二叉樹

 

 

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

2.4 后序遍歷

1)后序遍歷左子樹

2)后序遍歷右子樹

3)然后訪問根節(jié)點

還是舉例說明，后序遍歷同一顆二叉樹

 

 

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

3.二叉樹的種類

 

 

基本包含:

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

我先從滿二叉樹談起。

3.1滿二叉樹

1)滿二叉樹

一棵樹深度為k，2^k-1個節(jié)點的樹是滿二叉樹

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

 

 

3)滿二叉樹的特征

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

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

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

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

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

樹高：h=log2(n+1)

3.2.完全二叉樹

1)完全二叉樹

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

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

 

 

3)完全二叉樹的特征

深度為k的完全二叉樹，至少有2^(k-1)個節(jié)點，至多有2^k-1個節(jié)點。

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

滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹

3.3.二叉查找/搜索/排序樹-BST

1)二叉搜索樹

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

 

 

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

2)二叉搜索樹的特點

 

 

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

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

3)二叉搜索樹的優(yōu)缺點

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

缺點：出現(xiàn)平衡問題

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

 

 

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

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

時間復(fù)雜度

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

缺點

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

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

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

3.4.平衡二叉樹(AVL樹)

1)平衡二叉樹

平衡二叉樹全稱平衡二叉搜索樹，也叫AVL樹,是一種自平衡的樹，從上面二叉搜索樹升級過來的，重點是改進(jìn)了平衡問題。

2)平衡二叉樹的特征

 

 

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

3)AVL樹怎么解決平衡

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

 

 

所以通過下圖的左旋和右旋來解決上面的平衡問題。

 

 

 

 

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

4.結(jié)語

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