हमें एक बाइनरी ट्री दिया गया है और कार्य बाइनरी ट्री में उपलब्ध पूर्ण नोड्स की संख्या की गणना करना है इटरेटिव और रिकर्सिव दृष्टिकोण का उपयोग करके। पूर्ण नोड्स वे नोड्स हैं जिनके दोनों बच्चे हैं और कोई बच्चा null नहीं है। ध्यान दें कि पूर्ण नोड्स में हम ठीक दो बच्चों वाले नोड्स पर विचार करते हैं।
बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है। एक बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं। एक बाइनरी ट्री में एक क्रमबद्ध ऐरे और एक लिंक्ड लिस्ट दोनों के लाभ होते हैं क्योंकि खोज क्रमबद्ध ऐरे की तरह तेज़ होती है और सम्मिलन या विलोपन ऑपरेशन लिंक्ड लिस्ट की तरह तेज़ होते हैं। नॉन-लीफ नोड्स को पैरेंट नोड्स के रूप में भी जाना जाता है क्योंकि उनके 0 से अधिक बच्चे होते हैं और दो से कम बच्चे होते हैं।
उदाहरण
इनपुट: बाइनरी ट्री की छवि
आउटपुट: count is 2
व्याख्या: दिए गए ट्री में 2 नोड्स यानी 10 और 20 हैं जिनके ठीक दो बच्चे हैं या पूर्ण नोड्स हैं अन्य नोड्स के या तो एक बच्चा है या कोई बच्चा नहीं है।
इटरेटिव दृष्टिकोण
उपयोग किया गया दृष्टिकोण:
- डेटा पार्ट, लेफ्ट पॉइंटर और राइट पॉइंटर वाला नोड का स्ट्रक्चर बनाएं
- बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएं
- पूर्ण नोड्स गिनने के लिए एक फ़ंक्शन बनाएं
- फ़ंक्शन के अंदर, जांचें यदि !नोड तो वापस लौटें क्योंकि ट्री में कोई नोड नहीं है
- पूर्ण नोड्स की संख्या स्टोर करने के लिए एक अस्थायी वैरिएबल काउंट घोषित करें
- क्यू टाइप वैरिएबल बनाएं मान लीजिए qu
- नोड्स को क्यू में डालें qu.push(नोड)
- लूप चलाएं जब तक !qu.empty():
- Node टाइप का एक अस्थायी वैरिएबल बनाएं मान लीजिए temp और इसे queue.front() से इनिशियलाइज़ करें
- qu.pop() का उपयोग करके एलिमेंट्स पॉप करें
- जांचें यदि (!temp->left && temp->right) तो काउंट को 1 से बढ़ाएं
- जांचें यदि (temp->left != NULL) तो qu.push(temp->left) करें
- जांचें यदि (temp->right != NULL) तो qu.push(temp->right) करें
- काउंट वापस करें
- परिणाम प्रिंट करें।
उदाहरण (C++ कोड)
// इटरेटिव प्रोग्राम पूर्ण नोड्स गिनने के लिए
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// बाइनरी ट्री में पूर्ण नोड्स गिनने के लिए फ़ंक्शन
int fullcount(struct Node* node){
// जांचें यदि ट्री खाली है
if (!node){
return 0;
}
queue<Node *> myqueue;
// लेवल ऑर्डर ट्रैवर्सल का उपयोग करके ट्रैवर्स करें
int result = 0;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout << "count is: " << fullcount(root);
return 0;
}
आउटपुट
count is: 2
रिकर्सिव दृष्टिकोण
उपयोग किया गया दृष्टिकोण:
- डेटा पार्ट, लेफ्ट पॉइंटर और राइट पॉइंटर वाला नोड का स्ट्रक्चर बनाएं
- बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएं
- पूर्ण नोड्स गिनने के लिए एक फ़ंक्शन बनाएं
- फ़ंक्शन के अंदर, जांचें यदि !नोड तो वापस लौटें क्योंकि ट्री में कोई नोड नहीं है
- आधे नोड्स की संख्या स्टोर करने के लिए एक अस्थायी वैरिएबल काउंट घोषित करें
- जांचें यदि (रूट->लेफ्ट && रूट->राइट) तो काउंट को 1 से बढ़ाएं
- काउंट = काउंट + रिकर्सिव_कॉल_टू_दिस_फंक्शन(रूट->लेफ्ट) + रिकर्सिव_कॉल_टू_दिस_फंक्शन(रूट->राइट) सेट करें
- काउंट वापस करें
- परिणाम प्रिंट करें।
उदाहरण (C++ कोड)
// रिकर्सिव प्रोग्राम पूर्ण नोड्स गिनने के लिए
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// पूर्ण नोड्स की संख्या प्राप्त करने के लिए फ़ंक्शन
int fullcount(struct Node* root){
if (root == NULL){
return 0;
}
int result = 0;
if (root->left && root->right){
result++;
}
result += (fullcount(root->left) + fullcount(root->right));
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout << "count is: " << fullcount(root);
return 0;
}
आउटपुट
count is: 2
