डेटा स्ट्रक्चर में बाइनरी ट्री ट्रैवर्सल

इस खंड में हम बाइनरी सर्च ट्री में मौजूद कीज़ को ट्रैवर्स करने के लिए विभिन्न ट्रैवर्सल एल्गोरिदम देखेंगे। ये ट्रैवर्सल हैं: इनऑर्डर ट्रैवर्सल, प्रीऑर्डर ट्रैवर्सल, पोस्टऑर्डर ट्रैवर्सल और लेवल ऑर्डर ट्रैवर्सल।

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

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

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

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

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

एल्गोरिदम

inorderTraverse(root): Begin    if root खाली नहीं है, then       inorderTraversal(root का लेफ्ट)       रूट का मान प्रिंट करें       inorderTraversal(root का राइट)    end if End preorderTraverse(root): Begin    if root खाली नहीं है, then       रूट का मान प्रिंट करें       preorderTraversal(root का लेफ्ट)       preorderTraversal(root का राइट)    end if End postorderTraverse(root): Begin    if root खाली नहीं है, then       postorderTraversal(root का लेफ्ट)       postorderTraversal(root का राइट)       रूट का मान प्रिंट करें    end if End 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 inorder_traversal(node *r);       void preorder_traversal(node *r);       void postorder_traversal(node *r);       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::inorder_traversal(node *r){    if(r != NULL){ //जब रूट मौजूद है, लेफ्ट - रूट - राइट विजिट करें       inorder_traversal(r->left);       cout << r->value << " ";       inorder_traversal(r->right);    } } void tree::preorder_traversal(node *r){    if(r != NULL){ //जब रूट मौजूद है, लेफ्ट - रूट - राइट विजिट करें       cout << r->value << " ";       preorder_traversal(r->left);       preorder_traversal(r->right);    } } void tree::postorder_traversal(node *r){    if(r != NULL){ //जब रूट मौजूद है, लेफ्ट - रूट - राइट विजिट करें       postorder_traversal(r->left);       postorder_traversal(r->right);       cout << r->value << " ";    } } 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 << "In-Order Traversal: ";    my_tree.inorder_traversal(my_tree.root);    cout << "\nPre-Order Traversal: ";    my_tree.preorder_traversal(my_tree.root);    cout << "\nPost-Order Traversal: ";    my_tree.postorder_traversal(my_tree.root);    cout << "\nLevel-Order Traversal: ";    my_tree.levelorder_traversal(my_tree.root); }

आउटपुट

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