การแทรกคีย์ลงในทรีใน Javascript

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

มาดูกันว่าเราจะใช้อัลกอริธึมนี้ในโค้ดได้อย่างไร -

ตัวอย่าง

insertIter(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node; return;
   }

   let currNode = this.root;
   while (true) {
      if (data < currNode.data) {
         // Set the value here as we've reached a leaf node
         if (currNode.left === null) {
            currNode.left = node;
            break;
         } else {
            currNode = currNode.left;
         }
      } else {
         // Set the value here as we've reached a leaf node
         if (currNode.right === null) {
            currNode.right = node;
            break;
         } else {
            currNode = currNode.right;
         }
      }
   }
}

ให้เราเข้าใจว่าฟังก์ชันนี้ทำงานอย่างไร ขั้นแรก เราตรวจสอบว่ารูทเป็นโมฆะหรือไม่ ซึ่งหมายความว่าต้นไม้จะว่างเปล่าถ้าใช่ จากนั้นเราจะกำหนดโหนดใหม่เป็นรูท และเสร็จสิ้น หากไม่เป็นเช่นนั้น เราจะสร้างตัวแปร currNode และชี้ไปที่รูท จากนั้นเราตรวจสอบว่าข้อมูลของเราน้อยกว่า currNode หรือไม่ ถ้าใช่ เราจะตรวจสอบว่าลูกด้านซ้ายเป็นโมฆะหรือไม่ ถ้าเป็นเช่นนั้นเราจะเก็บข้อมูลของเราไว้ที่นี่และออก มิฉะนั้น เราจะวนซ้ำจนกว่าจะถึงจุดหนึ่งและในที่สุดก็วางข้อมูลของเราไว้ที่นั่น

คุณสามารถทดสอบฟังก์ชันนี้ได้โดยใช้ -

ตัวอย่าง

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

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

ตัวอย่าง

insertRec(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node;
   } else {
      insertRecHelper(this.root, node);
   }
}

เราจำเป็นต้องสร้างฟังก์ชันตัวช่วยที่สามารถเรียกซ้ำได้ แต่เราไม่ต้องการเปิดเผยว่าเป็นคุณสมบัติของคลาส ดังนั้นฟังก์ชันนี้จะไม่อยู่ในคำจำกัดความของคลาส

ตัวอย่าง

function insertRecHelper(root, node) {
   if (node.data < root.data) {
      // Set the value here as we've reached a leaf node

      if (root.left === null) {
         root.left = node;
      } else {
         // Recursively call this function with the left subtree
            insertRecHelper(root.left, node);
      }
   } else {
      // Set the value here as we've reached a leaf node
      if (root.right === null) {
         root.right = node;
      } else {
         // Recursively call this function with the right subtree
         insertRecHelper(root.right, node);
      }
   }
}

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

ตัวอย่าง

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