การแทนค่า Binary Tree ในหน่วยความจำ (Array vs Linked List)

2 วิธีการแทนค่า

1. Array Representation
2. Linked List Representation

Array Representation

เก็บข้อมูลแบบ Level Order (ทีละระดับ) ถ้าของขาดเว้นว่างไว้

Index 1 = Root, ลูกอยู่ Index 2, 3 สูตร:

• Child₁ = 2 × Parent
• Child₂ = 2 × Parent + 1
• Parent = ⌊Child / 2⌋

ข้อดี: หา Parent/Child เร็ว ข้อเสีย: ไม่ประหยัดหน่วยความจำ (เว้นที่ว่างมาก) เหมาะกับ Complete/Full Binary Tree

Linked List Representation

สร้าง Node สำหรับแต่ละองค์ประกอบ มี Pointer ชี้ Left และ Right Child

ยืดหยุ่นกว่า ประหยัดพื้นที่สำหรับ Sparse Trees