Melaksanakan pepohon carian binari dalam JavaScript

Struktur Data Pokok

Pokok ialah himpunan nod yang disambungkan oleh beberapa tepi. Mengikut konvensyen, setiap nod pokok Simpan beberapa data dan rujukan kepada nod anaknya.

Pokok Carian Perduaan

Pokok carian binari ialah pepohon perduaan di mana nod dengan nilai yang lebih kecil disimpan di sebelah kiri dan nod dengan nilai yang lebih kecil disimpan di sebelah kiri. Nilai yang lebih tinggi disimpan di sebelah kanan.

Sebagai contoh, perwakilan visual BST yang sah ialah -

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

Sekarang mari kita laksanakan pepohon carian binari kita sendiri dalam bahasa JavaScript.

Langkah 1: Kelas Nod

Kelas ini akan mewakili satu nod yang hadir pada setiap titik dalam BST. BST Tiada apa-apa Sebaliknya, ia adalah koleksi nod yang menyimpan data dan subrujukan yang diletakkan mengikut peraturan. Seperti yang dinyatakan di atas.

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

Untuk mencipta tika Node baharu kita boleh memanggil kelas ini dengan beberapa data -

const newNode = new Node(23);

Ini akan mencipta tika Nod baharu dengan set datanya kepada 23 dan kedua-dua rujukan kiri dan kanan kepada null.

Langkah 2: Kelas Pokok Carian Binari:

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

Ini akan mencipta kelas Pokok Carian Binari, kita boleh memanggilnya menggunakan kata kunci baharu untuk mencipta contoh pokok.

Sekarang kita telah melakukan perkara asas, mari teruskan dan masukkan nod baharu di lokasi yang betul (mengikut peraturan BST yang diterangkan dalam takrifan).

Langkah 3: Masukkan nod dalam 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);
         };
      };
   };
};

Contoh

Kod pepohon carian binari penuh:

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

Atas ialah kandungan terperinci Melaksanakan pepohon carian binari dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!