ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें ट्री के प्रत्येक नोड को ठीक एक बार चेक या प्रिंट करना शामिल है। बाइनरी सर्च ट्री का इनऑर्डर ट्रैवर्सल ट्री के नोड्स को (लेफ्ट, रूट, राइट) के क्रम में विजिट करता है।
बाइनरी ट्री के इनऑर्डर ट्रैवर्सल का एक उदाहरण निम्नलिखित है।
एक बाइनरी ट्री निम्नलिखित है।
इनऑर्डर ट्रैवर्सल है: 1 4 5 6 8
इनऑर्डर रिकर्सिव ट्रैवर्सल करने का प्रोग्राम निम्नलिखित है।
उदाहरण
#include<iostream> using namespace std; struct node { int data; struct node *left; struct node *right; }; struct node *createNode(int val) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = val; temp->left = temp->right = NULL; return temp; } void inorder(struct node *root) { if (root != NULL) { inorder(root->left); cout<<root->data<<" "; inorder(root->right); } } struct node* insertNode(struct node* node, int val) { if (node == NULL) return createNode(val); if (val < node->data) node->left = insertNode(node->left, val); else if (val > node->data) node->right = insertNode(node->right, val); return node; } int main() { struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3); cout<<"बाइनरी सर्च ट्री का इन-ऑर्डर ट्रैवर्सल है: "; inorder(root); return 0; } आउटपुट
बाइनरी सर्च ट्री का इन-ऑर्डर ट्रैवर्सल है: 1 2 3 4 5 9
उपरोक्त प्रोग्राम में, संरचना node ट्री के नोड को बनाती है। यह संरचना एक सेल्फ-रेफरेंशियल संरचना है क्योंकि इसमें struct node प्रकार के पॉइंटर्स होते हैं। यह संरचना निम्नलिखित है।
struct node { int data; struct node *left; struct node *right; }; createNode() फ़ंक्शन एक नोड temp बनाता है और malloc का उपयोग करके इसे मेमोरी आवंटित करता है। डेटा मान val को temp के data में संग्रहीत किया जाता है। temp के लेफ्ट और राइट पॉइंटर्स में NULL संग्रहीत किया जाता है। यह निम्नलिखित कोड स्निपेट द्वारा प्रदर्शित होता है।
struct node *createNode(int val) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = val; temp->left = temp->right = NULL; return temp; } inorder() फ़ंक्शन बाइनरी ट्री के रूट को आर्गुमेंट के रूप में लेता है और ट्री के एलिमेंट्स को इनऑर्डर में प्रिंट करता है। यह एक रिकर्सिव फ़ंक्शन है। इसे निम्नलिखित कोड का उपयोग करके प्रदर्शित किया गया है।
void inorder(struct node *root) { if (root != NULL) { inorder(root->left); cout<<root->data<<" "; inorder(root->right); } } insertNode() फ़ंक्शन बाइनरी ट्री में आवश्यक मान को उसकी सही स्थिति पर डालता है। यदि नोड NULL है, तो createNode को कॉल किया जाता है। अन्यथा, ट्री में नोड के लिए सही स्थिति ढूंढी जाती है। यह निम्नलिखित कोड स्निपेट में देखा जा सकता है।
struct node* insertNode(struct node* node, int val) { if (node == NULL) return createNode(val); if (val < node->data) node->left = insertNode(node->left, val); else if (val > node->data) node->right = insertNode(node->right, val); return node; } main() फ़ंक्शन में, रूट नोड को पहले NULL के रूप में परिभाषित किया जाता है। फिर आवश्यक मानों वाले सभी नोड्स को बाइनरी सर्च ट्री में डाला जाता है। यह नीचे दिखाया गया है।
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
अंत में, ट्री के रूट नोड का उपयोग करके inorder() फ़ंक्शन को कॉल किया जाता है और सभी ट्री मानों को इनऑर्डर में प्रदर्शित किया जाता है। यह नीचे दिया गया है।
cout<<"बाइनरी सर्च ट्री का इन-ऑर्डर ट्रैवर्सल है: "; inorder(root);
