मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें लेवल ऑर्डर ट्रैवर्सल स्कीम का उपयोग करके इस पेड़ को पार करना होगा। तो अगर पेड़ ऐसा है
ट्रैवर्सल अनुक्रम इस प्रकार होगा - [10, 5, 16, 8, 15, 20, 23]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- नोड्स को स्टोर करने के लिए क्यू को परिभाषित करें
- क्यू में रूट डालें।
- जबकि क्यू खाली नहीं है, करें
- आइटम:=आइटम कतार के सामने की स्थिति में मौजूद है
- आइटम का मूल्य प्रिंट करें
- यदि आइटम का बायां भाग रिक्त नहीं है, तो आइटम के बाईं ओर को कतार में डालें
- यदि आइटम का अधिकार शून्य नहीं है, तो आइटम का अधिकार क्यू में डालें
- क्यू से फ्रंट एलिमेंट हटाएं
उदाहरण(C++)
एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include<iostream>
#include<queue>
using namespace std;
class node{
public:
int h_left, h_right, bf, value;
node *left, *right;
};
class tree{
private:
node *get_node(int key);
public:
node *root;
tree(){
root = NULL; //set root as NULL at the beginning
}
void levelorder_traversal(node *r);
node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
node *new_node;
new_node = new node; //create a new node dynamically
new_node->h_left = 0; new_node->h_right = 0;
new_node->bf = 0;
new_node->value = key; //store the value from given key
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::levelorder_traversal(node *root){
queue <node*> que;
node *item;
que.push(root); //insert the root at first
while(!que.empty()){
item = que.front(); //get the element from the front end
cout << item->value << " ";
if(item->left != NULL) //When left child is present, insert into queue
que.push(item->left);
if(item->right != NULL) //When right child is present, insert into queue
que.push(item->right);
que.pop(); //remove the item from queue
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL){
return (get_node(key)); //when tree is empty, create a node as root
}
if(key < root->value){ //when key is smaller than root value, go to the left
root->left = insert_node(root->left, key);
}
else if(key > root->value){ //when key is greater than root value, go to the right
root->right = insert_node(root->right, key);
}
return root; //when key is already present, do not insert it again
}
main(){
node *root;
tree my_tree;
//Insert some keys into the tree.
my_tree.root = my_tree.insert_node(my_tree.root, 10);
my_tree.root = my_tree.insert_node(my_tree.root, 5);
my_tree.root = my_tree.insert_node(my_tree.root, 16);
my_tree.root = my_tree.insert_node(my_tree.root, 20);
my_tree.root = my_tree.insert_node(my_tree.root, 15);
my_tree.root = my_tree.insert_node(my_tree.root, 8);
my_tree.root = my_tree.insert_node(my_tree.root, 23);
cout << "Level-Order Traversal: ";
my_tree.levelorder_traversal(my_tree.root);
} इनपुट
[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]
आउटपुट
Level-Order Traversal: 10 5 16 8 15 20 23