t# 1. Tree

**ต้นไม้ (Tree)** คือ กราฟที่เชื่อมต่อกันและไม่มีวงจร มีคุณสมบัติที่ควรทราบดังนี้
- โดยประกอบด้วย $n$ โหนดและ $n − 1$ เส้นเชื่อม
- หากนำเส้นเชื่อมออกจากต้นไม้ ใด ๆ จะทำให้กราฟแบ่งออกเป็นสองส่วน (components)
- การเพิ่มเส้นเชื่อมเข้าไปในต้นไม้จะทำให้เกิดวงจรขึ้น
- ระหว่างโหนดใด ๆ สองโหนดในต้นไม้จะมีเส้นทางเฉพาะเจาะจงเพียงเส้นทางเดียวเสมอ

ตัวอย่างต้นไม้ที่ประกอบไปด้วย 8 จุดยอดและ 7 เส้นเชื่อม


**ใบ (leaves)** คือ โหนดที่มีดีกรีเท่ากับ 1 หรือพูดง่าย ๆ คือมีโหนดที่ติดกันเพียงโหนดเดียว ตัวอย่างเช่น จากต้นไม้ข้างต้น ใบของต้นไม้คือโหนด $3, 5, 7$ และ $8$

**ต้นไม้ที่มีราก (Rooted Tree)** จะมีการกำหนดโหนดหนึ่งเป็นรากของต้นไม้ (Root) และโหนดอื่น ๆ จะอยู่ใต้รากต้นไม้นั้น ตัวอย่างเช่น ในต้นไม้ต่อไปนี้ โหนด 1 ถูกกำหนดให้เป็นรากของต้นไม้


**ความสัมพันธ์ระหว่างโหนดในต้นไม้ที่มีราก**
- ลูก (Children) ของโหนด คือ โหนดที่อยู่ระดับต่ำกว่าซึ่งเชื่อมต่อโดยตรงกับโหนดปัจจุบัน
- พ่อแม่ (Parent) ของโหนด คือ โหนดที่อยู่ระดับสูงกว่าซึ่งเชื่อมต่อโดยตรงกับโหนดปัจจุบัน
- โหนดราก (Root Node) ไม่มีโหนดพ่อแม่
- แต่ละโหนดจะมีโหนดพ่อแม่เพียงโหนดเดียวเท่านั้น ยกเว้นรากของต้นไม้ซึ่งจะไม่มีพ่อแม่
- พี่น้อง (Sibling) คือ โหนดที่มีพ่อแม่เดียวกัน
- ความลึก (Depth) คือ ระยะทางจากโหนดรากไปยังโหนดปัจจุบัน
- ความสูง (Height) คือ ระยะทางจากโหนดปัจจุบันไปยังโหนดใบที่อยู่ลึกที่สุด

ตัวอย่างเช่น ในต้นไม้ด้านบน
- โหนด 2 มีลูกเป็นโหนด 5 และ 6
- โหนด 2 มีพ่อแม่เป็นโหนด 1
- โหนด 5 และ 6 เป็นพี่น้องกัน
- โหนด 2 มีความลึกเท่ากับ 1 มีความสูงเท่ากับ 2

**โครงสร้างของต้นไม้ที่มีราก (Recursive Structure)**
โครงสร้างของต้นไม้ที่มีรากสามารถนิยามแบบเวียนเกิด (Recursive) ได้ โดย แต่ละโหนดสามารถเป็นรากของต้นไม้ย่อย (Subtree) ซึ่งมีโหนดนั้นเป็นรากและรวมโหนดลูกทั้งหมดที่อยู่ใต้โหนดนั้น

ตัวอย่างเช่น

ต้นไม้ย่อยที่มีโหนด $2$ เป็นราก ประกอบด้วยโหนด $2, 5, 6$ และ $8$

## 2. Tree Traversal
แม้ว่าจะสามารถใช้ อัลกอริทึมท่องกราฟทั่วไป เช่น DFS (Depth-First Search) หรือ BFS (Breadth-First Search) ในการท่องโหนดของต้นไม้ได้ แต่การท่องต้นไม้จะง่ายกว่ากราฟทั่วไป เนื่องจาก:

