在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