Tính tổng tất cả nút của cây nhị phân hoàn hảo trong C++

Cho cây nhị phân hoàn hảo L cấp. Các lá được đánh số 1 đến n (n = 2^{L-1}). Nút cha = tổng hai con. Tính tổng tất cả nút.

Tổng lá = n(n+1)/2. Vì cây hoàn hảo, tổng mỗi cấp bằng nhau. Tổng toàn cây = tổng lá × số cấp L.

Ví dụ

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

int treeSum(int level) {
    int total_leaves = pow(2, level - 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);
}

Kết quả

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