1. ไม่มีวัฏจักร (Cycles) – ทำให้ไม่ต้องกังวลเรื่องการกลับมาเยี่ยมโหนดเดิมซ้ำ
2. ไม่มีเส้นทางที่เชื่อมกลับ (No Multiple Paths) – ในต้นไม้ แต่ละโหนดมีเพียงเส้นทางเดียวที่สามารถใช้เดินทางจากโหนดรากไปยังโหนดใด ๆ ในต้นไม้ได้

ดังนั้น DFS จึงเป็นวิธีที่นิยมใช้ ในการท่องต้นไม้ เพราะทำงานได้ง่ายและมีประสิทธิภาพสูง

**ตัวอย่างโปรแกรม**

void dfs(int s, int e) {
    // ประมวลผลโหนด s (สามารถเพิ่มโค้ดสำหรับการทำงานที่ต้องการได้)

    // วนลูปผ่านโหนดที่เชื่อมต่อกับ s
    for (auto u : adj[s]) {
        if (u != e) // หลีกเลี่ยงการกลับไปโหนดก่อนหน้า
            dfs(u, s);
    }
}

// เราสามารถเริ่มต้นการท่องต้นไม้จากโหนด x โดยเรียกใช้ฟังก์ชัน
dfs(x, 0);

## 3. การใช้ Dynamic Programming บนต้นไม้ (Tree DP)
Dynamic Programming (DP) สามารถนำมาใช้คำนวณข้อมูลระหว่างการท่องต้นไม้ได้ เช่น:

- หาจำนวนโหนดใน subtree ของโหนดใด ๆ
- คำนวณ เส้นทางที่ยาวที่สุดจากโหนดไปยังใบไม้
- หาค่าต่าง ๆ ที่สามารถแตกออกเป็นปัญหาย่อยได้

DP บนต้นไม้สามารถทำให้การคำนวณทำได้ใน O(n) เวลาแทนที่จะต้องใช้วิธี brute force ที่อาจใช้เวลามากกว่านั้น

### 3.1 คำนวณจำนวนโหนดใน subtree
เราจะคำนวณค่า count[s] ซึ่งหมายถึงจำนวนโหนดทั้งหมดที่อยู่ใน subtree ของโหนด s รวมถึงตัวมันเอง โดยพิจารณาคุณสมบัติของ subtree ต่อไปนี้
- โหนด s เป็นรากของ subtree
- subtree ของ s ประกอบด้วยตัวมันเอง และ subtree ของลูก ๆ
- ดังนั้นสามารถใช้ DFS + DP เพื่อคำนวณค่า count[s] ได้

**ตัวอย่างโปรแกรม**

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN]; // กราฟต้นไม้
int countSubtree[MAXN]; // เก็บจำนวนโหนดใน subtree ของแต่ละโหนด

void dfs(int s, int e) {
    countSubtree[s] = 1; // เริ่มต้นด้วยตัวมันเอง
    for (auto u : adj[s]) {
        if (u == e) continue; // ข้ามโหนดพ่อแม่
        dfs(u, s);
        countSubtree[s] += countSubtree[u]; // รวมขนาดของ subtree ลูก ๆ
    }
}

int main() {
    int n; cin >> n; // จำนวนโหนดในต้นไม้
    for (int i = 1; i < n; i++) { // รับข้อมูลเส้นเชื่อมของต้นไม้
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0); // เริ่ม DFS จากรากของต้นไม้ (สมมติว่าโหนด 1 เป็นราก)

    for (int i = 1; i <= n; i++) {
        cout << "Subtree size of node " << i << " : " << countSubtree[i] << "\n";
    }

    return 0;
}

## 4. การหาค่าเส้นผ่านศูนย์กลางของต้นไม้ (Tree Diameter)
เส้นผ่านศูนย์กลางของต้นไม้ หมายถึง ความยาวของเส้นทางที่ยาวที่สุด ระหว่างสองโหนดในต้นไม้

ตัวอย่างเช่น สำหรับต้นไม้ด้านล่าง

เส้นผ่านศูนย์กลางของต้นไม้นี้คือ 4 ซึ่งอาจเป็นเส้นทาง $5 → 2 → 1 → 4 → 7$ หรือ $6 → 2 → 1 → 4 → 7$ เนื่องจากมีหลายเส้นทางที่มีความยาวสูงสุดเท่ากัน

