二叉樹是資料結構中非常基礎且重要的主題。它由節點與分支組成,每個節點最多擁有兩個子節點,分別稱為左子樹與右子樹。二叉樹廣泛應用於表達式解析、搜尋結構、排序演算法與檔案系統等場景。
二叉樹是 n 個節點的有限集合。這個集合可能為空,也可能由一個根節點,以及左右兩棵互不相交的二叉樹組成。
以結構化方式表示時,二叉樹節點通常包含資料與左右子節點參考:
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
在 JavaScript 中,也可以用物件來表示節點:
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
二叉樹可以呈現多種形態,基本可概括為:
若所有節點都只有左子樹或都只有右子樹,會形成類似鏈表狀的斜樹。
若二叉樹中每個分支節點都有左右子樹,且所有葉節點都在同一層,則稱為滿二叉樹。
完全二叉樹是指除了最後一層之外,其他層都是滿的,且最後一層的葉節點集中在左側連續位置。
完全二叉樹的特性包括:
二叉樹有兩個重要性質:
順序儲存結構使用一維陣列來存放二叉樹節點,並透過索引位置來表示節點之間的關係。
由於順序儲存對非完全二叉樹較不友善,實務上更常使用鏈式儲存。每個節點包含資料域、左子節點指標與右子節點指標。
遍歷是指按照某種順序訪問二叉樹中的所有節點,且每個節點只被訪問一次。常見方式有三種:
// 前序遍歷
function preOrder(node) {
if (node) {
putstr(node.show() + ' ');
preOrder(node.left);
preOrder(node.right);
}
}
// 中序遍歷
function inOrder(node) {
if (node) {
inOrder(node.left);
putstr(node.show() + ' ');
inOrder(node.right);
}
}
// 後序遍歷
function postOrder(node) {
if (node) {
postOrder(node.left);
postOrder(node.right);
putstr(node.show() + ' ');
}
}
二叉查找樹,又稱 BST,是一種特殊的二叉樹。它要求左子樹上的所有節點值小於根節點,右子樹上的所有節點值大於根節點。這種特性讓搜尋、插入與刪除都能保持較高效率。
在二叉查找樹中,最小值一定位於左子樹最左側,最大值一定位於右子樹最右側。
function getMin() {
var current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.data;
}
function getMax() {
var current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.data;
}
二叉樹是學習資料結構與演算法時不可忽略的基礎主題。從節點定義、儲存方式、遍歷順序,到二叉查找樹的應用,都能幫助我們建立更完整的資料組織能力。理解二叉樹後,再進一步學習平衡樹、堆積與樹狀圖等進階結構,會更加順利。