二叉樹(Binary Tree)本質上是一種受限的樹形結構:它由 n(n ≥ 0)個結點組成,當 n 等於 0 時是一棵空樹;否則它由一個根結點,以及分別挂在根結點下的左子樹與右子樹構成,而這兩棵子樹本身也必須是二叉樹。這個定義是遞歸的,理解這一點,後面所有遍歷與操作都會變得自然。

二叉樹最直觀的約束是:每個結點最多只能有兩棵子樹,也就是說整棵樹中不存在度大於 2 的結點。左右子樹的位置是有順序的,不能隨意調換,這是二叉樹和普通樹最大的差別。
在程式實現層面,每一個結點通常被建模為一個物件,並持有三個引用:一個指向父結點,另外兩個分別指向左孩子與右孩子。結點之間靠這些引用互相串聯,凡是彼此相連的兩個結點,都構成父子關係。
以 C 語言風格描述,一個二叉樹結點可以這樣定義:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
其中 m_nValue 存放數據,m_pLeft 與 m_pRight 分別保存左右孩子的位址。若改用 JavaScript 實現,把指標換成物件引用即可。
二叉樹在形態上可以歸納為五種:空樹;只有一個根結點;根結點只有左子樹;根結點只有右子樹;根結點同時擁有左右子樹。

如果只考慮「有幾層」,含三個結點的普通樹不過兩三種擺法;但二叉樹要嚴格區分左右,同樣三個結點就會衍生出五種形態。

如上圖倒數第二張圖中的第 2、3 小圖所示,所有結點都只有單側孩子,整棵樹「歪」向一邊,退化成了類似鏈表的結構。
如果一棵二叉樹的每個分支結點都同時具備左子樹和右子樹,並且所有葉子結點都集中在同一層上,這樣的樹稱為滿二叉樹。此時深度為 k 的滿二叉樹恰好擁有 2 的 k 次方減 1 個結點,一個位置都不浪費。

完全二叉樹的要求比滿二叉樹寬鬆:除最後一層外,其餘各層必須排滿,而最後一層的結點則從左到右連續排列,右側允許留有空位。也就是說,深度為 k 的完全二叉樹,結點數介於 2 的 k-1 次方與 2 的 k 次方減 1 之間。
它有幾個容易驗證的性質:
葉子結點只可能出現在最後一層和倒數第二层;最後一層的葉子一定集中在左部的連續位置;倒數第二层若存在葉子結點,則必定集中在右部的連續位置;若某結點的度為 1,那麼它只會有左孩子而沒有右孩子;在結點總數相同的所有二叉樹中,完全二叉樹的深度最小。

需要牢記的關係是:滿二叉樹一定是完全二叉樹,反之則不成立。
判斷一棵樹是否為完全二叉樹,最經典的做法是層序遍歷:
bool is_complete(tree *root)
{
queue q;
tree *ptr;
// 進行廣度優先遍歷(層次遍歷),並把 NULL 節點也放入隊列
q.push(root);
while ((ptr = q.pop()) != NULL)
{
q.push(ptr->left);
q.push(ptr->right);
}
// 判斷是否還有未被訪問到的節點
while (!q.is_empty())
{
ptr = q.pop();
// 若 NULL 之後還出現非 NULL 節點,說明樹中存在空洞,不是完全二叉樹
if (NULL != ptr)
{
return false;
}
}
return true;
}
思路很直白:把空節點也一起入列,如果一個空節點後面還跟著非空節點,說明中間斷了層,自然不是完全二叉樹。
性質一:第 i 層上至多有 2 的 (i-1) 次方個結點(i ≥ 1)。
性質二:深度為 k 的二叉樹至多有 2 的 k 次方減 1 個結點(k ≥ 1)。
此外還有一條常用結論:若用 n0 表示葉子結點數、n2 表示度為 2 的結點數,則恆有 n0 = n2 + 1。
順序存儲就是用一維陣列把二叉樹的結點依次擺放,並靠下標的計算關係來表達父子之間的邏輯聯繫。對於完全二叉樹,這種方式非常緊湊;但一旦樹中出現大量空洞,陣列就會浪費大量空間,適用性明顯下降。

既然順序結構不夠靈活,工程實踐中更常採用鏈式存儲。二叉樹每個結點最多兩個孩子,因此為它設計一個數據域加兩個指標域是最自然的方案,這樣得到的鏈表稱為二叉鏈表。

遍歷(Traversing Binary Tree)指的是從根結點出發,按照某種約定的次序訪問樹中每一個結點,且每個結點僅被訪問一次。二叉樹有三種基本遍歷方式:
前序遍歷(DLR):先訪問根結點,再遍歷左子樹,最後遍歷右子樹,簡記為「根—左—右」。
中序遍歷(LDR):先遍歷左子樹,再訪問根結點,最後遍歷右子樹,簡記為「左—根—右」。
後序遍歷(LRD):先遍歷左子樹,再遍歷右子樹,最後訪問根結點,簡記為「左—右—根」。
若樹為空則直接返回,否則先輸出根結點,再遞歸前序遍歷左子樹與右子樹。遍歷結果為:A B D H I E J C F K G。
//前序遍歷
function preOrder(node){
if(node != null){
putStr(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}
若樹為空則返回,否則從根結點開始,但並不先輸出它,而是先遞歸中序遍歷左子樹,然後訪問根結點,最後中序遍歷右子樹。

遍歷結果為:H D I B E J A F K C G。
//使用遞歸方式實現中序遍歷
function inOrder(node){
if(!(node == null)){
inOrder(node.left);//先訪問左子樹
putStr(node.show() + " ");//再訪問根結點
inOrder(node.right);//最後訪問右子樹
}
}
若樹為空則返回,否則先遍歷左子樹,再遍歷右子樹,最後才訪問根結點,整體呈現「先葉子後結點」的特徵。

遍歷結果為:H I D J E B K F G C A。
//後序遍歷
function postOrder(node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show() + " ");
}
}
二叉查找樹是一種有附加約束的二叉樹:對任意結點而言,其左子樹上所有結點的值都小於它,右子樹上所有結點的值都大於它。正因這種有序性,查找、插入、求極值等操作都能沿著單一分支快速逼近目標。
先定義結點結構:
function Node(data, left, right){
this.data = data;
this.left = left; //保存左子節點鏈接
this.right = right;
this.show = show;
}
function show(){
return this.data; //顯示保存在節點中的數據
}
由於左子樹恆小於當前結點、右子樹恆大於當前結點,求最小值的過程就是一路向左走到不能再走;求最大值則一路向右。
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}
當某個結點滿足 current.left == null 時,它就是整棵樹最左端的結點,其 data 即為最小值。
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}
同理,最右端結點上保存的值就是最大值。這兩個操作的時間複雜度取決於樹高,在理想情況下為 O(log n),若樹退化為斜樹則退化為 O(n)。