### 4.1 การใช้ DP สำหรับการค่าเส้นผ่านศูนย์กลางของต้นไม้
แนวทางการแก้ปัญหาในต้นไม้ที่นิยมใช้ คือ การกำหนดรากของต้นไม้โดยสุ่ม (Rooting the Tree arbitrarily) และคำนวณค่าต่าง ๆ แยกกันในแต่ละ Subtree เมื่อเรากำหนดรากของต้นไม้แล้ว เราสามารถคำนวณคุณสมบัติต่าง ๆ ของโหนดในต้นไม้ได้อย่างมีประสิทธิภาพ

**กระบวนการ**
เราสามารถ คำนวณค่าที่สำคัญสองค่า สำหรับแต่ละโหนด x:
- `toLeaf(x):` ความยาวสูงสุดของเส้นทางจาก x ไปยังโหนดใบ (Leaf Node) ใด ๆ
- ใช้ DFS คำนวณ `toLeaf[u] = max(toLeaf[v]) + 1` โดย `v` คือโหนดลูกที่อยู่ติดกับ `u`
- `maxLength(x):` ความยาวสูงสุดของเส้นทางที่มี x เป็นโหนดสูงสุด (Highest Point)
- ถ้าโหนด `u` มีลูกหลายตัว ให้นำ `toLeaf` ของลูกที่มีค่ามากที่สุด 2 ตัวมาบวกกัน
- ค่า `maxLength[u]` จะเป็นเส้นผ่านศูนย์กลางที่มี `u` เป็นโหนดสูงสุด

ตัวอย่าง

**toLeaf(x):**
- toLeaf(5) = 0, toLeaf(6) = 0, toLeaf(7) = 0 (เพราะเป็น Leaf)
- toLeaf(2) = max(toLeaf(5), toLeaf(6)) + 1 = 1
- toLeaf(4) = toLeaf(7) + 1 = 1
- toLeaf(1) = max(toLeaf(2), toLeaf(3), toLeaf(4)) + 1 = 2

**maxLength(x):**
maxLength(1) = toLeaf(2) + toLeaf(4) + 2 = 4 (เป็นเส้นผ่านศูนย์กลางของต้นไม้)

**ข้อสังเกต**
- วิธีนี้ใช้แนวคิด Rooting the Tree แล้วคำนวณค่าต่าง ๆ ของแต่ละโหนดแยกกัน
- ใช้ Tree DP เพื่อคำนวณ toLeaf(x) และ maxLength(x) ผ่าน DFS
- ทำงานใน $O(n)$ เพราะมีการเยี่ยมชมโหนดแต่ละตัวเพียง 1 ครั้ง

**ตัวอย่างโปรแกรม**

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];  // Adjacency list
int toLeaf[N], maxLength[N];  // เก็บค่าต่าง ๆ สำหรับแต่ละโหนด
int diameter = 0;

void dfs(int u, int parent) {
    vector<int> childLengths;  // เก็บค่าของ `toLeaf` ของลูกแต่ละตัว
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        toLeaf[u] = max(toLeaf[u], toLeaf[v] + 1);
        childLengths.push_back(toLeaf[v] + 1);
    }

    // ถ้ามีลูกมากกว่า 2 ให้เรียงลำดับหา 2 ค่ามากสุด
    if (childLengths.size() >= 2) {
        sort(childLengths.rbegin(), childLengths.rend());  // เรียงจากมากไปน้อย
        maxLength[u] = childLengths[0] + childLengths[1];  // เอาสองค่ามากสุดมาบวกกัน
    } else if (!childLengths.empty()) {
        maxLength[u] = childLengths[0];
    }

    // อัปเดตค่าเส้นผ่านศูนย์กลางของต้นไม้
    diameter = max(diameter, maxLength[u]);
}

int main() {
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);  // เริ่ม DFS ที่โหนดราก (สมมติให้เป็นโหนด 1)
    cout << "Diameter of the tree: " << diameter << "\n";
    return 0;
}

