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