เขียนโปรแกรมคำนวณขนาดของต้นไม้ (Tree Size) ด้วย Recursion (C++)

โจทย์

ได้รับต้นไม้ (Tree) ต้องการเขียนโปรแกรมคำนวณขนาดของต้นไม้ (Size of Tree) โดยใช้ Recursion

นิยาม

ขนาดของต้นไม้ (Tree Size) = จำนวนโหนด (nodes) ทั้งหมดในต้นไม้

ตัวอย่าง

ต้นไม้ข้างต้นมีขนาด 5 โหนด

วิธีแก้ปัญหา (Recursive)

ขนาดของต้นไม้ที่รากเป็น node = ขนาด subtree ซ้าย + ขนาด subtree ขวา + 1 (นับรากตัวเอง)

size(node) = size(node->left) + size(node->right) + 1
Base case: size(nullptr) = 0

ตัวอย่างการคำนวณ

size(3) = size(5) + size(7) + 1
size(3) = (size(1) + size(9) + 1) + 1 + 1
size(3) = (1 + 1 + 1) + 1 + 1 = 5

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
};

Node* insertNode(int data) {
    Node* node = new Node();
    node->data = data;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

int findSize(Node* node) {
    if (node == nullptr) return 0;
    return findSize(node->left) + 1 + findSize(node->right);
}

int main() {
    Node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(7);
    root->left->left = insertNode(1);
    root->left->right = insertNode(5);
    root->right->left = insertNode(2);
    //       6
    //      / \
    //     3   7
    //    / \  /
    //   1  5 2
    
    cout << "The size of the given tree is " << findSize(root);
    return 0;
}

ผลลัพธ์

The size of the given tree is 6

Complexity

• Time: O(N) - เข้าชมทุกโหนดครั้งเดียว
• Space: O(H) - H = ความสูงของต้นไม้ (recursion stack), worst case O(N) สำหรับ skewed tree

Iterative Version (หลีกเลี่ยง Stack Overflow)

int findSizeIterative(Node* root) {
    if (!root) return 0;
    
    queue<Node*> q;
    q.push(root);
    int count = 0;
    
    while (!q.empty()) {
        Node* curr = q.front(); q.pop();
        count++;
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
    return count;
}

สรุป

Recursive approach สำหรับ Tree Size เข้าใจง่าย สั้น กระชับ เหมาะสำหรับต้นไม้ที่ไม่ลึกเกินไป (H < 10⁴-10⁵) สำหรับต้นไม้ลึกมาก ควรใช้ iterative BFS/DFS แทน