在二叉查找树上进行查找
对 BST 通常有下列三种类型的查找：
- 查找给定值；
- 查找最小值；
- 查找最大值。
class BinarySearchTree { ... min() { // 最小值 return this.minNode(this.root); } max() { // 最大值 return this.maxNode(this.root); } search(key) { // 查找 this.searchNode(this.root, key); } minNode(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; } maxNode(node) { if (node) { while (node && node.right !== null) { node = node.right; } return node.key; } return null; } searchNode(node, key) { if (node === null) return false; if (key < node.key) { return this.searchNode(node.left, key); } else if (key > node.key) { return this.searchNode(node.right, key); } else { return true; } } findMinNode(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; } }
从二叉查找树上删除节点
class BinarySearchTree { ... remove(key) { //移除树节点 this.removeNode(this.root, key); } removeNode(node, key) { if (node === null) return null; if (key < node.key) { node.left = this.removeNode(node.left, key); return node; } else if (key > node.key) { node.right = this.removeNode(node.right, key); return node; } else { if (node.left === null && node.right === null) { node = null; return node; } else if (node.left === null) { node = node.right; return node; } else if (node.right === null) { node = node.left; return node; } const aux = this.findMinNode(node.right); node.key = aux.key; node.right = this.removeNode(node.right, aux.key); return node; } } }
完整代码
class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(key) { // 插入 const newNode = new Node(key); if (this.root === null) { this.root = newNode; } else { this.insertNode(this.root, newNode); } console.log(this.root); } inOrderTraverse(callback) { // 中序查找 this.inOrderTraverseNode(this.root, callback); } preOrderTraverse(callback) { // 先序查找 this.preOrderTraverseNode(this.root, callback); } postOrderTraverse(callback) { // 后序查找 this.postOrderTraverseNode(this.root, callback); } min() { // 最小值 return this.minNode(this.root); } max() { // 最大值 return this.maxNode(this.root); } search(key) { // 查找 this.searchNode(this.root, key); } remove(key) { //移除树节点 this.removeNode(this.root, key); } insertNode(node, newNode) { if (newNode.key < node.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); } } } inOrderTraverseNode(node, callback) { if (node !== null) { this.inOrderTraverseNode(node.left, callback); callback(node.key); this.inOrderTraverseNode(node.right, callback); } } preOrderTraverseNode(node, callback) { if (node !== null) { callback(node.key); this.preOrderTraverseNode(node.left, callback); this.preOrderTraverseNode(node.right, callback); } } postOrderTraverseNode(node, callback) { if (node !== null) { this.postOrderTraverseNode(node.left, callback); this.postOrderTraverseNode(node.right, callback); callback(node.key); } } minNode(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; } maxNode(node) { if (node) { while (node && node.right !== null) { node = node.right; } return node.key; } return null; } searchNode(node, key) { if (node === null) return false; if (key < node.key) { return this.searchNode(node.left, key); } else if (key > node.key) { return this.searchNode(node.right, key); } else { return true; } } removeNode(node, key) { if (node === null) return null; if (key < node.key) { node.left = this.removeNode(node.left, key); return node; } else if (key > node.key) { node.right = this.removeNode(node.right, key); return node; } else { if (node.left === null && node.right === null) { node = null; return node; } else if (node.left === null) { node = node.right; return node; } else if (node.right === null) { node = node.left; return node; } const aux = this.findMinNode(node.right); node.key = aux.key; node.right = this.removeNode(node.right, aux.key); return node; } } findMinNode(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; } }
参考书籍
数据结构与算法JavaScript描述
