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

C++ में बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल करने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें लेवल ऑर्डर ट्रैवर्सल फैशन का उपयोग करके इस पेड़ को पार करना है। तो अगर पेड़ ऐसा है

C++ में बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल करने का कार्यक्रम

ट्रैवर्सल अनुक्रम इस प्रकार होगा:[1,2,3,5,4]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • नोड्स को स्टोर करने के लिए क्यू क्यू को परिभाषित करें

  • कतार में जड़ डालें।

  • जबकि क्यू खाली नहीं है, करें

    • आइटम:=आइटम कतार के सामने की स्थिति में मौजूद है

    • आइटम का मूल्य प्रिंट करें

    • यदि आइटम का बायां भाग रिक्त नहीं है, तो आइटम के बाईं ओर को कतार में डालें

    • यदि आइटम का अधिकार शून्य नहीं है, तो आइटम का अधिकार क्यू में डालें

    • कतार से सामने का तत्व हटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
class Solution {
   public:
   vector<int> solve(TreeNode* root) {
      if(!root)
         return {};
      vector <int> ret;
      queue <TreeNode*> q;
      q.push(root);
      while(!q.empty()){
         TreeNode* node = q.front();
         q.pop();
         ret.push_back(node->val);
         if(node->left){
            q.push(node->left);
         }
         if(node->right){
            q.push(node->right);
         }
      }
      return ret;
   }
};
main(){
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(2);
   root->right = new TreeNode(3);
   root->left->right = new TreeNode(5);
   root->right->right = new TreeNode(4);
   Solution ob;
   print_vector(ob.solve(root));
}

इनपुट

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);

आउटपुट

[1, 2, 3, 5, 4, ]

  1. सी ++ प्रोग्राम किसी दिए गए बाइनरी ट्री के पोस्टऑर्डर रिकर्सिव ट्रैवर्सल करने के लिए

    ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें पेड़ में प्रत्येक नोड को ठीक एक बार जांचना या प्रिंट करना शामिल है। बाइनरी सर्च ट्री के पोस्टऑर्डर ट्रैवर्सल में ट्री में प्रत्येक नोड को क्रम (बाएं, दाएं, रूट) में जाना शामिल है। बाइनरी ट्री के पोस्टऑर्डर ट्रैवर्सल का एक उदाहरण इस प्रकार है। एक ब

  1. सी ++ प्रोग्राम किसी दिए गए बाइनरी ट्री के इनऑर्डर रिकर्सिव ट्रैवर्सल करने के लिए

    ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें पेड़ में प्रत्येक नोड को ठीक एक बार जांचना या प्रिंट करना शामिल है। बाइनरी सर्च ट्री के इनऑर्डर ट्रैवर्सल में ट्री में प्रत्येक नोड को क्रम (बाएं, रूट, राइट) में जाना शामिल है। बाइनरी ट्री के इनऑर्डर ट्रैवर्सल का एक उदाहरण इस प्रकार है। एक बाइनरी

  1. सी ++ प्रोग्राम किसी दिए गए बाइनरी ट्री के प्रीऑर्डर रिकर्सिव ट्रैवर्सल करने के लिए

    ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें पेड़ में प्रत्येक नोड को ठीक एक बार जांचना या प्रिंट करना शामिल है। बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल में ट्री के प्रत्येक नोड को क्रम (रूट, लेफ्ट, राइट) में जाना शामिल है। बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल का एक उदाहरण इस प्रकार है। एक बाइ