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