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