สมมติว่าเรามีจำนวนเต็มบวก 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
