Giả sử chúng ta có một số nguyên dương L, đại diện cho số mức trong một cây nhị phân hoàn hảo. Các nút lá trong cây nhị phân hoàn hảo này được đánh số bắt đầu từ 1 đến n. Trong đó n là số nút lá. Nút cha là tổng của nút con. Nhiệm vụ của chúng ta là viết một chương trình để in ra tổng tất cả các nút của cây nhị phân hoàn hảo này. Vì vậy, nếu cây như dưới đây -
Vậy tổng cộng là 30.
Nếu chúng ta thấy gần hơn, chúng ta cần tìm tổng của tất cả các nút. Vì các nút lá đang giữ các giá trị từ 1 đến n, thì chúng ta có thể sử dụng công thức n (n + 1) / 2 để tính tổng các nút lá. Vì đây là cây nhị phân hoàn hảo nên tổng của mỗi cấp sẽ giống nhau. Vì vậy, hãy tìm tổng của cấp độ cuối cùng, sau đó nhân nó với số cấp độ.
Ví dụ
#include<iostream>
#include<cmath>
using namespace std;
int treeSum(int level) {
int total_leaves = pow(2, level - 1);
int leaf_sum = 0;
leaf_sum = (total_leaves * (total_leaves + 1)) / 2;
int sum = leaf_sum * level;
return sum;
}
int main() {
int levels = 4;
cout << "Sum of all nodes for a perfect binary tree with level " << levels << " is: " << treeSum(levels);
} Đầu ra
Sum of all nodes for a perfect binary tree with level 4 is: 144