function BinarySearchTree() { this.root = null; this.count = 0; // 内部类 存放节点的信息 function Node(key) { this.key = key; this.left = null; this.right = null; } // insert 对外用户插入方法 BinarySearchTree.prototype.insert = function (key) { // 创建一个新节点 let newNode = new Node(key); // 判断是否存在根节点 if (this.root == null) { this.root = newNode; } else { this.insertNode(this.root, newNode); } this.count++ } // insertNode 内部插入节点方法 递归比较直到找到合适的位置 BinarySearchTree.prototype.insertNode = function (node, newNode) { if (node.key > newNode.key) { if (node.left == null) { node.left = newNode; } else { this.insertNode(node.left, newNode) } } else { if (node.right == null) { node.right = newNode; } else { this.insertNode(node.right, newNode) } } } // preOrderTravelsal 先序遍历 BinarySearchTree.prototype.preOrderTravelsal = function (handler) { this.preOrderTravelsalNode(this.root, handler); } // preOrderTravelsalNode 根节点->left->right BinarySearchTree.prototype.preOrderTravelsalNode = function (node, handler) { if (node != null) { handler(node.key) this.preOrderTravelsalNode(node.left, handler); this.preOrderTravelsalNode(node.right, handler); } } // centerOrderTravelsal 中序遍历 BinarySearchTree.prototype.midOrderTravelsal = function (handler) { this.midOrderTravelsalNode(this.root, handler) } // centerOrderTravelsalNode left->根节点->right BinarySearchTree.prototype.midOrderTravelsalNode = function (node, handler) { if (node != null) { this.midOrderTravelsalNode(node.left, handler) handler(node.key); this.midOrderTravelsalNode(node.right, handler) } } // afterOrderTravelsalNode 后序遍历 BinarySearchTree.prototype.postOrderTravelsal = function (handler) { this.postOrderTravelsalNode(this.root, handler) } // afterOrderTravelsalNode left->right->root BinarySearchTree.prototype.postOrderTravelsalNode = function (node, handler) { if (node != null) { this.postOrderTravelsalNode(node.left, handler); this.postOrderTravelsalNode(node.right, handler); handler(node.key) } } // 查找最小值 BinarySearchTree.prototype.min = function () { if (this.root == null) return null; let node = this.root; while (node.left != null) { node = node.left } return node.key } // 查找最大值 BinarySearchTree.prototype.max = function () { if (this.root == null) return null; let node = this.root; while (node.right != null) { node = node.right } return node.key } // 查找特定值 BinarySearchTree.prototype.search = function (key) { let node = this.root; while (node != null) { if (node.key < key) { node = node.right } else if (node.key > key) { node = node.left } else { return true } } return false } // remove 删除节点 BinarySearchTree.prototype.remove = function (key) { if (this.root == null) return false; // 定义一些需要用到的属性 let current = this.root; let parent = null; let isLeftChild = false; // 1.先找到要删除的节点 while (current.key != key) { parent = current; if (current.key > key) { isLeftChild = true; current = current.left; } else { isLeftChild = false; current = current.right; } // 没找到节点 if (current == null) return false } // 2.找到节点，判断情况处理 // 2.1 叶子节点 if (current.left == null && current.right == null) { if (current == this.root) { this.root = null } else if (isLeftChild) { parent.left = null } else { parent.right = null } return true } // 2.2 只有一个子节点 if (current.left == null || current.right == null) { if (current == this.root) { this.root = current.left || current.right } else if (isLeftChild) { parent.left = current.left || current.right } else { parent.right = current.left || current.right } return true } // 2.3 有两个子节点 // 2.3.1 找到后继 let succssor = this.getSuccssor(current); // 2.3.2 情况处理 if (current == this.root) { this.root = succssor } else if (isLeftChild) { parent.left = succssor } else { parent.right = succssor } succssor.left = current.left; return true } // 找删除节点的后继(比删除节点稍微大一点点的节点) BinarySearchTree.prototype.getSuccssor = function (delNode) { // 定义一些需要用到的属性 let succssor = delNode.right; let parent = delNode; // 循环找后继 while (succssor.left != null) { parent = succssor; succssor = succssor.left } // 找到后继，情况处理 if (succssor != delNode.right) { parent.left = succssor.right; succssor.right = delNode.right; } return succssor } } // -----------------测试----------------- let bst = new BinarySearchTree(); // 插入节点 bst.insert(6) bst.insert(5) bst.insert(8) bst.insert(9) bst.insert(2) bst.insert(4) bst.insert(7) bst.insert(1) bst.insert(3) // console.log(bst); // 先序遍历 var str = ''; bst.preOrderTravelsal((key) => { str += key + ' ' }) console.log(str); // 中序遍历 str = ''; bst.midOrderTravelsal((key) => { str += key + ' ' }) console.log(str); // 后序遍历 str = ''; bst.postOrderTravelsal((key) => { str += key + ' ' }) console.log(str); // 最小值 // console.log(bst.min()); // 最大值 // console.log(bst.max()); // 特定值 // console.log(bst.search(3)); // console.log(bst.search(10)); // 删除节点 console.log(bst.remove(9)); // console.log(bst.remove(10)); // console.log(bst.search(4)); str = ''; bst.postOrderTravelsal((key) => { str += key + ' ' }) console.log(str);