완전한 이진 트리의 수준 수를 나타내는 양의 정수 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