हमें एक बाइनरी ट्री दिया गया है और कार्य एक बाइनरी ट्री में उपलब्ध आधे नोड्स की गणना करने के लिए पुनरावृत्ति और पुनरावर्ती दृष्टिकोण का उपयोग करना है। हाफ नोड्स वे नोड होते हैं जिनमें केवल एक बच्चा होता है और दूसरा बच्चा शून्य होता है। ध्यान दें कि आधे नोड्स में हम लीफ नोड्स पर विचार नहीं करते हैं।
बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। एक बाइनरी ट्री की एक विशेष शर्त है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं। एक बाइनरी ट्री में एक क्रमबद्ध सरणी और एक लिंक की गई सूची दोनों के लाभ होते हैं क्योंकि खोज एक क्रमबद्ध सरणी में जितनी जल्दी होती है और सम्मिलन या हटाने की कार्रवाई उतनी ही तेज होती है जितनी कि लिंक की गई सूची में होती है। नॉन-लीफ नोड्स को पैरेंट नोड्स के रूप में भी जाना जाता है क्योंकि उनके 0 से अधिक बच्चे और दो से कम बच्चे होते हैं।
बाइनरी ट्री की संरचना नीचे दी गई है -
उदाहरण के लिए
इनपुट -
आउटपुट - गिनती 2 है
स्पष्टीकरण - दिए गए पेड़ में 2 नोड होते हैं यानी 40 और 50 ठीक एक बच्चे या आधे नोड्स के साथ अन्य नोड्स में दो बच्चे हो सकते हैं या कोई बच्चा नहीं हो सकता है।
पुनरावर्ती
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
डेटा भाग, बाएँ सूचक और दाएँ सूचक वाले नोड की संरचना बनाएँ।
-
बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएँ।
-
आधा नोड्स गिनने के लिए एक फ़ंक्शन बनाएं।
-
किसी फ़ंक्शन के अंदर, IF !node जांचें और फिर वापस आएं क्योंकि पेड़ में कोई नोड नहीं है।
-
आधे नोड्स की संख्या को संग्रहीत करने के लिए एक अस्थायी चर गणना की घोषणा करें
-
एक कतार प्रकार चर बनाएं मान लें कि qu
-
कतार में नोड्स को qu.push(node) के रूप में पुश करें
-
लूप जबकि !qu.empty()
-
एक अस्थायी चर बनाएँ मान लें कि नोड प्रकार का अस्थायी है और इसे कतार के साथ प्रारंभ करें। सामने ()
-
qu.pop()
. का उपयोग करके तत्वों को पॉप करें -
IF (!temp-> लेफ्ट और टेम्प-> राइट) या (temp-> लेफ्ट और !temp-> राइट) चेक करें और फिर काउंट को 1 तक बढ़ा दें
-
IF (temp->left !=NULL) चेक करें और फिर qu.push(temp->left)
perform करें -
गिनती लौटाएं
-
परिणाम प्रिंट करें।
उदाहरण
// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
// If tree is empty
if (!node)
return 0;
int result = 0; // Initialize count of half nodes
// Do level order traversal starting from root
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;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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
पुनरावर्ती
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
डेटा भाग, बाएँ सूचक और दाएँ सूचक वाले नोड की संरचना बनाएँ।
-
बाइनरी ट्री में नोड्स डालने के लिए एक फ़ंक्शन बनाएँ।
-
आधा नोड्स गिनने के लिए एक फ़ंक्शन बनाएं।
-
किसी फ़ंक्शन के अंदर, IF !node जांचें और फिर वापस आएं क्योंकि पेड़ में कोई नोड नहीं है।
-
आधे नोड्स की संख्या को संग्रहीत करने के लिए एक अस्थायी चर गणना की घोषणा करें
-
IF (रूट -> लेफ्ट =न्यूल और रूट-> राइट! =न्यूल) या (रूट -> लेफ्ट! =न्यूल और रूट-> राइट ==न्यूल) चेक करें, फिर काउंट को 1 से बढ़ा दें
-
सेट काउंट =काउंट + रिकर्सिव_कॉल_टो_थिस_फंक्शन (रूट-> लेफ्ट) + रिकर्सिव_कॉल_टो_थिस_फंक्शन (रूट-> राइट)
-
गिनती लौटाएं
-
परिणाम प्रिंट करें।
उदाहरण
// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
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;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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