Tìm kiếm các giá trị tối thiểu và tối đa trong Cây Tìm kiếm Nhị phân Javascript

Trong Cây Tìm kiếm Nhị phân, nếu chúng ta nhìn vào thuộc tính mà con bên trái luôn nhỏ hơn con mẹ, chúng ta sẽ thấy rằng nếu chúng ta tiếp tục lặp lại về phía con bên trái cho đến khi chúng ta đạt được một không có nút con bên trái, về cơ bản chúng ta sẽ tìm thấy phần tử nhỏ nhất trong BST.

Hãy để chúng tôi triển khai chức năng này trong mã của chúng tôi. Từ bây giờ trở đi, chúng tôi sẽ chỉ triển khai các phiên bản duy nhất của hàm, tức là lặp đi lặp lại hoặc đệ quy. Trong trường hợp này, chúng tôi sẽ tạo một hàm lặp -

Ví dụ

getMinVal() {
   if (this.root === null) {
      throw "Empty tree!";
   }
   let currNode = this.root;

   while (currNode.left !== null) {
      currNode = currNode.left;
   }
   return currNode.data;
}

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.getMinVal());

Đầu ra

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

3

Tương tự, bạn có thể mở rộng mã này để viết một hàm có tên getMaxVal () trả về giá trị tối đa bằng cách lặp lại các giá trị con ngoài cùng bên phải. Chúng tôi sẽ chỉ đặt mã ở đây để bạn xác minh -

Ví dụ

getMaxVal() {
if (this.root === null) {
      throw "Empty tree!";
}
let currNode = this.root;

while (currNode.right !== null) {
   currNode = currNode.right;
}
   return currNode.data;
}