C++ में बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल (Binary Tree Level Order Traversal)

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

ट्रैवर्सल अनुक्रम इस तरह होगा: [10, 5, 16, 8, 15, 20, 23]

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• नोड्स संग्रहीत करने के लिए कतार que परिभाषित करें
• रूट को que में डालें।
• जब तक que खाली नहीं है:
  • item := कतार के सामने की स्थिति पर मौजूद आइटम
  • item का मान प्रिंट करें
  • यदि item का बायां बच्चा null नहीं है, तो item के बाएं को que में डालें
  • यदि item का दायां बच्चा null नहीं है, तो item के दाएं को que में डालें
  • कतार से सामने का तत्व हटाएं

उदाहरण (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;
    }
    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;
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = 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);
    while(!que.empty()){
        item = que.front();
        cout << item->value << " ";
        if(item->left != NULL)
            que.push(item->left);
        if(item->right != NULL)
            que.push(item->right);
        que.pop();
    }
}

node *tree::insert_node(node *root, int key){
    if(root == NULL){
        return (get_node(key));
    }
    if(key < root->value){
        root->left = insert_node(root->left, key);
    }
    else if(key > root->value){
        root->right = insert_node(root->right, key);
    }
    return root;
}

int main(){
    node *root;
    tree my_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 << "लेवल-ऑर्डर ट्रैवर्सल: ";
    my_tree.levelorder_traversal(my_tree.root);
}

इनपुट

[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]

आउटपुट

लेवल-ऑर्डर ट्रैवर्सल: 10 5 16 8 15 20 23