### 4.2 การหาค่าเส้นผ่านศูนย์กลางของต้นไม้โดยใช้ DFS สองครั้ง
อัลกอริทึม DFS 2 ครั้งสามารถหาเส้นผ่านศูนย์กลางของต้นไม้ได้เพราะอาศัยหลักการที่ว่าโหนดที่อยู่ไกลที่สุดจากโหนดเริ่มต้นต้องเป็นจุดปลายด้านหนึ่งของเส้นผ่านศูนย์กลางของต้นไม้ โดยเริ่มจากการเลือกโหนด a แบบสุ่มและใช้ DFS ครั้งที่หนึ่งเพื่อหาโหนด b ที่อยู่ไกลที่สุดจาก a ซึ่งรับประกันได้ว่า b ต้องเป็นส่วนหนึ่งของเส้นผ่านศูนย์กลาง จากนั้นใช้ DFS ครั้งที่สองเริ่มจาก b เพื่อหาโหนด c ที่อยู่ไกลที่สุด ซึ่ง c จะต้องเป็นปลายอีกด้านหนึ่งของเส้นผ่านศูนย์กลางเสมอ

**กระบวนการ**
1. เลือกโหนด a ใด ๆ เป็นจุดเริ่มต้น และใช้ Depth-First Search (DFS) เพื่อหาว่า โหนด b ที่อยู่ไกลที่สุดจาก a คืออะไร
2. ใช้ DFS อีกครั้งจาก b เพื่อหา โหนด c ที่อยู่ไกลที่สุดจาก b
3. ค่าระยะทางจาก b ไป c คือเส้นผ่านศูนย์กลางของต้นไม้

ตัวอย่าง

**ตัวอย่างโปรแกรม**

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int farthestNode, maxDistance;

// DFS เพื่อหาโหนดที่อยู่ไกลที่สุด
void dfs(int u, int parent, int depth) {
    if (depth > maxDistance) {
        maxDistance = depth;
        farthestNode = u;
    }
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u, depth + 1);
    }
}

int findTreeDiameter(int start) {
    maxDistance = -1;
    dfs(start, -1, 0);  // DFS ครั้งที่ 1 หาค่า farthestNode (โหนด b)

    maxDistance = -1;
    dfs(farthestNode, -1, 0);  // DFS ครั้งที่ 2 จากโหนด b เพื่อหาโหนด c และเส้นผ่านศูนย์กลาง
    return maxDistance;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << "Diameter of the tree: " << findTreeDiameter(1) << "\n";
    return 0;
}

## ตัวอย่างโจทย์
- https://leetcode.com/problems/diameter-of-binary-tree/description/

# 5. ต้นไม้ทวิภาค (Binary Tree)
ต้นไม้ทวิภาค (Binary Tree) เป็นต้นไม้แบบมีราก (Rooted Tree) ที่แต่ละโหนดมีโหนดลูกได้ไม่เกินสองโหนด ซึ่งประกอบด้วย ซ้าย (Left Subtree) และ ขวา (Right Subtree) โดยอาจเป็นไปได้ว่าโหนดลูกใดลูกหนึ่งหรือทั้งสองอาจว่างเปล่า (ไม่มีโหนดลูกเลย) ดังนั้นแต่ละโหนดในต้นไม้ทวิภาคสามารถมีลูกได้ 0, 1 หรือ 2 โหนดเท่านั้น

ตัวอย่าง

## 5.1 ประเภทของต้นไม้ทวิภาค

**ต้นไม้ทวิภาคแบบเต็ม (Full Binary Tree)** คือ ต้นไม้ทวิภาคที่ทุกโหนดจะต้องมีลูกสองโหนดหรือไม่มีลูกเลย กล่าวคือ ไม่มีโหนดใดที่มีลูกเพียงโหนดเดียว ต้นไม้ประเภทนี้มักใช้ในโครงสร้างข้อมูลที่ต้องการความเป็นระเบียบและช่วยให้การทำงานของอัลกอริทึมที่เกี่ยวข้องกับต้นไม้มีประสิทธิภาพมากขึ้น

**ต้นไม้ทวิภาคแบบสมบูรณ์ (Complete Binary Tree)** เป็นต้นไม้ทวิภาคที่ทุกระดับของต้นไม้จะต้องเต็ม ยกเว้นระดับสุดท้ายซึ่งอาจไม่เต็ม แต่ต้องเติมจากซ้ายไปขวาให้มากที่สุด ต้นไม้ประเภทนี้นิยมใช้ในการสร้าง Heap ซึ่งเป็นโครงสร้างข้อมูลที่ใช้จัดลำดับความสำคัญ (Priority Queue) เนื่องจากการแทรกและการลบโหนดสามารถทำได้ในเวลา $O(\log n)$

