Pre-order Traversal ใน Tree ด้วย JavaScript

ใน traversal method นี้ root node จะถูก visit ก่อน แล้ว left subtree และสุดท้าย right subtree

เริ่มจาก A ตาม pre-order เรา visit A ก่อน แล้วไป left subtree B B ก็ถูก traverse pre-order เช่นกัน กระบวนการดำเนินต่อไปจน visit ทุก nodes ผลลัพธ์ pre-order traversal:

A → B → D → E → C → F → G

อัลกอริธมที่เราจะนำไปใช้:

• Print node's data
• Recursively traverse left subtree
• Recursively traverse right subtree

มาดูการนำไปใช้ในคลาส:

preOrder() {
  preOrderHelper(this.root);
}

Helper function:

ตัวอย่าง

function preOrderHelper(root) {
  if (root !== null) {
    console.log(root.data);
    preOrderHelper(root.left);
    preOrderHelper(root.right);
  }
}

ทดสอบการทำงานได้ดังนี้:

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

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);
BST.preOrder();

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

10 5 3 7 15 12 50