我们将使用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