โครงสร้างทรี
ทรีเป็นโครงสร้างที่มีความสัมพันธ์ในลักษณะลำดับชั้นสมาชิกแต่ละโหมดล้วนแต่มีความสัมพันธ์กันในลักษณะเหมือนครอบครัวเดียวกันโดยมีโหนดพ่อซึ่งอยู่ระดับที่เหนือกว่ามีเส้นเชื่อมโยงจากโหนดไปยังโหนดที่อยู่ระดับต่ำกว่าที่เรียกว่าโหนดลูก
องค์ประกอบของทรี
โหนด ( Node )
ที่ใช้สำหรับบรรจุข้อมูลโดยจะมีกิ่งซึ่งเป็นเส้นที่โยงโหนดเข้าด้วยกันที่เรียกปลาจำนวนของ
บรานช์ (Branch) ที่สัมพันธ์กับโหนดเรียกว่า ดีกรี (Degree) และถ้าหากที่เป็นที่ที่ไม่ใช่ที่ว่างหนวดแรกจะเรียกรูท
(root) โดยโหนดทุก ๆ โหนดยกเว้นรูทโหนดจะมีเพียง 1 predecessor ในขณะที่ successor อาจเป็น 0
หรือ 1 หรือมากกว่า 1 ก็ได้ สำหรับ Leaf ก็คือโหนดใบที่ไม่มีบรานช์เชือมโยงไปยังโหนดถัดไปหรือโหนดที่ไม่มีตัวตามหลังหรือ Successor นั่นเองในขณะที่
โหนดพ่อ (Parent) จะมี่โหนดตามหลังหรือโหนดลูก (Child) ต่อท้าย
โหนดลูกตั้งแต่สองโหนดหรือมากกว่าที่มาจากพ่อเดียวกันจะเรียกว่า โหนดพี่น้อง (Siblings)
โหนดต่าง ๆ
ภายในทรีจะอยู่ในระดับที่ต่างกันโดยเริ่มต้นจากรูทโหนดซึ่งถือเป็นระดับแรกสุด(Level) ส่วนลูกๆ
ของรูทโหนดก็คือระดับที่ 1 (Lelvel) และลูกๆ
ของโหนดในระดับที่ 1 ก็จะอยู่ในระดับที่ 2 (Level 2) ซึ่งจะเพิ่มระดับไปเรื่อยๆเมื่อลูกหลานเพิ่มขึ้น
ซับทรี (Subtrees)
หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต้ Root โดย
- Node แรกของ Subtrees จะเป็น Root ของ Subtree นั้น และใช้เป็นชื่อเรียก Subtree
- Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ Empty
ต้นไม้แบบไบนารี (Binary Tree)
ไบนารีทรี หมายถึงทรีที่มีโหนดลูกไม่เกิน สองโหนด
ประกอบด้วยโหนดลูกทางซ้าย(Left child)และโหนดลูกทางขวา(Right child) โหนดลูก
อาจเป็นทรีย่อยก็ได้ซึ่งแบ่งออกเป็น ทรี
ย่อยทางซ้ายและทรีย่อยทางขวาและโหนดลูกแต่ละโหนดอาจมีหนดลูกเพียงด้านซ้ายหรือด้านขวาด้านเดียวก็ได้สำหรับโหนดของทรีมีจำนวนเป็น
0 เรียกว่าทรีว่าง (Empty Tree)
การท่องผ่าน Binary tree
การท่องผ่านโหนดหมายถึงการเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมาแสดงหรือเพื่อการค้นหาเพื่อประมวลผลการเดินเยี่ยมโหนดมี
3 วิธี
1. imorder trabersal หรือ symmetric
order จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ก่อนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์(Left/
Root/ Right)
2. preorder traversal จะทำการเยี่ยมโหนดรากก่อน
เยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ พรีออเดอร์
และเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบพรีออเดอร์ (Root/Left/Right)
3. postorder traversal หรือ Endorder จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ
โพสออเดอร์ก่อนเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบโพสออเดอร์และเยี่ยมโหนดราก (Left/Right/Root
ไม่มีความคิดเห็น:
แสดงความคิดเห็น