สร้าง Binary Search Tree (BST) ใน JavaScript

โครงสร้างข้อมูล Tree

Tree เป็นโหนดเชื่อมต่อกัน แต่ละโหนดเก็บข้อมูลและอ้างอิงลูก

Binary Search Tree

BST คือ Binary Tree ที่โหนดค่าน้อยอยู่ซ้าย ค่ามากอยู่ขวา

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

ขั้นตอนการสร้าง

1. Class Node

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

2. Class BinarySearchTree

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

3. Insert Node

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