การใช้แผนผังการค้นหาแบบไบนารีใน JavaScript

โครงสร้างข้อมูลต้นไม้

ต้นไม้คือกลุ่มของโหนดที่เชื่อมต่อกันด้วยขอบบางส่วน ตามธรรมเนียมแล้ว แต่ละโหนดของทรีจะมีข้อมูลและการอ้างอิงถึงลูกของมัน

แผนผังการค้นหาไบนารี

Binary Search tree เป็นไบนารีทรีที่โหนดที่มีค่าน้อยกว่าจะถูกเก็บไว้ทางด้านซ้ายในขณะที่โหนดที่มีค่าสูงกว่าจะถูกเก็บไว้ที่ด้านขวา

ตัวอย่างเช่น การแสดงภาพของ BST ที่ถูกต้องคือ −

     25
   /   \
  20   36
 / \   / \
10 22 30 40

ตอนนี้เรามาติดตั้ง Binary Search Tree ในภาษา JavaScript กัน

ขั้นตอนที่ 1:คลาสโหนด

คลาสนี้จะแสดงโหนดเดียวที่จุดต่างๆ ใน ​​BST BST เป็นเพียงชุดของโหนดที่จัดเก็บข้อมูลและการอ้างอิงย่อยที่วางตามกฎที่อธิบายไว้ข้างต้น

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};

ในการสร้างอินสแตนซ์โหนดใหม่ เราสามารถเรียกคลาสนี้ด้วยข้อมูลบางส่วนได้ -

const newNode = new Node(23);

สิ่งนี้จะสร้างอินสแตนซ์ Node ใหม่พร้อมชุดข้อมูลเป็น 23 และการอ้างอิงซ้ายและขวาทั้งคู่เป็นโมฆะ

ขั้นตอนที่ 2:การค้นหาแบบไบนารีทรีคลาส:

class BinarySearchTree{
   constructor(){
      this.root = null;
   };
};

สิ่งนี้จะสร้างคลาส Binary Search Tree ซึ่งเราสามารถเรียกด้วยคำหลักใหม่เพื่อสร้างอินสแตนซ์ atree

ตอนนี้เมื่อเราทำสิ่งพื้นฐานเสร็จแล้ว เรามาทำการแทรกโหนดใหม่ในตำแหน่งที่ถูกต้อง (ตามกฎของ BST ที่อธิบายไว้ในคำจำกัดความ)

ขั้นตอนที่ 3:การแทรกโหนดใน BST

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

ตัวอย่าง

รหัสต้นไม้การค้นหาไบนารีแบบเต็ม:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);