在 Javascript 二叉搜索树中搜索值
web developmentfront end technologyjavascript
我们将使用 BST 的属性来查找其中的元素。我们先来看一个搜索减法的迭代实现
示例
searchIter(data) {
let currNode = this.root;
while (currNode !== null) {
if (currNode.data === data) {
// 找到了元素!
return true;
} else if (data < currNode.data) {
// 由于数据小于父节点，因此向左移动
currNode = currNode.left;
} else {
// 由于数据大于父节点，因此向右移动
currNode = currNode.right;
}
}
return false;
}
在此函数中，我们从根节点作为 currNode 开始，并检查我们的数据与 currNode 的数据进行比较。如果我们找到匹配项，则返回 true，否则我们根据数据与 currNode 数据的关系继续向左或向右迭代，直到我们到达叶子节点或找到我们的元素。
您可以使用以下方法进行测试 −
示例
let BST = new BinarySearchTree(); BST.insertIter(10); BST.insertIter(15); BST.insertIter(5); BST.insertIter(50); BST.insertIter(3); BST.insertIter(7); BST.insertIter(12); console.log(BST.searchIter(2)); console.log(BST.searchIter(12)); console.log(BST.searchIter(50)); console.log(BST.searchIter(-22)); console.log(BST.searchIter(200));
输出
这将给出输出 −
false true true false false
与插入函数类似，搜索也可以递归实现。
searchRec(data) {
return searchRecHelper(data, this.root);
}
同样，我们需要创建一个辅助函数，我们不想让它成为类的一部分，所以我们将在类定义之外创建这个函数 −
示例
function searchRecHelper(data, root) {
if (root === null) {
// Reached leaf but didn't find it.
return false;
}
if (data < root.data) {
return searchRecHelper(data, root.left);
} else if (data > root.data) {
return searchRecHelper(data, root.right);
}
// This means element is found
return true;
}
您可以使用以下方法进行测试 −
示例
let BST = new BinarySearchTree(); BST.insertRec(10); BST.insertRec(15); BST.insertRec(5); BST.insertRec(50); BST.insertRec(3); BST.insertRec(7); BST.insertRec(12); console.log(BST.searchRec(2)); console.log(BST.searchRec(12)); console.log(BST.searchRec(50)); console.log(BST.searchRec(-22)); console.log(BST.searchRec(200));
输出
这将给出输出 −
false true true false false
