डेटा स्ट्रक्चर में लेवल ऑर्डर ट्री ट्रैवर्सल

इस खंड में हम बाइनरी सर्च ट्री के लिए लेवल-ऑर्डर ट्रैवर्सल तकनीक देखेंगे।

मान लीजिए हमारे पास ऐसा एक ट्री है:

ट्रैवर्सल क्रम इस प्रकार होगा: 10, 5, 16, 8, 15, 20, 23

एल्गोरिदम

levelOrderTraverse(root): Begin    नोड्स स्टोर करने के लिए कतार que परिभाषित करें    रूट को que में इन्सर्ट करें।    while que खाली नहीं है, do       item := कतार के फ्रंट पोजीशन पर मौजूद आइटम       item का मान प्रिंट करें       अगर item का लेफ्ट नल नहीं है, then          item के लेफ्ट को que में इन्सर्ट करें       end if       अगर item का राइट नल नहीं है, then          item के राइट को que में इन्सर्ट करें       end if       que से फ्रंट एलिमेंट डिलीट करें    done End

उदाहरण

#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; //शुरुआत में रूट को 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; //जब की पहले से मौजूद है, इसे फिर से इन्सर्ट न करें } 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 << "Level-Order Traversal: ";    my_tree.levelorder_traversal(my_tree.root); }

आउटपुट

Level-Order Traversal: 10 5 16 8 15 20 23