Chèn khóa vào cây trong Javascript

Lần chèn đầu tiên trong cây nhị phân mới được tạo sẽ tạo ra một nút ở gốc. Các phần chèn tiếp theo sẽ được chèn theo thuộc tính cây tìm kiếm nhị phân của các phần tử bên trái nhỏ hơn phần tử gốc và phần bên phải lớn hơn phần tử cha mẹ.

Hãy để chúng tôi xem cách chúng tôi có thể triển khai thuật toán này trong mã -

Ví dụ

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

Hãy cho chúng tôi hiểu cách hoạt động của chức năng này. Đầu tiên, chúng tôi kiểm tra xem gốc có phải là cây null hay không, nghĩa là cây trống nếu có thì chúng tôi chỉ định nút mới làm gốc và chúng tôi đã hoàn tất. Nếu không, chúng ta tạo một biến currNode và trỏ nó tới root. Sau đó, chúng tôi kiểm tra xem dữ liệu của chúng tôi có nhỏ hơn currNode hay không, nếu có, chúng tôi kiểm tra xem con bên trái của nó có phải là null hay không. Nếu đúng thì chúng tôi giữ dữ liệu của mình ở đây và thoát. Nếu không, chúng tôi tiếp tục lặp lại cho đến khi chúng tôi đến một chiếc lá và cuối cùng đặt dữ liệu của chúng tôi ở đó.

Bạn có thể kiểm tra chức năng này bằng cách sử dụng -

Ví dụ

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

Chúng ta cũng có thể làm cho hàm này trở nên đệ quy. Cây vốn là cấu trúc đệ quy và chúng ta có thể sử dụng thuộc tính đệ quy này khá dễ dàng. Hãy xem xét phiên bản đệ quy của insert -

Ví dụ

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

Chúng tôi cần tạo một hàm trợ giúp có thể đệ quy nhưng chúng tôi không muốn hiển thị nó như một thuộc tính của lớp, vì vậy hàm này sẽ nằm ngoài định nghĩa của lớp.

Ví dụ

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

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