หาผลรวมโหนดทั้งหมดของ Perfect Binary Tree ใน C++

Perfect Binary Tree ระดับ L ใบไม้ (Leaves) หมายเลข 1 ถึง n (n = 2^(L-1)) โหนดพาเรนต์ = ผลรวมลูก หาผลรวมโหนดทั้งหมด

ข้อสังเกตสำคัญ

• ผลรวมใบไม้ = 1 + 2 + ... + n = n(n+1)/2
• ใน Perfect Binary Tree ผลรวมแต่ละระดับเท่ากัน (เพราะแต่ละโหนด = ผลรวมลูก 2 ตัว)
• มีทั้งหมด L ระดับ → ผลรวมทั้งหมด = L × n(n+1)/2

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

#include <iostream>
#include <cmath>
using namespace std;

int treeSum(int level) {
    int total_leaves = pow(2, level - 1); // 2^(L-1)
    int leaf_sum = total_leaves * (total_leaves + 1) / 2;
    return leaf_sum * level;
}

int main() {
    int levels = 4;
    cout << "Sum of all nodes for a perfect binary tree with level "
         << levels << " is: " << treeSum(levels);
    return 0;
}

ผลลัพธ์

Sum of all nodes for a perfect binary tree with level 4 is: 144

การตรวจสอบ (L=4)

• Leaves: 2³ = 8 ใบ → ผลรวม = 8×9/2 = 36
• ระดับ 3: 4 โหนด → ผลรวม = 36
• ระดับ 2: 2 โหนด → ผลรวม = 36
• ระดับ 1 (Root): 1 โหนด → ผลรวม = 36
• รวม = 36 × 4 = 144 ✓

หมายเหตุ

โค้ดต้นฉบับใช้ loop i < 8 แทน i < n (n=6) เราแก้ไขให้ถูกต้อง