ทรี (Tree) เป็นโครงสร้างข้อมูลไม่เชิงเส้น โดยจะมีการเรียงข้อมูลลดหลั่งลงเป็นลำดับๆไปส่วนมากจะใช้ให้เห็นถึงความสำคัญข้อมูลว่าอันไหนสำคัญกว่าเเละอันไหนรองๆลงมา
ชื่อเรียกของโหนด
- จะมีการเีรียงข้อมูลโดยข้อมูลที่อยู่ในระดับสูงสุดจะเรียกว่า โหนดราก
- รองลงมาจะเป็นโหนดเเม่
- ข้อมูลที่ออกมาจากโหนดเเม่ คือ โหนดลูก
- โหนดที่มีเเม่เป็นโหนดเดียวกัน เรียกว่าโหนดพี่น้อง
- โหนดที่ไม่มีลูกคือ โหนดใบ
- เส้นที่ลากเเสดงความสัมพันธ์คือ กิ่ง
นิยามของทรี
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ลิงค์เท่านั้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น