Tìm kiếm các giá trị trong Cây Tìm kiếm Nhị phân Javascript

Chúng ta sẽ sử dụng thuộc tính của BST để tra cứu các phần tử trong đó. Trước tiên, hãy cùng chúng tôi xem xét việc triển khai lặp đi lặp lại tìm kiếm -

Ví dụ

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;
}

Trong hàm này, chúng tôi bắt đầu với gốc là currNode và kiểm tra dữ liệu của chúng tôi so với dữ liệu của currNode. Nếu chúng tôi tìm thấy một kết quả phù hợp, chúng tôi trả về true, nếu không, chúng tôi tiếp tục lặp lại ở bên trái hoặc bên phải theo mối quan hệ của dữ liệu với dữ liệu của currNode cho đến khi chúng tôi đạt được một lá hoặc tìm thấy phần tử của chúng tôi.

Bạn có thể kiểm tra điều này bằng cách sử dụng -

Ví dụ

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));

Đầu ra

Điều này sẽ cung cấp đầu ra -

false
true
true
false
false

Tương tự như chức năng chèn, tìm kiếm cũng có thể được thực hiện một cách đệ quy.

searchRec(data) {
   return searchRecHelper(data, this.root);
}

Một lần nữa, chúng ta sẽ cần tạo một hàm trợ giúp mà chúng ta không muốn như một phần của lớp, vì vậy chúng ta sẽ tạo hàm này bên ngoài định nghĩa lớp -

Ví dụ

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;
}

Bạn có thể kiểm tra điều này bằng cách sử dụng -

Ví dụ

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));

Đầu ra

Điều này sẽ cung cấp đầu ra -

false
true
true
false
false