Binary Tree ADT (Abstract Data Type) ในโครงสร้างข้อมูล

แนวคิดพื้นฐาน

Binary Tree คือต้นไม้ที่โหนดแต่ละตัวมีลูกได้สูงสุด 2 ตัว (Left และ Right) องศาสูงสุดของโหนดคือ 2 องศาของ Binary Tree จึงเป็น 0, 1, หรือ 2

ในรูป: Binary Tree ประกอบด้วย Root และ Subtree 2 ด้าน คือ TreeLeft และ TreeRight โหนดทางซ้ายเรียกว่า Left Subtree โหนดทางขวาเรียกว่า Right Subtree

การนำไปใช้ (Implementation)

เนื่องจาก Binary Tree มีลูกสูงสุด 2 ตัว จึงสามารถใช้ Pointer โดยตรงได้ การประกาศโหนดคล้าย Doubly Linked List: โหนดเป็น Struct ที่มีข้อมูล (key) และ Pointer 2 ตัว (left, right)

การประกาศโหนด Binary Tree (C/C++ Style)

typedef struct tree_node *tree_ptr;
struct tree_node {
    element_type element1;
    tree_ptr left1;
    tree_ptr right1;
};
typedef tree_ptr TREE;

ประเภทของ Binary Tree

1. Strictly Binary Tree (ต้นไม้แบ่งสองอย่างเคร่งครัด)

ทุกโหนดมีลูก 0 หรือ 2 ตัวเท่านั้น ไม่มีโหนดใดมีลูก 1 ตัว

2. Skew Tree (ต้นไม้เอียง)

ทุกโหนด (ยกเว้น Leaf) มีลูก เพียง 1 ตัว แบ่งเป็น 2 แบบ:

• Left Skewed: มีแค่ Left Subtree
• Right Skewed: มีแค่ Right Subtree

3. Full Binary Tree / Proper Binary Tree (ต้นไม้เต็ม)

Leaf ทุกตัวอยู่ Level เดียวกัน โหนดที่ไม่ใช่ Leaf มีลูก 2 ตัวทุกตัว มีโหนดสูงสุด 2^h+1 - 1 ตัว (h = ความสูง)

4. Complete Binary Tree (ต้นไม้สมบูรณ์)

ทุก Level เต็มไปด้วยโหนด ยกเว้น Level สุดท้าย Level สุดท้ายเต็มจากซ้ายไปขวา

5. Almost Complete Binary Tree (ต้นเกือบสมบูรณ์)

โหนดที่มี Right Child ต้องมี Left Child ด้วย (แต่มี Left Child ไม่จำเป็นต้องมี Right Child)

ความแตกต่าง General Tree vs Binary Tree

การประยุกต์ใช้ Binary Tree

• จัดการ Arithmetic Expression (Expression Tree)
• สร้าง Symbol Table (Compiler)
• Syntax Analysis (Parsing)
• Grammar Representation
• Decision Tree (Machine Learning)