การเพิ่มข้อมูลใน Tree ด้วย JavaScript

การ insert ครั้งแรกใน binary tree ที่เพิ่งสร้างจะสร้าง node ที่ root การ insert ต่อๆ ไปจะทำตาม property ของ BST คือ left child น้อยกว่า parent และ right child มากกว่า parent

มาดูวิธีการนำอัลกอริธมนี้ไปใช้งานในโค้ด:

ตัวอย่างโค้ด

insertIter(data) {
  let node = new this.Node(data);
  // ตรวจสอบว่าต้นไม้ว่างหรือไม่
  if (this.root === null) {
    // ใส่เป็น element แรก
    this.root = node;
    return;
  }
  let currNode = this.root;
  while (true) {
    if (data < currNode.data) {
      // ตั้งค่าที่นี่เพราะถึง leaf node แล้ว
      if (currNode.left === null) {
        currNode.left = node;
        break;
      } else {
        currNode = currNode.left;
      }
    } else {
      // ตั้งค่าที่นี่เพราะถึง leaf node แล้ว
      if (currNode.right === null) {
        currNode.right = node;
        break;
      } else {
        currNode = currNode.right;
      }
    }
  }
}

มาเข้าใจการทำงานของฟังก์ชันนี้: เริ่มตรวจสอบว่า root เป็น null หมายถึง tree ว่าง ถ้าใช่ กำหนด node ใหม่เป็น root เสร็จแล้ว ถ้าไม่ เราสร้าง currNode ชี้ไป root แล้วเช็คว่า data น้อยกว่า currNode หรือไม่ ถ้าใช่ เช็คว่า left child เป็น null หรือไม่ ถ้าใช่ ใส่ข้อมูลที่นี่และออก มิฉะนั้นวนต่อจนถึง leaf และวางข้อมูล

ทดสอบฟังก์ชันนี้ได้ดังนี้:

ตัวอย่างการใช้งาน

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

เราสามารถทำให้ฟังก์ชันนี้เป็น recursive ได้เช่นกัน Tree เป็นโครงสร้างที่ recursive โดยปัจจุบัน เราสามารถใช้ property นี้ได้ง่าย มาดู recursive version ของ insert:

ตัวอย่างโค้ด

insertRec(data) {
  let node = new this.Node(data);
  // ตรวจสอบว่าต้นไม้ว่างหรือไม่
  if (this.root === null) {
    // ใส่เป็น element แรก
    this.root = node;
  } else {
    insertRecHelper(this.root, node);
  }
}

เราต้องสร้าง helper function ที่ recurse ได้ แต่ไม่อยาก expose เป็น property ของคลาส ดังนั้นฟังก์ชันนี้จะอยู่นอก class definition

ตัวอย่าง

function insertRecHelper(root, node) {
  if (node.data < root.data) {
    // ตั้งค่าที่นี่เพราะถึง leaf node แล้ว
    if (root.left === null) {
      root.left = node;
    } else {
      // เรียกฟังก์ชันนี้ซ้ำกับ left subtree
      insertRecHelper(root.left, node);
    }
  } else {
    // ตั้งค่าที่นี่เพราะถึง leaf node แล้ว
    if (root.right === null) {
      root.right = node;
    } else {
      // เรียกฟังก์ชันนี้ซ้ำกับ 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);