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