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

ใน traversal method นี้ left subtree จะถูก visit ก่อน แล้ว root และทีหลัง right sub-tree เราควรจำเสมอว่าแต่ละ node อาจเป็น subtree เองก็ได้

ถ้า binary tree ถูก traverse in-order ผลลัพธ์จะได้ sorted key values ใน ascending order

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

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

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

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

มาดูการนำไปใช้ในคลาส เนื่องจากไม่อยากให้ user ส่ง root เอง เราจะสร้าง helper function นอกคลาสอีกครั้ง:

inOrder() { inOrderHelper(this.root); }

Helper function:

ตัวอย่าง

function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(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.inOrder();

ผลลัพธ์

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

3 5 7 10 12 15 50

สังเกตว่า elements ถูก print ใน sorted order เพราะเรา explore left subtree recursively ก่อน จึงได้ค่าน้อยที่สุดก่อน และดำเนินต่อไปจนสิ้นสุด ได้ elements ทั้งหมดเรียงลำดับ