首页 > 代码库 > JavaScript 二叉树搜索
JavaScript 二叉树搜索
TypeScript方式实现源码
1 // 二叉树与二叉树搜索 2 class Node { 3 key; 4 left; 5 right; 6 constructor(key) { 7 this.key = key; 8 this.left = null; 9 this.right = null; 10 } 11 } 12 class BinarySearchTree { 13 root = null; 14 public insert(key) { 15 let newNode = new Node(key); 16 17 if (this.root === null) { 18 this.root = newNode; 19 } else { 20 this.insertNode(this.root, newNode); 21 } 22 } 23 private insertNode(node, newNode) { 24 if (newNode.key < node.key) { 25 if (node.left === null) { 26 node.left = newNode; 27 } else { 28 this.insertNode(node.left, newNode); 29 } 30 } else { 31 if (node.right === null) { 32 node.right = newNode; 33 } else { 34 this.insertNode(node.right, newNode); 35 } 36 } 37 } 38 public search(key) { 39 return this.searchNode(this.root, key); 40 } 41 private searchNode(node, key) { 42 if (node === null) { 43 return false; 44 } 45 if (key < node.key) { 46 return this.searchNode(node.left, key); 47 } else if (key > node.key) { 48 return this.searchNode(node.right, key); 49 } else { 50 return true; 51 } 52 } 53 /** 54 * 中序遍历 55 */ 56 public inOrderTraverse(callback) { 57 this.inOrderTraverseNode(this.root, callback); 58 } 59 private inOrderTraverseNode(node, callback) { 60 if (node !== null) { 61 this.inOrderTraverseNode(node.left, callback); 62 callback(node.key); 63 this.inOrderTraverseNode(node.right, callback); 64 } 65 } 66 /** 67 * 先序遍历 68 */ 69 public preOrderTraverse(callback) { 70 this.preOrderTraverseNode(this.root, callback) 71 } 72 private preOrderTraverseNode(node, callback) { 73 if (node !== null) { 74 callback(node.key); 75 this.preOrderTraverseNode(node.left, callback); 76 this.preOrderTraverseNode(node.right, callback); 77 } 78 } 79 /** 80 * 后序遍历 81 */ 82 public postOrderTraverse(callback) { 83 this.postOrderTranverseNode(this.root, callback) 84 } 85 private postOrderTranverseNode(node, callback) { 86 if (node !== null) { 87 this.postOrderTranverseNode(node.left, callback); 88 this.postOrderTranverseNode(node.right, callback); 89 callback(node.key); 90 } 91 } 92 public min() { 93 94 } 95 private minNode(node) { 96 if (node) { 97 while (node && node.left !== null) { 98 node = node.left; 99 } 100 return node.key; 101 } 102 return null; 103 } 104 public max(node) { 105 if (node) { 106 while (node && node.right !== null) { 107 node = node.right; 108 } 109 return node.key; 110 } 111 return null; 112 } 113 public remove(key) { 114 this.root = this.removeNode(this.root, key); 115 } 116 private removeNode(node, key) { 117 if (node === null) { 118 return null; 119 } 120 if (key < node.key) { 121 node.left = this.removeNode(node.left, key); 122 return node; 123 } else if (key > node.key) { 124 node.right = this.removeNode(node.right, key); 125 return node; 126 } else { // 建等于node.key 127 // 第一种情况——一个叶节点 128 if (node.left === null && node.right === null) { 129 node = null; 130 return node; 131 } 132 133 // 第二种情况——一个只有一个子节点的节点 134 if (node.left === null) { 135 node = node.right; 136 return node; 137 } else if (node.right === null) { 138 node = node.left; 139 return node; 140 } 141 142 // 第三种情况——一个只有两个子节点的节点 143 let aux = findMinNode(node.right); 144 node.key = aux.key; 145 node.right = this.removeNode(node.right, aux.key); 146 return node; 147 } 148 } 149 } 150 function printNode(value) { 151 console.log(value); 152 } 153 let tree = new BinarySearchTree(); 154 tree.insert(11); 155 tree.insert(7); 156 tree.insert(15); 157 tree.insert(5); 158 tree.insert(3); 159 tree.insert(9); 160 tree.insert(8); 161 tree.insert(10); 162 163 tree.insert(13); 164 tree.insert(12); 165 tree.insert(14); 166 tree.insert(20); 167 tree.insert(18); 168 tree.insert(25); 169 tree.insert(6); 170 171 // tree.inOrderTraverse(printNode); 172 // tree.preOrderTraverse(printNode); 173 tree.postOrderTraverse(printNode); 174 175 console.log(tree.search(1) ? ‘Key 1 found.‘ : ‘Key 1 not found.‘); 176 console.log(tree.search(8) ? ‘Key 8 found.‘ : ‘Key 8 not found.‘);
JavaScript方式实现源码
1 // 二叉树与二叉树搜索 2 var Node = (function () { 3 function Node(key) { 4 this.key = key; 5 this.left = null; 6 this.right = null; 7 } 8 return Node; 9 }()); 10 var BinarySearchTree = (function () { 11 function BinarySearchTree() { 12 this.root = null; 13 } 14 BinarySearchTree.prototype.insert = function (key) { 15 var newNode = new Node(key); 16 if (this.root === null) { 17 this.root = newNode; 18 } 19 else { 20 this.insertNode(this.root, newNode); 21 } 22 }; 23 BinarySearchTree.prototype.insertNode = function (node, newNode) { 24 if (newNode.key < node.key) { 25 if (node.left === null) { 26 node.left = newNode; 27 } 28 else { 29 this.insertNode(node.left, newNode); 30 } 31 } 32 else { 33 if (node.right === null) { 34 node.right = newNode; 35 } 36 else { 37 this.insertNode(node.right, newNode); 38 } 39 } 40 }; 41 BinarySearchTree.prototype.search = function (key) { 42 return this.searchNode(this.root, key); 43 }; 44 BinarySearchTree.prototype.searchNode = function (node, key) { 45 if (node === null) { 46 return false; 47 } 48 if (key < node.key) { 49 return this.searchNode(node.left, key); 50 } 51 else if (key > node.key) { 52 return this.searchNode(node.right, key); 53 } 54 else { 55 return true; 56 } 57 }; 58 /** 59 * 中序遍历 60 */ 61 BinarySearchTree.prototype.inOrderTraverse = function (callback) { 62 this.inOrderTraverseNode(this.root, callback); 63 }; 64 BinarySearchTree.prototype.inOrderTraverseNode = function (node, callback) { 65 if (node !== null) { 66 this.inOrderTraverseNode(node.left, callback); 67 callback(node.key); 68 this.inOrderTraverseNode(node.right, callback); 69 } 70 }; 71 /** 72 * 先序遍历 73 */ 74 BinarySearchTree.prototype.preOrderTraverse = function (callback) { 75 this.preOrderTraverseNode(this.root, callback); 76 }; 77 BinarySearchTree.prototype.preOrderTraverseNode = function (node, callback) { 78 if (node !== null) { 79 callback(node.key); 80 this.preOrderTraverseNode(node.left, callback); 81 this.preOrderTraverseNode(node.right, callback); 82 } 83 }; 84 /** 85 * 后序遍历 86 */ 87 BinarySearchTree.prototype.postOrderTraverse = function (callback) { 88 this.postOrderTranverseNode(this.root, callback); 89 }; 90 BinarySearchTree.prototype.postOrderTranverseNode = function (node, callback) { 91 if (node !== null) { 92 this.postOrderTranverseNode(node.left, callback); 93 this.postOrderTranverseNode(node.right, callback); 94 callback(node.key); 95 } 96 }; 97 BinarySearchTree.prototype.min = function () { 98 }; 99 BinarySearchTree.prototype.minNode = function (node) { 100 if (node) { 101 while (node && node.left !== null) { 102 node = node.left; 103 } 104 return node.key; 105 } 106 return null; 107 }; 108 BinarySearchTree.prototype.max = function (node) { 109 if (node) { 110 while (node && node.right !== null) { 111 node = node.right; 112 } 113 return node.key; 114 } 115 return null; 116 }; 117 BinarySearchTree.prototype.remove = function (key) { 118 this.root = this.removeNode(this.root, key); 119 }; 120 BinarySearchTree.prototype.removeNode = function (node, key) { 121 if (node === null) { 122 return null; 123 } 124 if (key < node.key) { 125 node.left = this.removeNode(node.left, key); 126 return node; 127 } 128 else if (key > node.key) { 129 node.right = this.removeNode(node.right, key); 130 return node; 131 } 132 else { 133 // 第一种情况——一个叶节点 134 if (node.left === null && node.right === null) { 135 node = null; 136 return node; 137 } 138 // 第二种情况——一个只有一个子节点的节点 139 if (node.left === null) { 140 node = node.right; 141 return node; 142 } 143 else if (node.right === null) { 144 node = node.left; 145 return node; 146 } 147 // 第三种情况——一个只有两个子节点的节点 148 var aux = findMinNode(node.right); 149 node.key = aux.key; 150 node.right = this.removeNode(node.right, aux.key); 151 return node; 152 } 153 }; 154 return BinarySearchTree; 155 }()); 156 function printNode(value) { 157 console.log(value); 158 } 159 var tree = new BinarySearchTree(); 160 tree.insert(11); 161 tree.insert(7); 162 tree.insert(15); 163 tree.insert(5); 164 tree.insert(3); 165 tree.insert(9); 166 tree.insert(8); 167 tree.insert(10); 168 tree.insert(13); 169 tree.insert(12); 170 tree.insert(14); 171 tree.insert(20); 172 tree.insert(18); 173 tree.insert(25); 174 tree.insert(6); 175 // tree.inOrderTraverse(printNode); 176 // tree.preOrderTraverse(printNode); 177 tree.postOrderTraverse(printNode); 178 console.log(tree.search(1) ? ‘Key 1 found.‘ : ‘Key 1 not found.‘); 179 console.log(tree.search(8) ? ‘Key 8 found.‘ : ‘Key 8 not found.‘);
JavaScript 二叉树搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。