ค้นหาค่าต่ำสุดและสูงสุดใน Javascript Binary Search Tree

ใน Binary Search Tree หากเราดูคุณสมบัติที่ลูกทางซ้ายมีขนาดเล็กกว่าแม่เสมอ เราจะพบว่าถ้าเราวนซ้ำไปทางลูกทางซ้ายจนกว่าเราจะถึง โหนดที่ไม่มีลูกด้านซ้าย โดยทั่วไปเราจะพบองค์ประกอบที่เล็กที่สุดใน BST

ให้เราใช้ฟังก์ชันนี้ในโค้ดของเรา นับจากนี้เป็นต้นไป เราจะใช้ฟังก์ชันเวอร์ชันเดียว กล่าวคือ แบบวนซ้ำหรือแบบเรียกซ้ำ ในกรณีนี้ เราจะสร้างฟังก์ชันวนซ้ำ -

ตัวอย่าง

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

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

คุณสามารถทดสอบได้โดยใช้ −

ตัวอย่าง

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

ผลลัพธ์

สิ่งนี้จะให้ผลลัพธ์ -

3

ในทำนองเดียวกัน คุณสามารถขยายรหัสนี้เพื่อเขียนฟังก์ชันที่เรียกว่า getMaxVal() ซึ่งคืนค่าสูงสุดโดยการวนซ้ำค่าลูกที่อยู่ทางขวาสุด เราจะใส่รหัสที่นี่เพื่อให้คุณตรวจสอบ -

ตัวอย่าง

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

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