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

ใน traversal method นี้ root node จะถูก visit สุดท้าย จึงชื่อว่า post-order ก่อนอื่นเรา traverse left subtree แล้ว right subtree และสุดท้ายคือ root node

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

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

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

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

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

postOrder() {
  postOrderHelper(this.root);
}

Helper function:

ตัวอย่าง

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

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

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

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

ผลลัพธ์

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

3 7 5 12 50 15 10