二元樹是資料結構中極為重要的一環,無論是排序、搜尋還是表達式的解析,都離不開它。本文將從二元樹的基本概念出發,逐步介紹它的形態分類、儲存結構、遍歷方式,最後以二元搜尋樹(BST)的實作收尾,幫助你建立完整的知識體系。
二元樹(Binary Tree)是由 n(n ≥ 0)個結點組成的有限集合。這個集合要麼是空集(即空二元樹),要麼由一個根結點,加上兩棵互不相交、分別稱為左子樹與右子樹的二元樹組成。

每個結點最多擁有兩棵子樹,因此二元樹中不存在度數大於 2 的結點。每一個節點都是一個物件,通常具備三個指標,分別指向父母、左孩子與右孩子。所有節點透過指標彼此相連,而這些相連的關係都是父子關係。
以結構化的方式來看,二元樹節點可以定義如下:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
雖然擁有相同數量結點的普通樹型態有限,但由於二元樹需要區分左右,因此會衍生出五種基本形態:


所有結點都只有單一子樹,整體偏向一側,形狀猶如斜坡。
如果一棵二元樹的所有分支結點都同時擁有左子樹與右子樹,且所有葉子都分佈在同一層上,這樣的二元樹就稱為滿二元樹。

完全二元樹是指最後一層左側是填滿的,右側可能填滿也可能未填滿,而其餘各層都是填滿的。一棵深度為 k、節點數量為 2^k − 1 的二元樹即為滿二元樹。完全二元樹具備以下特點:

請注意:滿二元樹一定是完全二元樹,但完全二元樹不一定是滿二元樹。判斷一棵樹是否為完全二元樹,可以透過廣度優先遍歷並把 NULL 節點也放入佇列來實作:
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 節點,則樹存在空洞,為非完全二元樹
if (NULL != ptr)
{
return false;
}
}
return true;
}
順序儲存結構使用一維陣列來存放二元樹的各個結點,並讓結點的存放位置能反映結點之間的邏輯關係。

由於順序儲存的適用性不強,實務上通常採用鏈式儲存。二元樹每個結點最多有兩個孩子,因此為它設計一個資料域與兩個指標域是很自然的做法,我們稱這樣的鏈表為「二叉鏈表」。

二元樹的遍歷(traversing binary tree)是指從根結點出發,按照某種次序依次拜訪所有結點,使得每個結點被拜訪一次且仅一次。常見的遍歷方式有三種:
若二元樹為空則返回,否則先拜訪根結點,再前序遍歷左子樹,最後前序遍歷右子樹。遍歷順序為: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() + " ");
}
}
二元搜尋樹由節點組成,我們先定義一個 Node 節點物件:
function Node(data, left, right){
this.data = data;
this.left = left; // 保存 left 節點連結
this.right = right;
this.show = show;
}
function show(){
return this.data; // 顯示保存在節點中的資料
}
在 BST 上查找最小值非常簡單,因為較小的值總是位於左子節點。只需沿著左子樹不斷往下走,直到找到最後一個節點即可。
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}
當遍歷到 BST 最左側的節點(即 current.left == null)時,該節點上保存的值就是最小值。
同理,查找最大值只需沿著右子樹不斷往下走,直到最後一個節點,該節點保存的值即為最大值。
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}