**ต้นไม้ทวิภาคแบบสมบูรณ์แบบ (Perfect Binary Tree)** คือ ต้นไม้ที่ทุกโหนดภายใน (Internal Nodes) มีลูกสองโหนดทั้งหมด และทุกโหนดใบ (Leaf Nodes) อยู่ในระดับเดียวกัน ต้นไม้ประเภทนี้มีโครงสร้างที่สมดุลอย่างสมบูรณ์และมักใช้ในอัลกอริทึมที่ต้องการความสม่ำเสมอของโครงสร้างต้นไม้ เช่น Divide and Conquer Algorithm ซึ่งอาศัยการแบ่งปัญหาออกเป็นส่วน ๆ ที่มีขนาดเท่ากัน

**ต้นไม้ทวิภาคแบบสมดุล (Balanced Binary Tree)** เป็นต้นไม้ทวิภาคที่มีความสูงของซับทรีฝั่งซ้ายและฝั่งขวาแตกต่างกันไม่เกิน 1 เพื่อให้สามารถดำเนินการต่าง ๆ เช่น ค้นหา (Search), แทรก (Insert) และลบ (Delete) ได้ในเวลา $O(\log n)$ ต้นไม้ประเภทนี้ถูกนำไปใช้ใน **AVL Tree** และ **Red-Black Tree** ซึ่งเป็นต้นไม้ที่สามารถปรับสมดุลได้อัตโนมัติเมื่อมีการแทรกหรือลบข้อมูล ทำให้ต้นไม้ยังคงมีโครงสร้างที่เหมาะสมสำหรับการดำเนินการต่าง ๆ

**ต้นไม้ทวิภาคแบบเสื่อม (Degenerate Binary Tree)** หรือที่เรียกอีกชื่อว่า ต้นไม้เอนเอียง (Skewed Tree) เป็นต้นไม้ที่แต่ละโหนดมีลูกเพียงโหนดเดียวเท่านั้น อาจเป็นลูกฝั่งซ้ายทั้งหมดหรือฝั่งขวาทั้งหมด ทำให้ต้นไม้มีโครงสร้างคล้ายกับ Linked List ซึ่งส่งผลให้การดำเนินการต่าง ๆ เช่น การค้นหาใช้เวลา $O(n)$ ในกรณีที่แย่ที่สุด ต้นไม้ประเภทนี้มักเกิดจากการแทรกข้อมูลใน Binary Search Tree (BST) โดยไม่มีการบาลานซ์โครงสร้าง ดังนั้นต้นไม้ที่สมดุลเช่น AVL Tree และ Red-Black Tree จึงถูกนำมาใช้เพื่อแก้ปัญหานี้

## 5.2 การแทนต้นไม้ทวิภาค (Binary Tree Representation)
ต้นไม้ทวิภาค (Binary Tree) สามารถแทนอยู่ในหน่วยความจำของคอมพิวเตอร์ได้หลายวิธี โดยทั่วไปสามารถแบ่งออกเป็นสองแนวทางหลัก ได้แก่ การใช้โครงสร้างข้อมูลแบบลิงก์ (Linked Representation) และ การใช้อาร์เรย์ (Array Representation) แต่ละวิธีมีข้อดีและข้อเสียที่แตกต่างกันตามลักษณะของปัญหาที่ต้องการแก้ไข

### 5.2.1 การแทนต้นไม้ทวิภาคด้วยโครงสร้างข้อมูลแบบเชื่อมต่อ (Linked Representation)
วิธีนี้ใช้โครงสร้างแบบ โหนด (Node) ซึ่งมีพอยน์เตอร์ชี้ไปยังลูกซ้ายและลูกขวาของแต่ละโหนด โครงสร้างพื้นฐานของโหนดในต้นไม้ทวิภาคสามารถนิยามได้ดังนี้

struct Node {
    int data;       // ข้อมูลที่เก็บในโหนด
    Node* left;     // พอยน์เตอร์ชี้ไปยังลูกซ้าย
    Node* right;    // พอยน์เตอร์ชี้ไปยังลูกขวา

