文章首發于「陳樹義」公衆号及個人部落格 shuyi.tech，歡迎通路更多有趣有價值的文章。
文章首發于「陳樹義」公衆号及個人部落格 shuyi.tech
樹結構是資料結構中非常重要的一種類型，本文将從最基礎的普通樹結構入門，延伸到二叉樹，再延伸至二叉查找樹。通過這種思路，讓大家建構起關于樹的最基本的知識鍊路。
普通樹
樹是一種非線性資料結構，它是資料元素按分支關系組織起來的結構，很像自然界中的樹那樣。
關于樹的官方定義是：一棵樹是由 N（N>0）個元素組成的有限集合，其中：
- 每個元素稱為結點（node）。
- 有一個特定的結點，稱為根結點或根（root）。
- 除根結點外，其餘結點被分成 m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹（稱為原樹的子樹）。
關于樹有幾個重要的概念，這裡簡單做下介紹：
- 度
度即節點的分支數，例如上圖樹中節點 A 有三個子節點，那麼我們稱節點 A 的度是 3。
- 層次
節點的層次，表示節點在書中的位置。根結點的層次為 1，其他結點的層次等于它的父結點的層次數加 1。例如上圖中節點 F 的層次為 3。
- 深度
樹的深度，即組成該樹各節點的最大層次。例如上圖中節點的最大層次為 K/L/M，那麼樹的深度就為 K/L/M 任何一個的層次，即樹的深度為 4。
- 路徑
對于一棵子樹中的任意兩個不同的結點，如果從一個結點出發，按層次自上而下沿着一個個樹枝能到達另一結點，稱它們之間存在着一條路徑。可用路徑所經過的結點序清單示路徑，路徑的長度等于路徑上的結點個數減 1。
例如上圖中 A 到 L 的路徑為：A > B > E > L，其路徑結點個數為 4，那麼其長度為 3。
二叉樹
二叉樹其實就是在普通樹的基礎上，加上了對樹的度限制，即每個節點最多隻能有兩個子節點。 二叉樹有五種基本的形态：
1、空二叉樹 —— 如圖 a 所示。
2、隻有一個根結點的二叉樹 —— 如圖 b 所示。
3、隻有左子樹 —— 如圖 c 所示。
4、隻有右子樹 —— 如圖 d 所示。
5、完全二叉樹 —— 如圖 e 所示。
二叉樹是一種簡單且重要的樹，許多其他類型的樹都建立在二叉樹的基礎之上。根據葉子節點的不同情形，我們可以将二叉樹再細分為：完滿二叉樹、完全二叉樹、滿二叉樹。
完滿二叉樹，指的是所有非葉子節點的度都是 2（隻有你有孩子，你必然有兩個孩子）。
完全二叉樹，指的是深度為 k，有 n 個結點的二叉樹當且僅當其每一個結點都與深度為 k 的滿二叉樹中編号從 1 到 n 的結點一一對應。簡單地說，完全二叉樹是滿二叉樹的一個子集。簡單地說，完全二叉樹就是非葉子節點都有兩個子節點，并且必須是從左到右、從上到下的順序。
滿二叉樹，指的是一棵二叉樹隻有度為 0 的結點和度為 2 的結點，并且度為 0 的結點在同一層上，則這棵二叉樹為滿二叉樹。 簡單地說，就是所有葉子節點都在同一個層上，每一層都鋪滿了節點。
文章首發于「陳樹義」公衆号及個人部落格 shuyi.tech，歡迎通路更多有趣有價值的文章。
二叉查找樹
上面學了那麼多樹結構的知識，但都沒有實際應用，隻能說是在打基礎，了解基本概念。而二叉查找樹可以說是一個非常實用的資料結構，可以用來快速查找元素。
二叉查找樹（Binary Search Tree，BST），有些稱其為二叉排序樹，其平均查找效率為 O(logN)，最差查找效率為 O(N)（退化為連結清單）。而其能實作如此快速的查找速度，主要是其對于資料存儲順序的限制。
二叉查找樹的定義為：
- 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。
- 若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
- 左、右子樹也分别為二叉排序樹
- 沒有鍵值相等的結點
根據上面二叉查找樹的定義，我們不難畫出下面的二叉查找樹。可以看到根節點的 7 元素，大于左邊的 3 元素，小于右邊的 11 元素。而左右子樹 3、11 也同樣符合這樣的規律。
根據這樣的元素排序，要查找一個元素最多隻需要查找樹的深度次數就夠了。例如要查找元素 5，那麼我們的查找路徑是：7 > 3 > 5，隻需要查找 3 次。而如果要查找 4，那麼我們的查找路徑是：7 > 3 > 5 > 4，隻需要查找 4 次。根據二叉樹的深度與節點數量的關系，我們就可以算出二叉查找樹的深度為 O(LogN），即二叉查找樹的時間複雜度為 O(LogN）。
二叉查找樹在查詢方面的效率提升是巨大的，比起連結清單來說提升了幾萬倍。特别是在資料量不斷增大的情況下，其提升性能更加恐怖。例如我們有 1 億個元素，如果使用連結清單存儲，那麼其平均需要比較 5000 萬次。而使用二叉查找樹存儲，我們隻需要比較 27 次就可以了。5000 萬次與 27 次想比較，相差了 185 萬倍！
但二叉查找樹也有一個問題，即它在極端情況下會退化成連結清單。例如我們有這樣一組數字：30、20、10、1，它們組成二叉查找樹之後就會退化成普通連結清單。
那麼如何彌補二叉查找樹的這個缺陷呢？這就涉及到了樹的平衡這個概念。根據樹平衡這個思路，先賢們又創造出了平衡二叉樹這個概念，創造出了 AVL 樹、紅黑樹等經典的資料結構。我們下回繼續聊平衡二叉樹。
總結
今天我們介紹了普通樹結構，以及其相關的基礎概念。接着我們介紹了非常基礎的二叉樹結構，接着将其擴充到完滿二叉樹、完全二叉樹、滿二叉樹。最後，介紹了二叉查找樹結構，以及存在的問題。從今天的文章中，我們可以得出一些結論：
- 二叉樹是特殊的樹結構，表示其最多隻有兩個節點。
- 完滿二叉樹是非葉子節點都有 2 個節點的二叉樹。
- 完全二叉樹是在完滿二叉樹的基礎上，加上左右到有、從上到下都有節點的限制。
- 滿二叉樹是是在完全二叉樹的基礎上，加上每層的節點都是滿的這個限制。
- 二叉查找樹能實作 O（logN）的時間複雜度查找，但是會有退化成連結清單的風險。
到目前為止，我們将學習到的的樹結構搭建起來，可以畫出如下的樹結構大道。
參考資料
- 完美二叉樹，完全二叉樹和完滿二叉樹 - veli - 部落格園
- 6 天通吃樹結構 —— 第一天 二叉查找樹 - 一線碼農 - 部落格園