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