ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें पेड़ में प्रत्येक नोड को ठीक एक बार जांचना या प्रिंट करना शामिल है। बाइनरी सर्च ट्री के इनऑर्डर ट्रैवर्सल में ट्री में प्रत्येक नोड को क्रम (बाएं, रूट, राइट) में जाना शामिल है।
बाइनरी ट्री के इनऑर्डर ट्रैवर्सल का एक उदाहरण इस प्रकार है।
एक बाइनरी ट्री इस प्रकार दिया गया है।
इनऑर्डर ट्रैवर्सल है: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<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
} आउटपुट
In-Order traversal of the Binary Search Tree is: 1 2 3 4 5 9
उपरोक्त कार्यक्रम में, संरचना नोड एक पेड़ का नोड बनाता है। यह संरचना एक स्व-संदर्भात्मक संरचना है क्योंकि इसमें स्ट्रक्चर नोड प्रकार के पॉइंटर्स होते हैं। यह संरचना इस प्रकार दिखाई गई है।
struct node {
int data;
struct node *left;
struct node *right;
}; फ़ंक्शन createNode () एक नोड अस्थायी बनाता है और इसे मॉलोक का उपयोग करके मेमोरी आवंटित करता है। डेटा मान वैल अस्थायी के डेटा में संग्रहीत किया जाता है। 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;
} फ़ंक्शन इनऑर्डर () बाइनरी ट्री की जड़ को तर्क के रूप में लेता है और ट्री के तत्वों को इनऑर्डर में प्रिंट करता है। यह एक पुनरावर्ती कार्य है। यह निम्नलिखित कोड का उपयोग करके प्रदर्शित किया जाता है।
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
} फ़ंक्शन इन्सर्ट नोड () बाइनरी ट्री में आवश्यक मान को उसकी सही स्थिति में सम्मिलित करता है। यदि नोड 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;
} मुख्य () फ़ंक्शन में, रूट नोड को पहले NULL के रूप में परिभाषित किया गया है। फिर आवश्यक मान वाले सभी नोड्स को बाइनरी सर्च ट्री में डाला जाता है। यह नीचे दिखाया गया है।
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
अंत में, फ़ंक्शन इनऑर्डर () को ट्री के रूट नोड का उपयोग करके कॉल किया जाता है और सभी ट्री मान इनऑर्डर में प्रदर्शित होते हैं। यह नीचे दिया गया है।
cout<<"In-Order traversal of the Binary Search Tree is: "; inorder(root);