ย่อยๆได้อีกหลายโหนดเรียกกันว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent node) โดยการแตกโหนดออกเป็นโหนดย่อยๆ ได้อีก
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 K J K L M
Baranch 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 คือ ทุกโหนดที่เหลือในทรี
Binary tree มีลักษณะเหมือนกับ tree ปกติแต่มีคุณสมบัติพิเศษ คือ แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด หรือพูดอีกอย่างหนึ่งว่า แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2
Complete Binary Tree
หรือต้นไม้ใบนารีแบบสมบูรณ์ มีลักษณะคล้ายกับ Binary Tree แต่มีข้อพิเศษ คือ
1. ทุกโหนดที่ไม่ใช่ Leaf node จะต้องมีโหนดลูก 2 โหนด
2. Leaf node จะต้องอยู่ในระดับเดียวกัน
Binary Search Tree
จะมีลักษณะคล้ายกับ Binary Tree แต่มีลักษณะพิเศษเพิ่มเติม คือ
1. ค่าของรูทโหนดมีค่ามากกว่าค่าในต้นไม้ย่อยซ้าย
การท่องไปในทรี (Tree Traversal)
สามารถท่องเข้าไปในทรีเพื่อดูข้อมูลได้ 3 วิธีด้วยกัน คือ
1. Preorder
2. inorder
3. postorder
ในการท่องเข้าไปในทรีแต่ละแบบจะใช้สัญลักษณ์ดังนี้ Root = root node left = ต้นไม้ย่อยซ้ายของ
Root Right = ต้นไม้ย่อยขวาของ Root
วิธีการท่องเข้าไปในทรีแต่ละทรีแต่ละแบบจะมีลักษณะดังนี้
1. Preorder = Root Left Right
2. Inorder = Left Root Right
3. Postorder = Left Right Root
ตัวอย่างแสดงการท่องไปในทรี
ไม่มีความคิดเห็น:
แสดงความคิดเห็น