二叉搜尋樹(Binary Search Tree)顧名思義,每個節點最多只有左右兩個分支,且左子節點的值必定小於右子節點的值。這個特性讓插入節點、尋找最大/最小值、以及排序輸出都變得非常直覺——只要做一次中序遍歷,就能得到由小到大的有序序列。
以下用 JavaScript 完整實作節點類別與樹的操作,包含插入、最小值、最大值,以及中序、先序、後序三種遍歷。
<script type="text/javascript">
// 簡單的輸出函式
function println(msg) {
document.write(msg + " ");
}
// 節點類別
var Node = function (v) {
this.data = v; // 節點值
this.left = null; // 左節點
this.right = null; // 右節點
};
// 二叉搜尋樹類別
var BinarySearchTree = function () {
this.root = null; // 初始化時根節點為空
// 插入節點,參數 v 為節點值
this.insert = function (v) {
var newNode = new Node(v);
if (this.root == null) { // 樹為空時,新節點直接成為根
this.root = newNode;
return;
}
var currentNode = this.root; // 工作指針,從根往下找
var parentNode = null;
while (true) {
parentNode = currentNode;
if (v < currentNode.data) { // 比當前節點小,往左走
currentNode = currentNode.left;
if (currentNode == null) {
parentNode.left = newNode;
return;
}
} else { // 否則往右走
currentNode = currentNode.right;
if (currentNode == null) {
parentNode.right = newNode;
return;
}
}
}
};
// 尋找最小節點:一路往左到底
this.min = function () {
var p = this.root;
while (p != null && p.left != null) { p = p.left; }
return p;
};
// 尋找最大節點:一路往右到底
this.max = function () {
var p = this.root;
while (p != null && p.right != null) { p = p.right; }
return p;
};
// 中序遍歷:左 → 根 → 右(結果為遞增序列)
this.inOrder = function (rootNode) {
if (rootNode != null) {
this.inOrder(rootNode.left);
println(rootNode.data);
this.inOrder(rootNode.right);
}
};
// 先序遍歷:根 → 左 → 右
this.preOrder = function (rootNode) {
if (rootNode != null) {
println(rootNode.data);
this.preOrder(rootNode.left);
this.preOrder(rootNode.right);
}
};
// 後序遍歷:左 → 右 → 根
this.postOrder = function (rootNode) {
if (rootNode != null) {
this.postOrder(rootNode.left);
this.postOrder(rootNode.right);
println(rootNode.data);
}
};
};
// 測試
var bTree = new BinarySearchTree();
bTree.insert(6);
bTree.insert(3);
bTree.insert(8);
bTree.insert(1);
bTree.insert(4);
bTree.insert(9);
println('中序遍歷:'); bTree.inOrder(bTree.root); println("<br/>");
println("先序遍歷:"); bTree.preOrder(bTree.root); println("<br/>");
println("後序遍歷:"); bTree.postOrder(bTree.root); println("<br/>");
var minNode = bTree.min();
println("最小節點:" + (minNode == null ? "不存在" : minNode.data));
println("<br/>");
var maxNode = bTree.max();
println("最大節點:" + (maxNode == null ? "不存在" : maxNode.data));
// ]]>
</script>
實際輸出結果:
中序遍歷: 1 3 4 6 8 9 先序遍歷: 6 3 1 4 8 9 後序遍歷: 1 4 3 9 8 6 最小節點:1 最大節點:9
從輸出可以驗證:中序遍歷的結果正好是升冪排序,這也是搜尋樹最實用的性質之一。另外要留意,以上是最基礎的版本,沒有做平衡處理;當插入資料本身已接近有序時,樹會退化成一條鏈表,查詢複雜度從 O(log n) 掉到 O(n)。若要在 production 環境使用,建議進一步實作 AVL 樹或紅黑樹,並補上刪除節點的操作。