โครงสร้างข้อมูลแบบต้นไม้
Tree Data Structure
Tree Data Structure
โครงสร้างข้อมูลที่ออกแบบมาให้มีลักษณะไม่เป็นเชิงเส้น มีการจัดเก็บข้อมูลเชื่อมโยงกันเป็นระดับชั้น โดยเริ่มจากโหนดแรกที่อยู่บนสุดเรียกว่า Root Node เชื่อมโยงไปยังโหนดระดับรองลงไป แต่ละระดับก็มีการเชื่อมโยงโหนดระดับต่อไป ซึ่งเรียกว่า Subtree
จากรูป
R เป็นรูทของต้นไม้ย่อย A,B,C,D
A เป็นรูทของต้นไม้ย่อย E,F,G
F เป็นรูทของต้นไม้ย่อย J
B เป็นรูทของต้นไม้ย่อย H และ I
โครงสร้างข้อมูลแบบต้นไม้ มีคุณสมบัติดังนี้
1. มีโหนดที่เรียกว่า รากหรือรูต (Root node) , R
2. โหนดที่ไม่ใช่รูตแบ่งย่อยออกเป็น n กลุ่ม โดยที่แต่ละกลุ่มไม่มีโหนดร่วมกันเลย เช่น กลุ่ม T1 , T2 ,…..Tn (n >=0) แต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน
จะเรียกว่าต้นไม้ย่อย (Subtree)
ระดับของโหนด (Level)
ระดับของโหนดหนึ่ง ๆ แสดงถึงหน่วยระยะทางตามแนวดิ่งของโหนดนั้นว่าอยู่ห่างจากรูตโหนดเท่าไร ถ้ากำหนดว่ารูตโหนดของต้นไม้นั้นอยู่ที่ระดับ 1 และกิ่งทุกกิ่งมีความยาวเท่ากัน หมดคือยาว 1 หน่วย เลขระดับของโหนดใด ๆ คือจำนวนกิ่งที่น้อยที่สุดจากรูตโหนดบวกหนึ่งเช่น F มีเลขระดับเป็น 4 เป็นต้น
ดีกรีของโหนด (Level Degree)
ดีกรีของโหนด คือ จำนวนต้นไม้ย่อยของโหนดนั้น จากรูป โหนด X มีดีกรี 1 โหนด A มีดีกรี 2 ส่วนโหนด H มีดีกรี 3 โหนด B มีดีกรี 1 และโหนด E มีดีกรี 0 เป็นต้น
โหนดที่เป็นใบ (Leaf Node)
โหนดที่เป็นใบ หมายถึงโหนดที่มีดีกรีเป็น 0 เช่นโหนด C, D, E, J, F และ G ส่วนโหนดที่มีดีกรีไม่เท่ากับ 0 เรียกว่า โหนดภายใน หรือ interior node หรือ branch nodeImmediate Successor หรือ SON ของโหนด i
Immediate Successor คือโหนดทั้งหลายของต้นไม้ย่อย i ที่มีค่าระดับต่ำกว่าโหนด i อยู่หนึ่ง
เช่น SON ของโหนด H คือโหนด E, I, และ F
Immediate Predecessor หรือ father ของโหนด i
Immediate Predecessor คือโหนดที่มีค่าระดับสูงกว่าโหนด i อยู่หนึ่ง เช่น FATHER ของโหนด J คือโหนด I,
FATHER ของโหนด I คือโหนด H เป็นต้น
ต้นไม้ไบนารีเป็น rooted binary tree ที่ว่างเปล่า หรือประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่มที่ไม่มีโหนดร่วมกัน
แต่ละกลุ่มจะมีชื่อเรียก (โดยตำแหน่งที่อยู่หรือที่เขียน) ว่าต้นไม้ย่อยทางซ้าย (left subtree) และต้นไม้ย่อยทางขวา (right subtree) ตามลำดับ คำว่า ว่างเปล่า ในนิยามหมายความว่า ต้นไม้ไบนารีต้นนั้นมีแต่รูตโหนดเพียงโหนดเดียวเท่านั้น
ต้นไม้ไบนารีแบบสมบูรณ์ หมายถึงต้นไม้ไบนารีที่แต่ละโหนดภายในมีโหนดย่อยซ้ายและขวา (นั่นคือแต่ละโหนดภายในมี left son และ right son) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป (ก) เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มี 3 ระดับ