在Javascript二进制搜索树中搜索值
我们将使用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) {
//到达叶子但没有找到它。
return false;
}
if (data < root.data) {
return searchRecHelper(data, root.left);
} else if (data > root.data) {
return searchRecHelper(data, root.right);
}
//这意味着找到了元素
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