เราได้รับ Inorder และ Preorder traversals ของไบนารีทรี เป้าหมายคือการสร้างต้นไม้จากการข้ามผ่านที่กำหนด
การข้ามผ่านแบบไม่เรียงลำดับ − ในการข้ามผ่านต้นไม้ประเภทนี้ ต้นไม้ย่อยด้านซ้ายจะถูกเข้าชมก่อน ตามด้วยโหนดและทรีย่อยด้านขวาในตอนท้าย
ไม่เป็นระเบียบ (รากของต้นไม้)
-
สำรวจทรีย่อยทางซ้ายของโหนดที่ชี้โดยรูท เรียก inorder ( root→left )
-
เยี่ยมชมราก
-
สำรวจทรีย่อยทางขวาของโหนดที่ชี้โดยรูท เรียก inorder ( root→right )
สั่งจองล่วงหน้า − ในการข้ามผ่านต้นไม้ประเภทนี้ โหนดจะเข้าชมก่อน ตามด้วยทรีย่อยด้านซ้ายและทรีย่อยด้านขวาในตอนท้าย
สั่งซื้อล่วงหน้า (รากต้นไม้)
- เยี่ยมชมราก
- สำรวจทรีย่อยทางซ้ายของโหนดที่รูทชี้ เรียก inorder ( root→left )
- ข้ามทรีย่อยทางขวาของโหนดที่รูทชี้ เรียก inorder ( root→right )
จะมีการระบุเส้นทาง inorder และ preorder traversal ของต้นไม้ด้านล่าง -
ไม่เป็นระเบียบ
2-3-4-5-6-8-10
สั่งจองล่วงหน้า
4-3-2-5-8-6-10
ตอนนี้เราจะสร้างต้นไม้ด้านบนอีกครั้งสำหรับการสั่งซื้อล่วงหน้าและการข้ามลำดับที่กำหนด
ไม่เป็นระเบียบ
2-3-4-5-6-8-10
สั่งจองล่วงหน้า
5-3-2-4-8-6-10
-
ดังที่เราทราบแล้วว่าการสั่งซื้อล่วงหน้าไปที่โหนดรูทก่อน จากนั้นค่าแรกจะแทนรูทของทรีเสมอ จากข้างบนลำดับที่ 5 คือรากของต้นไม้
สั่งจองล่วงหน้า
5 -3-2-4-8-6-10
-
จากการสำรวจแบบไม่เรียงลำดับด้านบน เรารู้ว่าทรีย่อยด้านซ้ายของโหนดมีการสำรวจก่อนที่จะตามด้วยทรีย่อยด้านขวา ดังนั้น ค่าทั้งหมดทางด้านซ้ายของ 5 ตามลำดับจะเป็นของทรีย่อยทางซ้าย และค่าทั้งหมดทางด้านขวาจะเป็นของทรีย่อยทางขวา
ไม่เป็นระเบียบ
2-3-4 ← 5 → 6-8-10
- ตอนนี้สำหรับทรีย่อยด้านซ้าย ให้ทำแบบเดียวกับด้านบน
การสั่งผ่านล่วงหน้าของทรีย่อยด้านซ้ายคือ 3 -2-4 ดังนั้น 3 จึงกลายเป็นรูท
Inorder traversal แบ่งออกเป็น 2 ← 3 → 4
- ตอนนี้สำหรับทรีย่อยด้านขวา ให้ทำแบบเดียวกับด้านบน
การสั่งผ่านล่วงหน้าของทรีย่อยด้านขวาคือ 8 -6-10 ดังนั้น 8 จึงกลายเป็นรูต
Inorder traversal แบ่งออกเป็น 6 ← 8 → 10
ด้วยวิธีนี้ เราจึงสร้างต้นไม้ดั้งเดิมจากการสั่งซื้อล่วงหน้าและการสำรวจแบบไม่เรียงลำดับที่กำหนด
