ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা L আছে, যা একটি নিখুঁত বাইনারি গাছের স্তরের সংখ্যাকে প্রতিনিধিত্ব করে। এই নিখুঁত বাইনারি গাছের পাতার নোডগুলি 1 থেকে n পর্যন্ত সংখ্যাযুক্ত। যেখানে n হল পাতার নোডের সংখ্যা। প্যারেন্ট নোড হল শিশুদের সমষ্টি। আমাদের কাজ হল এই নিখুঁত বাইনারি গাছের সমস্ত নোডের যোগফল প্রিন্ট করার জন্য একটি প্রোগ্রাম লেখা। তাই যদি গাছটি নিচের মত হয় -
সুতরাং মোট যোগফল 30।
যদি আমরা কাছাকাছি দেখি, আমাদের সমস্ত নোডের যোগফল খুঁজে বের করতে হবে। যেহেতু লিফ নোডগুলি 1 থেকে n পর্যন্ত মান ধারণ করে, তাই আমরা লিফ নোডের যোগফল পেতে n(n+1)/2 সূত্রটি ব্যবহার করতে পারি। যেহেতু এটি নিখুঁত বাইনারি গাছ, তাই প্রতিটি স্তরের যোগফল একই হবে। তাই শেষ স্তরের যোগফল বের করুন, তারপর এটিকে স্তরের সংখ্যা দিয়ে গুণ করুন।
উদাহরণ
#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);
} আউটপুট
Sum of all nodes for a perfect binary tree with level 4 is: 144
