什麼是樹？
資料結構都像自然界中的樹一樣，從同一個“根”衍生出許多“枝幹”，再 從每一個“枝幹”衍生出許多更小的“枝幹”，最後衍生出更多的“葉子”。
在資料結構中，樹的定義如下。
樹（tree）是n（n≥0）個節點的有限集。當n=0時，稱為空樹。在任意一 個非空樹中，有如下特點。
1. 有且僅有一個特定的稱為根的節點。
2. 當n>1時，其餘節點可分為m（m>0）個互不相交的有限集，每一個集合本身又是一個樹，并稱為根的子樹。
下面這張圖，就是一個标準的樹結構。
在上圖中，節點1是根節點（root） ；節點5、6、7、8是樹的末端，沒 有“孩子”，被稱為葉子節點（leaf） 。圖中的虛線部分，是根節點1的其中一個子樹 。
同時，樹的結構從根節點到葉子節點，分為不同的層級。從一個節點的角度來看，它的上下級和同級節點關系如下。
在上圖中，節點4的上一級節點，是節點4的父節點（parent） ；從節點4衍生出來的節點，是節點4的孩子節點（child） ；和節點4同級，由同一個父節點衍生出來的節點，是節點4的兄弟節點（sibling） 。
樹的最大層級數，被稱為樹的高度或深度。顯然，上圖這個樹的高度是 4。
什麼是二叉樹
二叉樹（binary tree）是樹的一種特殊形式。二叉，顧名思義，這種樹每個節點最多有2個孩子節點 。注意，這裡是最多有2個，也可能隻有1個，或者沒有孩子節點。
二叉樹的結構如圖所示。
二叉樹節點的兩個孩子節點，一個被稱為左孩子（left child） ，一個被稱為右孩子（right child） 。這兩個孩子節點的順序是固定的，就像人的左手就是左手，右手就是右手，不能夠颠倒或混淆。
此外，二叉樹還有兩種特殊形式，一個叫作滿二叉樹 ，另一個叫作完全二叉樹 。
什麼是滿二叉樹呢？
一個二叉樹的所有非葉子節點都存在左右孩子，并且所有葉子節點都在同一層級上，那麼這個樹就是滿二叉樹。
簡單點說，滿二叉樹的每一個分支都是滿的。
什麼又是完全二叉樹呢？完全二叉樹的定義很有意思。
對一個有n個節點的二叉樹，按層級順序編号，則所有節點的編号為從1到n。如果這個樹所有節點和同樣深度的滿二叉樹的編号為從1到n的節 點位置相同，則這個二叉樹為完全二叉樹。
這個定義還真繞，看看下圖就很容易了解了。
在上圖中，二叉樹編号從1到12的12個節點，和前面滿二叉樹編号從1到12的節點位置完全對應。是以這個樹是完全二叉樹。
完全二叉樹的條件沒有滿二叉樹那麼苛刻：滿二叉樹要求所有分支都是滿的；而完全二叉樹隻需保證最後一個節點之前的節點都齊全即可。
二叉樹在記憶體中是怎樣存儲的呢？
前面講過，資料結構可以劃分為實體結構和邏輯結構。二叉樹屬于邏輯結構，它可以通過多種物 理結構來表達。
二叉樹可以用哪些實體存儲結構來表達呢？
1. 鍊式存儲結構。
2. 數組。
鍊式存儲結構
鍊式存儲是二叉樹最直覺的存儲方式。
上一章講過連結清單，連結清單是一對一的存儲方式，每一個連結清單節點擁有data變量和一個指向下一節點的next指針。
而二叉樹稍微複雜一些，一個節點最多可以指向左右兩個孩子節點，所 以二叉樹的每一個節點包含3部分。
- 存儲資料的data變量
- 指向左孩子的left指針
- 指向右孩子的right指針
數組存儲結構。
使用數組存儲時，會按照層級順序把二叉樹的節點放到數組中對應的位置上。如果某一個節點的左孩子或右孩子空缺，則數組的相應位置也空出來。
為什麼這樣設計呢？因為這樣可以更友善地在數組中定位二叉樹的孩子節點和父節點。
假設一個父節點的下标是parent，那麼它的左孩子節點下标就是：2×parent + 1 ；右孩子節點下标就是2×parent + 2 。
反過來，假設一個左孩子節點的下标是leftChild，那麼它的父節點下标就是 （leftChild-1）/ 2 。
假如節點4在數組中的下标是3，節點4是節點2的左孩子，節點2的下标可以直接通過計算得出。 節點2的下标 = (3-1)/2 = 1
顯然，對于一個稀疏的二叉樹來說，用數組表示法是非常浪費空間的。 什麼樣的二叉樹最适合用數組表示呢？ 我們後面即将學到的二叉堆，一種特殊的完全二叉樹，就是用數組來存儲的。
二叉樹的應用
二叉樹包含許多特殊的形式，每一種形式都有自己的作用，但是其最主
要的應用還在于進行查找操作和維持相對順序 這兩個方面。
1. 查找
二叉樹的樹形結構使它很适合扮演索引的角色。 這裡我們介紹一種特殊的二叉樹：二叉查找樹（binary search tree） 。 光看名字就可以知道，這種二叉樹的主要作用就是進行查找操作。
二叉查找樹在二叉樹的基礎上增加了以下幾個條件。
- 如果左子樹不為空，則左子樹上所有節點的值均小于根節點的值
- 如果右子樹不為空，則右子樹上所有節點的值均大于根節點的值
- 左、右子樹也都是二叉查找樹
下圖就是一個标準的二叉查找樹。
二叉查找樹的這些條件有什麼用呢？當然是為了查找友善。
例如查找值為4的節點，步驟如下。
1. 通路根節點6，發現4<6。
2. 通路節點6的左孩子節點3，發現4>3。
3. 通路節點3的右孩子節點4，發現4=4，這正是要查找的節點。
對于一個節點分布相對均衡 的二叉查找樹來說，如果節點總數是n，那 麼搜尋節點的時間複雜度就是O(logn) ，和樹的深度是一樣的。 這種依靠比較大小來逐漸查找的方式，和二分查找算法非常相似。
2. 維持相對順序
這一點仍然要從二叉查找樹說起。二叉查找樹要求左子樹小于父節點，右子樹大于父節點，正是這樣保證了二叉樹的有序性。是以二叉查找樹還有另一個名字——二叉排序樹（binary sort tree） 。
新插入的節點，同樣要遵循二叉排序樹的原則。例如插入新元素5，由 于5<6，5>3，5>4，是以5最終會插入到節點4的右孩子位置。
再如插入新元素10，由于10>6，10>8，10>9，是以10最終會插入到節點9的右孩子位置。
這一切看起來很順利，然而卻隐藏着一個緻命的問題。什麼問題呢？下面請試着在二叉查找樹中依次插入9、8、7、6、5、4，看看會出現什麼
結果。哈哈，好好的一個二叉樹，變成“跛腳”啦！
不隻是外觀看起來變得怪異了，查詢節點的時間複雜度也退化成了O(n)。
怎麼解決這個問題呢？這就涉及二叉樹的自平衡 了。二叉樹自平衡的方式有多種，如紅黑樹、AVL樹、樹堆等。