मान लीजिए कि हमारे पास एक सकारात्मक पूर्णांक 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