हमें एक बाइनरी ट्री दिया गया है और कार्य एक बाइनरी ट्री में उपलब्ध पूर्ण नोड्स की गणना करने के लिए पुनरावृत्ति और पुनरावर्ती दृष्टिकोण का उपयोग करना है। पूर्ण नोड्स वे नोड हैं जिनके दोनों बच्चे हैं और कोई भी बच्चा शून्य नहीं है। ध्यान दें कि पूर्ण नोड्स में हम ठीक दो बच्चों वाले नोड्स पर विचार करते हैं।
बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। एक बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं। एक बाइनरी ट्री में एक क्रमबद्ध सरणी और एक लिंक की गई सूची दोनों के लाभ होते हैं क्योंकि खोज एक क्रमबद्ध सरणी में जितनी जल्दी होती है और सम्मिलन या हटाने की कार्रवाई उतनी ही तेज होती है जितनी कि लिंक की गई सूची में होती है। नॉन-लीफ नोड्स को पैरेंट नोड्स के रूप में भी जाना जाता है क्योंकि उनके 0 से अधिक बच्चे और दो से कम बच्चे होते हैं।
बाइनरी ट्री की संरचना नीचे दी गई है -
उदाहरण के लिए
इनपुट -
आउटपुट - गिनती 2 है
स्पष्टीकरण - दिए गए पेड़ में 2 नोड होते हैं यानी 10 और 20 ठीक दो बच्चों के साथ या पूर्ण नोड्स अन्य नोड्स में या तो एक बच्चा होता है या कोई बच्चा नहीं होता है।
पुनरावर्ती
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
डेटा भाग, बाएँ सूचक और दाएँ सूचक वाले नोड की संरचना बनाएँ।
-
बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएँ।
-
पूर्ण नोड्स गिनने के लिए एक फ़ंक्शन बनाएं।
-
किसी फ़ंक्शन के अंदर, IF !node जांचें और फिर वापस आएं क्योंकि पेड़ में कोई नोड नहीं है।
-
पूर्ण नोड्स की संख्या को संग्रहीत करने के लिए एक अस्थायी चर गणना की घोषणा करें
-
एक कतार प्रकार चर बनाएं मान लें कि qu
-
कतार में नोड्स को qu.push(node) के रूप में पुश करें
-
लूप जबकि !qu.empty()
-
एक अस्थायी चर बनाएँ मान लें कि नोड प्रकार का अस्थायी है और इसे कतार के साथ प्रारंभ करें। सामने ()
-
qu.pop()
. का उपयोग करके तत्वों को पॉप करें -
IF (!temp-> लेफ्ट और टेम्प-> राइट) चेक करें और फिर काउंट को 1 तक बढ़ा दें
-
IF (temp->left !=NULL) चेक करें और फिर qu.push(temp->left)
perform करें -
IF (temp->right !=NULL) चेक करें फिर qu.push(temp->right)
-
गिनती वापस करें
-
परिणाम प्रिंट करें।
उदाहरण
// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
// Check if tree is empty
if (!node){
return 0;
}
queue<Node *> myqueue;
// traverse using level order traversing
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
पुनरावर्ती
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
डेटा भाग, बाएँ सूचक और दाएँ सूचक वाले नोड की संरचना बनाएँ।
-
बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएँ।
-
पूर्ण नोड्स गिनने के लिए एक फ़ंक्शन बनाएं।
-
किसी फ़ंक्शन के अंदर, IF !node जांचें और फिर वापस आएं क्योंकि पेड़ में कोई नोड नहीं है।
-
आधे नोड्स की संख्या को संग्रहीत करने के लिए एक अस्थायी चर गणना की घोषणा करें
-
IF (रूट -> लेफ्ट और रूट-> राइट) चेक करें और फिर काउंट को 1 से बढ़ा दें
-
सेट काउंट =काउंट + रिकर्सिव_कॉल_टो_थिस_फंक्शन (रूट-> लेफ्ट) + रिकर्सिव_कॉल_टो_थिस_फंक्शन (रूट-> राइट)
-
गिनती वापस करें
-
परिणाम प्रिंट करें।
उदाहरण
// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of full Nodes
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