โปรแกรมหาผลคูณโหนดใบ (Leaf Nodes) ใน Binary Tree ด้วย C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลคูณของ โหนดใบ (Leaf Nodes) ใน Binary Tree โหนดใบคือโหนดที่ไม่มีลูก (left และ right เป็น NULL ทั้งคู่)

นิยามโหนดใบ (Leaf Node)

Leaf Node: node->left == nullptr && node->right == nullptr

หลักการทำงาน

ท่องต้นไม้ทุกโหนด (DFS) เมื่อเจอโหนดใบ ให้นำค่าข้อมูลไปคูณสะสม

ฟังก์ชันคำนวณผลคูณโหนดใบ

void productOfLeafNodes(Node* root, long long& product) {
    if (root == nullptr) return;
    
    // ตรวจสอบว่าเป็นโหนดใบหรือไม่
    if (root->left == nullptr && root->right == nullptr) {
        product *= root->data;
        return;
    }
    
    // ท่องต่อซับทรีซ้ายและขวา
    productOfLeafNodes(root->left, product);
    productOfLeafNodes(root->right, product);
}

โปรแกรมสมบูรณ์พร้อมทดสอบ

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

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

void productOfLeafNodes(Node* root, long long& product) {
    if (!root) return;
    if (!root->left && !root->right) {
        product *= root->data;
        return;
    }
    productOfLeafNodes(root->left, product);
    productOfLeafNodes(root->right, product);
}

void printTree(Node* root, string prefix = "", bool isLeft = true) {
    if (!root) return;
    cout << prefix << (isLeft ? "├── " : "└── ") << root->data << endl;
    printTree(root->left, prefix + (isLeft ? "│   " : "    "), true);
    printTree(root->right, prefix + (isLeft ? "│   " : "    "), false);
}

int main() {
    // สร้างต้นไม้จากตัวอย่าง:
    //        10
    //       /  \
    //      20   50
    //     / \   / \
    //    30 40 70 60
    
    Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(50);
    root->left->left = createNode(30);
    root->left->right = createNode(40);
    root->right->left = createNode(70);
    root->right->right = createNode(60);
    
    cout << "Binary Tree Structure:\n";
    printTree(root);
    
    // ระบุโหนดใบ
    cout << "\nLeaf nodes: ";
    // ฟังก์ชันช่วยพิมพ์โหนดใบ
    function printLeaves = [&](Node* node) {
        if (!node) return;
        if (!node->left && !node->right) cout << node->data << " ";
        printLeaves(node->left);
        printLeaves(node->right);
    };
    printLeaves(root);
    cout << endl;
    
    long long product = 1;
    productOfLeafNodes(root, product);
    cout << "Product of leaf nodes = " << product << endl;
    
    // ตรวจสอบ: 30 × 40 × 70 × 60 = 5,040,000
    cout << "Verification: 30*40*70*60 = " << 30LL*40*70*60 << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Binary Tree Structure:
├── 10
│   ├── 20
│   │   ├── 30
│   │   └── 40
│   └── 50
│       ├── 70
│       └── 60

Leaf nodes: 30 40 70 60 
Product of leaf nodes = 5040000
Verification: 30*40*70*60 = 5040000

ตัวอย่างจากโจทย์ต้นฉบับ

โจทย์ต้นฉบับมีโหนดใบ: 23, 34, 25

Product = 23 × 34 × 25 = 19,550

ความแตกต่างระหว่าง "ทุกโหนด" และ "โหนดใบ"

ความซับซ้อนของอัลกอริทึม

• เวลา: O(N) - เยี่ยมชมทุกโหนดครั้งเดียว
• พื้นที่: O(H) - ความลึกของ recursion stack (H = ความสูงต้นไม้)

วิธีการท่องแบบ Iterative (ใช้ Stack)

long long productOfLeavesIterative(Node* root) {
    if (!root) return 1;
    long long product = 1;
    stack st;
    st.push(root);
    
    while (!st.empty()) {
        Node* curr = st.top(); st.pop();
        if (!curr->left && !curr->right) {
            product *= curr->data;
        }
        if (curr->right) st.push(curr->right);
        if (curr->left) st.push(curr->left);
    }
    return product;
}

ประยุกต์ใช้

• การคำนวณคุณสมบัติของต้นไม้
• การบีบอัดข้อมูล (Huffman coding - ใบคือตัวอักษร)
• การวิเคราะห์โครงสร้างข้อมูลแบบลำดับชั้น