在 JavaScript 二叉搜索树中搜索值

我们将利用 BST 的特性来查找其中的元素。我们先看一个搜索的迭代实现 -

示例

searchIter(data) {
   let currNode = this.root;
   while (currNode !== null) {
      if (currNode.data === data) {
         // Found the element!
         return true;
      } else if (data < currNode.data) {
         // Go Left as data is smaller than parent
         currNode = currNode.left;
      } else {
         // Go right as data is greater than parent
         currNode = currNode.right;
      }
   }
   return false;
}

在此函数中，我们从 root 作为 currNode 开始，并将我们的数据与 currNode 的数据进行比较。如果找到匹配项，则返回 true，否则我们将根据 data 与 currNode 的 data 的关系继续在 left 或 right 中迭代，直到我们到达叶节点或找到了我们的元素。

你可以使用 - 对其进行测试

示例

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

类似于 insert 函数，搜索也可以以递归方式实现。 

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

更新于： 15-6 月-2020

428 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告