हमें एक बाइनरी ट्री दिया गया है और कार्य बाइनरी ट्री में उपलब्ध नॉन-लीफ नोड्स की संख्या की गणना करना है।
बाइनरी ट्री डेटा संग्रहण उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है। एक बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं। एक बाइनरी ट्री में एक क्रमबद्ध सरणी और एक लिंक्ड सूची दोनों के लाभ होते हैं क्योंकि खोज एक क्रमबद्ध सरणी की तरह तेज होती है और सम्मिलन या विलोपन ऑपरेशन लिंक्ड सूची की तरह तेज होते हैं। नॉन-लीफ नोड्स को पैरेंट नोड्स के रूप में भी जाना जाता है क्योंकि उनके 0 से अधिक बच्चे होते हैं और दो से कम बच्चे होते हैं।
बाइनरी ट्री की संरचना नीचे दी गई है -
उदाहरण के लिए
इनपुट -
आउटपुट - नॉन-लीफ नोड्स की गिनती: 3
व्याख्या - दिए गए ट्री में, हमारे पास 27, 14 और 35 नॉन-लीफ नोड्स के रूप में हैं क्योंकि उनके 0 से अधिक बच्चे हैं और 2 से कम बच्चे हैं।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
बाइनरी ट्री की संरचना बनाएं जिसमें बाएं नोड का पॉइंटर, दाएं नोड का पॉइंटर और एक नोड में संग्रहीत डेटा भाग हो
एक फंक्शन बनाएं जो नोड को इन्सर्ट करेगा जब भी यह फंक्शन कॉल किया जाएगा। इसके लिए, नए नोड में डेटा इन्सर्ट करें और नए नोड के दाएं और बाएं पॉइंटर को NULL पर सेट करें और नोड लौटाएं।
एक रिकर्सिव फंक्शन बनाएं जो बाइनरी ट्री में नॉन-लीफ नोड्स की संख्या गिनेगा।
- जांचें कि क्या रूट NULL है या रूट का बायां NULL है और रूट का दायां NULL है तो 0 लौटाएं
- 1 + इस फंक्शन को बाएं पॉइंटर के साथ रिकर्सिव कॉल + इस फंक्शन को दाएं पॉइंटर के साथ रिकर्सिव कॉल लौटाएं
गिनती प्रिंट करें
उदाहरण
#include <iostream>
using namespace std;
// नोड की संरचना
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// नए नोड को परिभाषित करने के लिए
struct Node* newNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// नॉन-लीफ नोड्स गिनें
int nonleaf(struct Node* root) {
if (root == NULL || (root->left == NULL && root->right == NULL)) {
return 0;
}
return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// मुख्य फंक्शन
int main() {
struct Node* root = newNode(10);
root->left = newNode(21);
root->right = newNode(33);
root->left->left = newNode(48);
root->left->right = newNode(51);
cout << nonleaf(root);
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
count of non-leaf nodes is: 2
