C++で与えられた完全な二分木のすべてのノードの合計を見つけます

完全な二分木のレベル数を表す正の整数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