สรุป เรื่อง (Tree )
tree เป็นส่วนหนึ่งของกราฟเป็นโครงสรางข้อมูลที่มีความสัมพันธ์ระหว่างโหนดแบบลำดับชั้น (Hierarchi calreltionship)
สำหรับในการประยุกต์ใช้ สามารถนำไปใช้ได้ในงานต่าง ๆ เช่น แผนผังแสดงความสัมพันธ์ของโหนดต่าง ๆ องค์ประกอบหรือหน่วยงานโครงสรางสารบัญหนังสือ เป็นต้น
ลักษณะของโหนดจะประกอบไปด้วยดังต่อไปนี้คือ
โหนดแม่ parent or mother node
โหนดลูก child or son node
โหนดราก root node
โหนดพี่น้อง siblings node
โหนดใบ leave node
เส้นแสดงความสัมพันธ์ระหว่างโหนดเรียกว่า กิ่ง (Branch)
ทรีเป็นกราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)
นิยามทรีเป็นรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้ากรณีว่างเรียกว่าไม่มีโหนดหรือ นัลทรี (null tree)ทรีย่อย(sub tree)
ตัวอย่างของโหนดแบบเครือข่ายต้นไม้
Root Node คือ โหนด A หรือโหนดแม่
Child Node หรือ โหนดลูก จากรูป B , C , D และ E เป็น โหนดลูกของ A
Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็นโหนดย่อยๆ ได้แก่ F และ G ดังนั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A ก็เป็นโหนด พ่อแม่ของ B , C , D และ Eกิ่ง (Branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก
Brother Node หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B , C , D , E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
Leaf Node คือ โหนดที่ไม่มีโหนดลูก จากรูปโหนดที่ไม่มีโหนดลูก ได้แก่ F G H I J K L M
Branch Node คือ โหนดที่ไม่ใช่ Leaf Node เช่น โหนด B C D E เรียกว่า Branch Node
Degree คือ จำนวนลูกของโหนด x เช่น degree ของ โหนด A = 4 ได้แก่ B C D E จำนวน degree ของโหนด B = 2 จำนวนdegree ของโหนด F = 0 เนื่องจากโหนด F ไม่มีโหนดลูก
Direct Descendant Node คือโหนดที่มาทีหลังทันที จากรูป B C D E เป็น direct descendant node ของโหนด A เพราะเป็นโหนดที่มาทีหลังทันที
Descendant Node คือ โหนดลูกของโหนด x และโหนดที่ทุกโหนดที่แตกจากโหนดลูกของโหนด x ตัวอย่าง descendant ของโหนด A คือ ทุกโหนดที่เหลือในทรี
Direct Ancestor Node หรือโหนดที่มาก่อนทันที ตัวอย่าง Direct Ancestor ของโหนด H คือ โหนด C , Direct Ancestor ของโหนด C คือ โหนด ALevel หรือระดับ คือ หมายเลขแสดงระดับของโหนดในทรี ซึ่งรูทโหนดจะมีค่า
tree มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR,LNR,LRN,NRL,RNL,RLN
และวิธีเข้าจากซ้ายไปขวามี 3 แบบ คือ NLR,LNR,LRN ลักษณะนี้จะเป็นนิยามแบบ รีเดอร์ซีฟ
การแปลงทรีทั่วไปให้เป็นไบนารีทรี มี 3 ขั้นตอนคือ
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วลบความสัมพันธ์ระหว่างโหนแม่และโหนดลูกอื่น ๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
(Expression Tree)คือ การนำโครงสร้างtreeไปเก็บไว้ในนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรีโดยแต่ละโหนดจะเก็บตัวดำเนินการ(Opreator)และตัวดำเนินการ(Operrand)ของนิพจน์คณิตศาสตร์นั้น ๆ
(Binary Search Tree)ค่าโหนดรากที่มีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้ายและค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและแต่ละทรีย่อยจะมีคุณสมบัติเช่นเดี่ยวกันในแบบไบนารีตัวเลขเป็นต้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น