การข้ามผ่านในลำดับใน Javascript Tree

ในวิธีการข้ามผ่านนี้ ทรีย่อยด้านซ้ายจะถูกเยี่ยมชมก่อน จากนั้นจึงไปที่รูทและต่อมาในทรีย่อยทางขวา เราควรจำไว้เสมอว่าทุกโหนดอาจเป็นตัวแทนของแผนผังย่อยได้เอง

หากต้นไม้ไบนารีถูกข้าม ในลำดับ เอาต์พุตจะสร้างค่าคีย์ที่เรียงลำดับจากน้อยไปหามาก

เราเริ่มจาก A และตามการข้ามผ่านตามลำดับ เราย้ายไปที่ทรีย่อยด้านซ้าย B. ข ได้ผ่านตามลำดับเช่นกัน กระบวนการนี้ดำเนินต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด ผลลัพธ์ของการข้ามผ่านของต้นไม้นี้จะเป็น −

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

นี่คืออัลกอริทึมที่เราจะนำไปใช้ -

สำรวจทรีย่อยด้านซ้ายซ้ำๆ
พิมพ์ข้อมูลของโหนด
ข้ามทรีย่อยด้านขวาซ้ำๆ

ให้เราดูว่าเราจะนำไปใช้อย่างไรในชั้นเรียนของเรา เนื่องจากเราไม่ต้องการให้ผู้ใช้ส่งผ่านรูทเอง เราจึงจะสร้างฟังก์ชันตัวช่วยนอกชั้นเรียนอีกครั้ง

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

ฟังก์ชันตัวช่วย -

ตัวอย่าง

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

ผลลัพธ์

สิ่งนี้จะให้ผลลัพธ์ -

โปรดทราบว่าองค์ประกอบถูกพิมพ์ตามลำดับการจัดเรียง เนื่องจากเราสำรวจทรีย่อยด้านซ้ายซ้ำๆ กันก่อน เราจึงได้ค่าที่น้อยที่สุดก่อน สิ่งนี้ดำเนินต่อไปจนจบและเราได้รับองค์ประกอบทั้งหมดตามลำดับการเรียงลำดับ