    Node(int val) { // คอนสตรักเตอร์กำหนดค่าเริ่มต้น
        data = val;
        left = right = nullptr;
    }
};

การสร้างต้นไม้สามารถทำได้โดยการกำหนดค่าของรากและเชื่อมโยงลูกซ้ายและลูกขวาแบบไดนามิก เช่น

int main() {
    Node* root = new Node(1);  // สร้างรากของต้นไม้
    root->left = new Node(2);  // สร้างลูกซ้ายของราก
    root->right = new Node(3); // สร้างลูกขวาของราก
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);

    return 0;
}

**ข้อดีของการใช้โครงสร้างแบบลิงก์**
- มีความยืดหยุ่นสูง สามารถปรับขนาดของต้นไม้ได้โดยไม่มีข้อจำกัดด้านหน่วยความจำที่ต่อเนื่อง
- รองรับต้นไม้ที่ไม่สมบูรณ์ ต้นไม้ที่มีโหนดบางส่วนว่างเปล่าสามารถแทนได้อย่างมีประสิทธิภาพ
- รองรับการเปลี่ยนแปลงโครงสร้าง การเพิ่มหรือลบโหนดทำได้สะดวกโดยไม่ต้องเลื่อนข้อมูลในอาร์เรย์

**ข้อเสีย**
- ใช้หน่วยความจำมากกว่าวิธีอาร์เรย์ เนื่องจากต้องเก็บพอยน์เตอร์เพิ่มเติม
- เข้าถึงข้อมูลแบบสุ่ม (Random Access) ทำได้ช้ากว่าอาร์เรย์

### 5.2.2 การแทนต้นไม้ทวิภาคด้วยอาร์เรย์ (Array Representation)
วิธีนี้ใช้ อาร์เรย์ (Array) แทนต้นไม้โดยกำหนดให้รากอยู่ที่ดัชนีที่ 1 หรือ 0 แล้วใช้กฎต่อไปนี้เพื่อกำหนดความสัมพันธ์ระหว่างโหนดพ่อแม่กับลูก

โหนดพ่อแม่ที่ตำแหน่ง i
- ลูกซ้ายอยู่ที่ ตำแหน่ง 2*i + 1
- ลูกขวาอยู่ที่ ตำแหน่ง 2*i + 2

โหนดลูกที่ดัชนี j
- โหนดพ่อแม่อยู่ที่ ตำแหน่ง (j-1)/2

ตัวอย่างโครงสร้างของต้นไม้ที่แทนด้วยอาร์เรย์

#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // ขนาดสูงสุดของต้นไม้

int tree[MAX_SIZE];

// ฟังก์ชันแทรกโหนดที่ตำแหน่ง i
void insert(int i, int value) {
    if (i < MAX_SIZE)
        tree[i] = value;
}

// แสดงค่าของต้นไม้ที่ถูกแทนในอาร์เรย์
void printTree(int n) {
    for (int i = 0; i < n; i++)
        cout << tree[i] << " ";
    cout << endl;
}

int main() {
    insert(0, 1); // ราก
    insert(1, 2); // ลูกซ้ายของราก
    insert(2, 3); // ลูกขวาของราก
    insert(3, 4); // ลูกซ้ายของโหนดที่ 2
    insert(4, 5); // ลูกขวาของโหนดที่ 2
    insert(6, 6); // ลูกขวาของโหนดที่ 3

    printTree(7);
    return 0;
}

### 5.2.3 การเปรียบเทียบระหว่างการแทนต้นไม้
| คุณสมบัติ | โครงสร้างลิงก์ (Linked Representation) | อาร์เรย์ (Array Representation) |
|-------------------|--------------------------------|--------------------------------|
| **การใช้หน่วยความจำ** | ใช้พอยน์เตอร์เพิ่มหน่วยความจำมากขึ้น | ใช้หน่วยความจำอย่างมีประสิทธิภาพหากต้นไม้เต็ม |
| **การเข้าถึงข้อมูล** | ต้องใช้การค้นหาแบบ DFS หรือ BFS | สามารถเข้าถึงข้อมูลได้โดยใช้ตำแหน่ง |
| **ความเร็วในการดำเนินการ** | เพิ่ม/ลบโหนดได้เร็ว แต่ค้นหาช้ากว่าอาร์เรย์ | เข้าถึงข้อมูลเร็ว แต่เพิ่ม/ลบโหนดยาก |

