สรุปเรื่อง "ทรี"
ทรี หรือที่เรียกอีกอย่างหนึ่งว่าโครงสร้างต้นไม้
เป็นอีกโครงสร้างที่มีความสัมพันธ์กัน
จะประกอบไปด้วยโหนด ( Node )
แต่ละโหนดจะมีความสัมพันธ์กัน
และยังสามารถแตกโหนดออกมาเป็นโหนดย่อยๆ
ได้อีกหลายโหนดด้วยกันเรียกว่า "โหนดลูก"
เมื่อเรามีโหนดลูกแล้วก็ยังสามารถ
แตกออกไปเป็นโหนดพ่อ โหนดแม่ได้อีก
ชนิดของ "ทรี" จะแบ่งออกได้ 2 ชนิดคือ
1.ทรีทั่วไป
2.ไบนารีทรี
ในแต่ละโหนดที่มีแม่เป็นโหนดเดียวกันนั้น
เรียกว่าโหนดพี่น้อง
โหนดที่ไม่มีโหนดลูกเรียกว่าโหนดใบ
และเส้นที่แสดงความสัมพันธ์ระหว่างโหนด 2 โหนด เรียกว่า "กิ่ง"
ระดับของโหนดคือ
ระยะทางในแนวดิ่งของโหนดนั้นๆ
ที่อยู่ห่างจากโหนดรากเมื่อกำหนดให้โหนดรากของทรีนั้น
อยู่ในระดับ 1 และกิ่งแต่ละกิ่งที่มีความยาวเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย
ซึ่งระดับของโหนดจะเท่ากับกิ่งที่น้อยที่สุด
จากโหนดรากไปยังโหนดใดๆ บวกด้วย 1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ
ซึ่งห่างจากโหนดรากเรียกว่า "ความสูง" หรือ "ความลึก"
ไบนารีทรีมีทั้งทรีย่อย ซ้าย เเละ ขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนด
จะต้องอยู่ในระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
มี 3 ขั้นตอน คือ
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2.ให้มีการเชื่อมความสัมพันธ์กันระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี มีด้วยกัน 3 แบบคือ
**การท่องไปแบบพรีออเดอร์
1เยือนโหนดราก
2.ท่องไปในทรีย่อยทางซ้ายแบบพรีออเดอร์
3.ท่องไปในทรีย่อยทางขวาแบบพรีออเดอร์
**การท่องแบบอินออเดอร์
1.ท่องไปในทรีย่อยทางซ้ายแบบอินออเดอร์
2.เยือนโหนดราก
3.ท่องไปในทรีย่อยทางขวาแบบอินออเดอร์
**การท่องแบบโพสต์ออร์เดอร์
1.ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
2.ท่องไปในทรย่อยทางขวาแบบโพสต์ออร์เดอร์
3.เยือนโหนดราก
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น