मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें लेवल ऑर्डर ट्रैवर्सल फैशन का उपयोग करके इस पेड़ को पार करना है। तो अगर पेड़ ऐसा है
ट्रैवर्सल अनुक्रम इस प्रकार होगा:[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, ]