ทรี เป็นโครงสร้างข้อมูลไม่เชิงเส้น โดยจะมีการเรียงข้อมูลลดหลั่งลงเป็นลำดับๆไปส่วนมากจะใช้ให้เห็นถึงความสำคัญข้อมูลว่าอันไหนสำคัญกว่าเเละอันไหนรองๆลงมา
ชื่อเรียกของโหนด
-จะมีการเีรียงข้อมูลโดยข้อมูลที่อยู่ในระดับสูงสุดจะเรียกว่า โหนดราก
-รองลงมาจะเป็นโหนดเเม่
-ข้อมูลที่ออกมาจากโหนดเเม่ คือ โหนดลูก
-โหนดที่มีเเม่เป็นโหนดเดียวกัน เรียกว่าโหนดพี่น้อง-โหนดที่ไม่มีลูกคือ โหนดใบ
-เส้นที่ลากเเสดงความสัมพันธ์คือ กิ่ง
นิยามของทรี
1.เป็นนิยามเเบบกราฟ-ทรีคือ กราฟที่จะไม่มีวงจรปิดจำนวนโหนดทั้งหมด เท่ากับZ กิ่งของโหนดก็จะเท่ากับ Z-1 เสมอ
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ-ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้าเป็นโหนดว่างคือนัลทรี เเละโหนดที่ออกมาจากโหนดราก คือ ทรีย่อย
นิยามที่เกี่ยวกับทรี
1. ฟอร์เรสต์ (Forest)คือ กลุ่มของทรีที่มีโหนดรากเเละย่อยๆออกมา
2. ทรีที่มีแบบแผน (Ordered Tree)คือ ทรีที่โหนดมีความสัมพันธ์ที่แน่นอนหรือมีเเบบเเผนนั้นเอง
3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนเเต่ข้อมูลไม่เหมือนกัน
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ ทั้งข้อมูลทั้งโครงสร้าง
5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด
6. ระดับของโหนด (Level of Node) คือการเเบ่งระดับของทรีเป็นชั้นๆเช่นโหนดรากคือระดับ1 โหนดเเม่ระดับ 2 เป็นต้น
การเเทนที่ในหน่วยความจำมี 2 แบบ
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด
2.เเบบไบนารีทรี คือเเต่ละโหนดจะมีลิงค์เเค่2ลิงค์เท่านั้นมีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLNN คือ เยือนโหนดรากL คือ ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์R คือ ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
ไม่มีความคิดเห็น:
แสดงความคิดเห็น