Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

बाइनरी ट्री के सभी लीफ नोड्स को C++ में दाएं से बाएं प्रिंट करें


इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना होता है।

आइए समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट -

बाइनरी ट्री के सभी लीफ नोड्स को C++ में दाएं से बाएं प्रिंट करें

आउटपुट - 7 4 1

इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को पार करना होगा। यह ट्रैवर्सल दो तरह से किया जा सकता है -

प्रीऑर्डर ट्रैवर्सल - यह ट्रैवर्सल रिकर्सन का उपयोग करता है। यहां, हम ट्रैवर्स करेंगे, रूट करेंगे फिर लेफ्ट और फिर राइट सबट्री। यदि हमें कोई लीफ नोड मिलता है तो हम उसे प्रिंट करेंगे, अन्यथा हम नोड के बच्चों की जांच करेंगे और लीफ नोड को खोजने के लिए उन्हें एक्सप्लोर करेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम -

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
Node* insertNode(int data) {
   Node* temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
void findLeafNode(Node* root) {
   if (!root)
      return;
   if (!root->left && !root->right) {
      cout<<root->data<<"\t";
      return;
   }
   if (root->right)
      findLeafNode(root->right);
   if (root->left)
      findLeafNode(root->left);
}
int main() {
   Node* root = insertNode(21);
   root->left = insertNode(5);
   root->right = insertNode(11);
   root->left->left = insertNode(8);
   root->left->right = insertNode(98);
   root->right->left = insertNode(2);
   root->right->right = insertNode(8);
   cout<<"Leaf nodes of the tree from right to left are:\n";
   findLeafNode(root);
   return 0;
}

आउटपुट

Leaf nodes of the tree from right to left are −
18 2 98 8
. हैं

पोस्टऑर्डर ट्रैवर्सल - लीफ नोड को खोजने के लिए यह ट्रैवर्सल पुनरावृत्ति का उपयोग करेगा। हम डेटा को स्टोर करने के लिए स्टैक का उपयोग करेंगे और पेड़ को पोस्टऑर्डर तरीके से पार करेंगे (पहले दायां उपट्री फिर बाएं सबट्री और फिर रूट) और लीफ नोड्स प्रिंट करें।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम -

#include<bits/stdc++.h>
using namespace std;
struct Node {
   Node* left;
   Node* right;
   int data;
};
Node* insertNode(int key) {
   Node* node = new Node();
   node->left = node->right = NULL;
   node->data = key;
   return node;
}
void findLeafNode(Node* tree) {
   stack<Node*> treeStack;
   while (1) {
      if (tree) {
         treeStack.push(tree);
         tree = tree->right;
      } else {
         if (treeStack.empty())
            break;
         else {
            if (treeStack.top()->left == NULL) {
               tree = treeStack.top();
               treeStack.pop();
               if (tree->right == NULL)
                  cout<<tree->data<<"\t";
            }
            while (tree == treeStack.top()->left) {
               tree = treeStack.top();
               treeStack.pop();
               if (treeStack.empty())
                  break;
            }
            if (!treeStack.empty())
               tree = treeStack.top()->left;
            else
               tree = NULL;
         }  
      }
   }
}
int main(){
   Node* root = insertNode(21);
   root->left = insertNode(5);
   root->right = insertNode(11);
   root->left->left = insertNode(8);
   root->left->right = insertNode(98);
   root->right->left = insertNode(2);
   root->right->right = insertNode(18);
   cout<<"Leaf nodes of the tree from right to left are:\n";
   findLeafNode(root);
   return 0;
}

आउटपुट

Leaf nodes of the tree from right to left are −
18 2 98 8
. हैं
  1. बाइनरी सर्च ट्री के सभी विषम नोड्स को C++ में प्रिंट करें

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

  1. C++ प्रोग्रामिंग में एक बाइनरी ट्री में सभी नोड्स के प्रिंट स्तर।

    बाइनरी ट्री को देखते हुए, कार्य 1 से n तक के नोड में संग्रहीत प्रत्येक कुंजी से जुड़े स्तर को प्रिंट करना है उपरोक्त पेड़ में, नोड्स हैं - 10 लेवल 13 पर और 211 लेवल 2140 पर, 162, 100 और 146 लेवल 3 पर कुंजी को देखते हुए प्रोग्राम को उस विशेष कुंजी के स्तर को प्रिंट करना होगा। उदाहरण एल्गोरिदम न

  1. C++ में एक स्टैक का उपयोग करके बाएं से दाएं बाइनरी ट्री में लीफ नोड्स प्रिंट करें

    प्रोग्राम को बाइनरी ट्री के लीफ नोड्स को बाएं से दाएं प्रिंट करना चाहिए, लेकिन चुनौती में केवल एक स्टैक का उपयोग करना शामिल है पुश () फ़ंक्शन के माध्यम से एक बाइनरी ट्री के नोड्स डालें और पॉप () ऑपरेशन के माध्यम से लीफ नोड्स प्रदर्शित करें। लीफ नोड्स अंतिम नोड होते हैं जिनके बाएँ और दाएँ पॉइंटर NU