## 5.3 การเรียงลำดับโหนดในต้นไม้ทวิภาค (Tree Traversal)
ต้นไม้ทวิภาคสามารถทำการเยี่ยมชมโหนดได้สามแบบหลัก ซึ่งแตกต่างกันตามลำดับการดำเนินการ:

**1. Pre-order Traversal (ก่อนลำดับ)**
ดำเนินการที่โหนดรากก่อน → เยี่ยมชมซับทรีทางซ้าย → เยี่ยมชมซับทรีทางขวา
ลำดับของโหนด: [1, 2, 4, 5, 6, 3, 7]
**2. In-order Traversal (กลางลำดับ)**
เยี่ยมชมซับทรีทางซ้ายก่อน → ดำเนินการที่โหนดราก → เยี่ยมชมซับทรีทางขวา
ลำดับของโหนด: [4, 2, 6, 5, 1, 3, 7]
**3. Post-order Traversal (หลังลำดับ)**
เยี่ยมชมซับทรีทางซ้าย → เยี่ยมชมซับทรีทางขวา → ดำเนินการที่โหนดราก
ลำดับของโหนด: [4, 6, 5, 2, 7, 3, 1]

ตัวอย่าง

**ตัวอย่างโปรแกรม**

#include <iostream>
using namespace std;

// โครงสร้างของโหนดใน Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

// ฟังก์ชัน Pre-order Traversal
void preOrder(Node* root) {
    if (!root) return;
    cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// ฟังก์ชัน In-order Traversal
void inOrder(Node* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->data << " ";
    inOrder(root->right);
}

// ฟังก์ชัน Post-order Traversal
void postOrder(Node* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << " ";
}

int main() {
    // สร้าง Binary Tree ตามตัวอย่าง
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);
    root->left->right->left = new Node(6);

    cout << "Pre-order Traversal: ";
    preOrder(root);
    cout << "\n";

    cout << "In-order Traversal: ";
    inOrder(root);
    cout << "\n";

    cout << "Post-order Traversal: ";
    postOrder(root);
    cout << "\n";

    return 0;
}

## 5.4 Binary Search Tree (BST)
Binary Search Tree (BST) เป็นโครงสร้างข้อมูลต้นไม้ทวิภาคที่มีคุณสมบัติพิเศษเพิ่มเติม คือ:
- ค่าของโหนดซ้าย (Left Subtree) ต้องน้อยกว่าค่าของโหนดปัจจุบัน
- ค่าของโหนดขวา (Right Subtree) ต้องมากกว่าค่าของโหนดปัจจุบัน
- กฎนี้ต้องเป็นจริงสำหรับทุกโหนดในต้นไม้

ตัวอย่าง


BST เป็นโครงสร้างข้อมูลที่มีประโยชน์ในการค้นหาข้อมูลอย่างมีประสิทธิภาพ โดยใช้กฎที่ว่า ค่าทางซ้ายต้องน้อยกว่าโหนดปัจจุบัน และค่าทางขวาต้องมากกว่าโหนดปัจจุบัน ซึ่งช่วยให้การแทรก, ค้นหา และลบข้อมูลเป็นไปได้อย่างรวดเร็วในเวลาเฉลี่ย $O(\log n)$ อย่างไรก็ตาม หาก BST ไม่สมดุล จะมีประสิทธิภาพลดลงเหลือ $O(n)$ ในกรณีที่แย่ที่สุด

## ตัวอย่างโจทย์
- https://leetcode.com/problems/binary-tree-inorder-traversal/
- https://leetcode.com/problems/same-tree/description/
- https://leetcode.com/problems/maximum-depth-of-binary-tree
- https://leetcode.com/problems/balanced-binary-tree/
- https://leetcode.com/problems/merge-two-binary-trees/description/

# อ้างอิง

- https://cses.fi/book/book.pdf
- https://github.com/tchomphoochan/toi14-tutorial/tree/master
- https://visualgo.net/en
- https://programming.in.th/