सी ++ में बाइनरी ट्री में गैर-पत्ती नोड्स की गणना करें

हमें एक बाइनरी ट्री दिया गया है और कार्य एक बाइनरी ट्री में उपलब्ध गैर-पत्ती नोड्स की गिनती की गणना करना है।

बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। एक बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं। एक बाइनरी ट्री में एक क्रमबद्ध सरणी और एक लिंक की गई सूची दोनों के लाभ होते हैं क्योंकि खोज एक क्रमबद्ध सरणी में जितनी जल्दी होती है और सम्मिलन या हटाने की कार्रवाई उतनी ही तेज होती है जितनी कि लिंक की गई सूची में होती है। नॉन-लीफ नोड्स को पैरेंट नोड्स के रूप में भी जाना जाता है क्योंकि उनके 0 से अधिक बच्चे और दो से कम बच्चे होते हैं।

बाइनरी ट्री की संरचना नीचे दी गई है -

उदाहरण के लिए

इनपुट -

आउटपुट - गैर-पत्ती नोड्स की संख्या है:3

स्पष्टीकरण - दिए गए पेड़ में, हमारे पास 27, 14 और 35 गैर-पत्ती नोड्स हैं क्योंकि उनके 0 से अधिक बच्चे हैं और 2 से कम बच्चे हैं।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• बाइनरी ट्री की संरचना बनाएं, जिसमें बाएं नोड का पॉइंटर, दाएं नोड का पॉइंटर और नोड में संग्रहीत डेटा भाग हो

• एक फ़ंक्शन बनाएं जो इस फ़ंक्शन को कॉल किए जाने पर नोड सम्मिलित करेगा। उसके लिए, नए नोड में डेटा डालें और नए नोड के दाएं और बाएं पॉइंटर को NULL पर सेट करें और नोड को वापस करें।

• एक पुनरावर्ती फ़ंक्शन बनाएं जो एक बाइनरी ट्री में गैर-पत्ती नोड्स की संख्या की गणना करेगा।

  • जांचें कि क्या रूट न्यूल है या रूट का बायां हिस्सा न्यूल है और रूट का राइट न्यूल है तो वापस 0
  • बाएं पॉइंटर के साथ इस फ़ंक्शन पर 1 + रिकर्सिव कॉल लौटाएं + दाएं पॉइंटर के साथ इस फ़ंक्शन पर रिकर्सिव कॉल

• गिनती प्रिंट करें

उदाहरण

#include <iostream>
using namespace std;
// Node's structure
struct Node {
   int data;
   struct Node* left;
   struct Node* right;
};
// To define the new node
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
// Count the non leaf nodes.
int nonleaf(struct Node* root){
   if (root == NULL || (root->left == NULL && root->right == NULL)){
      return 0;
   }
   return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// Main function
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