詳解二叉樹的遍歷以及完全二叉樹等6種二叉樹

作者：優知學院 2020-04-27 07:05:58

開發前端

樹在數據結構中占據了非常重要的位置，尤其是二叉樹。經常是在java面試中必問的一個環節，而且二叉樹的應用場景真的非常普遍，需要重點掌握好。

[[323923]]

但是一直以來，很多同學對于二叉樹的掌握都是不太全面。今天我就來談談二叉樹，希望你喜歡這個Java數據結構與算法這個專題，認真看完后你會對二叉樹會有一個比較完整的了解。

本文作者：陳睿|mikechen 優知學院創始人

重點會談到以下幾點：

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

1.什么是二叉樹

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

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

下圖你一看就秒懂了。

2.二叉樹遍歷方式

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

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

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

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

2.2 先序遍歷(根左右)

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

1)先訪問根結點

2)然后先序遍歷左子樹

3)然后先序遍歷右子樹

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

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

2.3 中序遍歷(左根右)

1)先中序遍歷左子樹

2)然后是根結點

3)然后中序遍歷右子樹

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

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

2.4 后序遍歷

1)后序遍歷左子樹

2)后序遍歷右子樹

3)然后訪問根節點

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

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

3.二叉樹的種類

基本包含:

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

我先從滿二叉樹談起。

3.1滿二叉樹

1)滿二叉樹

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

2)滿二叉樹的形態

3)滿二叉樹的特征

所有內部節點都有兩個子節點，最底一層是葉子節點。

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

第k層的結點數是：2^(k-1)

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

總節點數一定是奇數。

樹高：h=log2(n+1)

3.2.完全二叉樹

1)完全二叉樹

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

2)完全二叉樹的形態

3)完全二叉樹的特征

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

樹高h=log2n + 1

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

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

1)二叉搜索樹

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

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

2)二叉搜索樹的特點

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

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

3)二叉搜索樹的優缺點

優點：查找速度快，二叉查找樹比普通樹查找更快

缺點：出現平衡問題

二叉搜索樹在經過多次插入與刪除后，有可能導致如下右圖的結構：

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

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

時間復雜度

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

缺點

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

備注：時間復雜度

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

3.4.平衡二叉樹(AVL樹)

1)平衡二叉樹

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

2)平衡二叉樹的特征