二叉搜索樹的簡明實現（ES5 & ES6）

01-31

二叉樹 & 二叉搜索樹

二叉樹（Binary Tree）是 n（n >= 0）個節點的有限集合，集合為空集時，叫作空二叉樹；不為空時，由根節點及左子樹、右子樹組成，左子樹、右子樹也都是二叉樹。

從這個描述，可以看出樹的結構與遞歸之間存在密切關係，這種密切關係在樹的遍歷時能夠得到充分體現。

二叉搜索樹（Binary Search Tree），又叫二叉查找樹；也稱為有序二叉樹（Ordered Binary Tree），排序二叉樹（Sorted Binary Tree）。

這是維基百科上歸納的一些二叉搜索樹的性質：

若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
任意節點的左、右子樹也分別為二叉查找樹；
沒有鍵值相等的節點。

本次實現中有點不一樣的地方，右節點是大於或等於父節點的。不過對示例沒有影響，而且很容易改成只能大於父節點。

關於《學習JavaScript數據結構與演算法（第2版）》

當年看過這本書的第一版，最近打算複習一下數據結構與演算法，於是看了第二版。

這是難得的一本用 JavaScript 實現的數據結構與演算法的書，它的講解十分清晰，相對來說質量較高，但問題也有很多。應該說第一版的內容還是比較可靠的，第二版新增的內容可靠性就差了很多。總的來說，這是一本從非常淺顯的層面講解數據結構與演算法的書，想獲得比較全面的知識還是需要閱讀更專業的資料。

本文的 ES5 實現參考了這本書，因為我覺得它是比較工整的實現，用於學習和理解時，好過我看到的其他一些實現方式。在原書示例代碼的基礎上，我做了一些小調整。本書第二版號稱擁抱 ES6，但我看過之後發現至少樹這一章沒有改為 ES6 的實現，於是自己寫了一遍，正好當作練習的機會。

另外，這本書中提到的樹的遍歷方式包括中序、先序、後序遍歷，這些都屬於深度優先遍歷。在本文的代碼中，我補充了廣度優先遍歷以及按照層次遍歷二叉樹的實現。

Binary Search Tree - ES5

Binary Search Tree - ES6

