二元樹為 n (n≥0) 節點有限集:或為空樹,或由根節點 + 左右兩棵互不相交的二元樹組成。每節點度 ≤ 2,嚴格區分左/右子樹。
function isCompleteTree(root) {
if (!root) return true;
var queue = [root];
var encounteredNull = false;
while (queue.length) {
var node = queue.shift();
if (!node) {
encounteredNull = true;
} else {
if (encounteredNull) return false; // 出現 null 後又有節點 → 不完全
queue.push(node.left);
queue.push(node.right);
}
}
return true;
}
function Node(data, left, right) {
this.data = data;
this.left = left || null;
this.right = right || null;
}
Node.prototype.show = function() { return this.data; };
// 前序:根 → 左 → 右
function preOrder(node) {
if (!node) return;
console.log(node.show());
preOrder(node.left);
preOrder(node.right);
}
// 中序:左 → 根 → 右
function inOrder(node) {
if (!node) return;
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
// 後序:左 → 右 → 根
function postOrder(node) {
if (!node) return;
postOrder(node.left);
postOrder(node.right);
console.log(node.show());
}
function BST() {
this.root = null;
}
BST.prototype.insert = function(data) {
var n = new Node(data);
if (!this.root) { this.root = n; return; }
var current = this.root;
while (true) {
if (data < current.data) {
if (!current.left) { current.left = n; return; }
current = current.left;
} else {
if (!current.right) { current.right = n; return; }
current = current.right;
}
}
};
BST.prototype.getMin = function() {
var current = this.root;
while (current.left) current = current.left;
return current.data;
};
BST.prototype.getMax = function() {
var current = this.root;
while (current.right) current = current.right;
return current.data;
};
BST.prototype.find = function(data) {
var current = this.root;
while (current) {
if (data === current.data) return current;
current = data < current.data ? current.left : current.right;
}
return null;
};
// 中序遍歷即可得到排序序列
BST.prototype.inOrderTraverse = function(callback) {
function traverse(node) {
if (!node) return;
traverse(node.left);
callback(node);
traverse(node.right);
}
traverse(this.root);
};
BST.prototype.remove = function(data) {
this.root = removeNode(this.root, data);
};
function removeNode(node, data) {
if (!node) return null;
if (data < node.data) {
node.left = removeNode(node.left, data);
return node;
} else if (data > node.data) {
node.right = removeNode(node.right, data);
return node;
} else { // 找到目標
// 情況 1:葉子
if (!node.left && !node.right) return null;
// 情況 2:單一子節點
if (!node.left) return node.right;
if (!node.right) return node.left;
// 情況 3:雙子節點
var minRight = getMinNode(node.right);
node.data = minRight.data;
node.right = removeNode(node.right, minRight.data);
return node;
}
}
function getMinNode(node) {
while (node.left) node = node.left;
return node;
}
二元樹是無數進階資料結構(紅黑樹、AVL、B-Tree、Trie、堆)的基石。熟練實作 BST 的增刪查與三種遍歷,並理解完全二元樹判斷邏輯,是演算法面試與高效能索引設計的必修課。