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