โปรแกรมหาผลคูณทุกโหนดใน Binary Tree ด้วย C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลคูณของค่าข้อมูล (data) ของทุกโหนดใน Binary Tree โดยใช้การท่องต้นไม้แบบ Recursive (DFS)

โครงสร้าง Binary Tree Node

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

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

ผลคูณของต้นไม้ = (ค่าราก) × (ผลคูณซับทรีซ้าย) × (ผลคูณซับทรีขวา)

Base case: ถ้าโหนดเป็น NULL คืนค่า 1 (เอกเอกของการคูณ)

ฟังก์ชันคำนวณผลคูณ (Recursive)

long long productOfAllNodes(Node* root) {
    if (root == nullptr) return 1;  // Base case
    
    return static_cast(root->data) * 
           productOfAllNodes(root->left) * 
           productOfAllNodes(root->right);
}

ฟังก์ชันสร้างโหนดใหม่

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

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

#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;
}

long long productOfAllNodes(Node* root) {
    if (root == nullptr) return 1;
    return static_cast(root->data) * 
           productOfAllNodes(root->left) * 
           productOfAllNodes(root->right);
}

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

int main() {
    // สร้างต้นไม้:
    //        10
    //       /  \
    //      20   30
    //     / \   / \
    //    40 50 60  70
    
    Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(40);
    root->left->right = createNode(50);
    root->right->left = createNode(60);
    root->right->right = createNode(70);
    
    cout << "Binary Tree Structure:\n";
    printTree(root);
    
    long long product = productOfAllNodes(root);
    cout << "\nProduct of all nodes = " << product << endl;
    
    // ตรวจสอบ: 10×20×30×40×50×60×70 = 504,000,000
    cout << "Verification: 10*20*30*40*50*60*70 = " << 10LL*20*30*40*50*60*70 << endl;
    
    return 0;
}

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

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

Product of all nodes = 504000000
Verification: 10*20*30*40*50*60*70 = 504000000

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

ต้นฉบับมีต้นไม้: 10, 20, 30, 40, 50, 60 (6 โหนด)

Product = 10 × 20 × 30 × 40 × 50 × 60 = 720,000,000

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

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

การท่องต้นไม้อื่นๆ ที่ใช้ได้

ทุกวิธีให้ผลลัพธ์เดียวกันเพราะการคูณมีคุณสมบัติการสลับที่ได้ (Commutative)

ข้อควรระวัง

• ใช้ long long ป้องกัน overflow สำหรับต้นไม้ขนาดเล็ก-ปานกลาง
• ต้นไม้ขนาดใหญ่หรือค่าข้อมูลใหญ่ ควรใช้ Big Integer หรือ Modulo
• Base case คืนค่า 1 ไม่ใช่ 0 (เพราะ 0 จะทำให้ผลคูณทั้งหมดเป็น 0)