class Node {n constructor(key) {n this.key = key;n this.left = null;n this.right = null;n }n}nn// insert(key):向樹中插入一個新的鍵。n// search(key):在樹中查找一個鍵，如果節點存在，則返回true;如果不存在，則返回false。n// inOrderTraverse:通過中序遍歷方式遍歷所有節點。n// preOrderTraverse:通過先序遍歷方式遍歷所有節點。n// postOrderTraverse:通過後序遍歷方式遍歷所有節點。n// min:返回樹中最小的值/鍵。n// max:返回樹中最大的值/鍵。n// remove(key):從樹中移除某個鍵。nclass BinarySearchTree {nn constructor() {n this.root = null;n }nn static insertNode(node, newNode) {n if (node.key > newNode.key) {n if (node.left === null) {n node.left = newNode;n } else {n BinarySearchTree.insertNode(node.left, newNode);n }n } else {n if (node.right === null) {n node.right = newNode;n } else {n BinarySearchTree.insertNode(node.right, newNode);n }n }n }nn static searchNode(node, key) {n if (node === null) {n return false;n }nn if (node.key === key) {n return true;n } else if (node.key > key) {n BinarySearchTree.searchNode(node.left, key);n } else if (node.key < key) {n BinarySearchTree.searchNode(node.right, key);n }n }nn static inOrderTraverseNode(node, cb) {n if (node === null) {n return;n }n BinarySearchTree.inOrderTraverseNode(node.left, cb);n cb(node.key);n BinarySearchTree.inOrderTraverseNode(node.right, cb);n }nn static preOrderTraverseNode(node, cb) {n if (node === null) {n return;n }n cb(node.key);n BinarySearchTree.preOrderTraverseNode(node.left, cb);n BinarySearchTree.preOrderTraverseNode(node.right, cb);n }nn static postOrderTraverseNode(node, cb) {n if (node === null) {n return;n }n BinarySearchTree.postOrderTraverseNode(node.left, cb);n BinarySearchTree.postOrderTraverseNode(node.right, cb);n cb(node.key);n }nn static levelOrderTraverseNode(node, cb) {n if (node === null) {n return null;n }nn const list = [node];nn while (list.length > 0) {n node = list.shift();n cb(node.key);n if (node.left) {n list.push(node.left);n }n if (node.right) {n list.push(node.right);n }n }n }nn static separateByLevelFn(node, cb, separator = ---*---) {n const list = [];n const END_FLAG = END_FLAG;nn list.push(node);n list.push(END_FLAG);nn while (list.length > 0) {n node = list.shift();nn // 遇到結束信號，表示已經遍歷完一層；若隊列中還有元素，說明它們是剛剛遍歷完的這一層的所有子元素。n if (node === END_FLAG && list.length > 0) {n list.push(END_FLAG);n cb(separator);n } else {n cb(node.key);nn if (node.left) {n list.push(node.left)n }nn if (node.right) {n list.push(node.right);n }n }n }n }nn static removeNode(node, key) {n if (node === null) {n return null;n }nn if (node.key === key) {nn if (node.left === null && node.right === null) {n node = null;n return node;n } else if (node.left === null) {n node = node.right;n return node;n } else if (node.right === null) {n node = node.left;n return node;n } else if (node.left && node.right) {n let rightMinNode = node.right;nn while (rightMinNode.left !== null) {n rightMinNode = rightMinNode.left;n }nn node.key = rightMinNode.key;n node.right = BinarySearchTree.removeNode(node.right, rightMinNode.key);n return node;n }nn } else if (node.key > key) {n node.left = BinarySearchTree.removeNode(node.left, key);n return node;n } else if (node.key < key) {n node.right = BinarySearchTree.removeNode(node.right, key);n return node;n }n }nn static printNode(val) {n console.log(val);n }nn insert(key) {n const newNode = new Node(key);nn if (this.root === null) {n this.root = newNode;n } else {n BinarySearchTree.insertNode(this.root, newNode);n }n }nn search(key) {n return BinarySearchTree.searchNode(key);n }nn // 中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式，也就是以從最小到最大的順序訪n // 問所有節點。中序遍歷的一種應用就是對樹進行排序操作。n inOrderTraverse(cb = BinarySearchTree.printNode) {n BinarySearchTree.inOrderTraverseNode(this.root, cb);n }nn // 先序遍歷是以優先於後代節點的順序訪問每個節點的。先序遍歷的一種應用是列印一個結構化的文檔。n preOrderTraverse(cb = BinarySearchTree.printNode) {n BinarySearchTree.preOrderTraverseNode(this.root, cb);n }nn // 後序遍歷則是先訪問節點的後代節點，再訪問節點本身。後序遍歷的一種應用是計算一個目n // 錄和它的子目錄中所有文件所佔空間的大小。n postOrderTraverse(cb = BinarySearchTree.printNode) {n BinarySearchTree.postOrderTraverseNode(this.root, cb);n }nn // Breadth-First-Searchn // 可以用來解決尋路徑的問題。n levelOrderTraverse(cb = BinarySearchTree.printNode) {n BinarySearchTree.levelOrderTraverseNode(this.root, cb);n }nn // Breadth-First-Searchn // 區分層次n separateByLevel(cb = BinarySearchTree.printNode) {n BinarySearchTree.separateByLevelFn(this.root, cb);n }nn min() {n let node = this.root;nn if (node === null) {n return null;n }nn while (node.left !== null) {n node = node.left;n }nn return node.key;n }nn max() {n let node = this.root;nn if (node === null) {n return null;n }nn while (node.right !== null) {n node = node.right;n }nn return node.key();n }nn remove(key) {n this.root = BinarySearchTree.removeNode(this.root, key);n }n}nnn/* ========== test case ========== */nnnconst tree = new BinarySearchTree();nn/**n *n * 11n * / n * / n * / n * / n * / n * / n * 7 5n * / / n * / / n * 5 9 13 20n * / / / / n * 3 6 8 10 12 14 18 25n *n */ntree.insert(11);ntree.insert(7);ntree.insert(15);ntree.insert(5);ntree.insert(3);ntree.insert(9);ntree.insert(8);ntree.insert(10);ntree.insert(13);ntree.insert(12);ntree.insert(14);ntree.insert(20);ntree.insert(18);ntree.insert(25);ntree.insert(6);nntree.inOrderTraverse();nnconsole.log(n)ntree.levelOrderTraverse();nnconsole.log(n)ntree.separateByLevel();nnconsole.log(n)ntree.remove(7)ntree.inOrderTraverse();nnconsole.log(n)ntree.preOrderTraverse();nnconsole.log(n)ntree.postOrderTraverse();n

二叉搜索樹的簡明實現（ES5 &amp; ES6）

二叉樹 &amp; 二叉搜索樹

關於《學習JavaScript數據結構與演算法（第2版）》

Binary Search Tree - ES5

Binary Search Tree - ES6

二叉搜索樹的簡明實現（ES5 & ES6）

二叉樹 & 二叉搜索樹