C++ प्रोग्राम: बाइनरी ट्री का प्रीऑर्डर नॉन-रिकर्सिव ट्रैवर्सल

ट्री ट्रैवर्सल

ग्राफ ट्रैवर्सल का एक रूप। ट्री के प्रत्येक नोड को ठीक एक बार चेक/प्रिंट करना शामिल है। प्रीऑर्डर ट्रैवर्सल क्रम: रूट → बाएं → दाएं।

बाइनरी ट्री उदाहरण

Preorder Traversal: 5 3 2 4 8 9

C++ प्रोग्राम उदाहरण (इटरेटिव/नॉन-रिकर्सिव)

#include <iostream>
#include <stack>
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 preorder(struct Node* root) {
    if (root == NULL) return;
    
    stack<Node*> nodeStack;
    nodeStack.push(root);
    
    while (!nodeStack.empty()) {
        struct Node* temp_node = nodeStack.top();
        cout << temp_node->data << " ";
        nodeStack.pop();
        
        // दाएं पहले पुश करें ताकि बाएं पहले प्रोसेस हो (स्टैक LIFO)
        if (temp_node->right)
            nodeStack.push(temp_node->right);
        if (temp_node->left)
            nodeStack.push(temp_node->left);
    }
}

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, 5);
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 2);
    insertNode(root, 6);
    insertNode(root, 9);
    insertNode(root, 4);
    
    cout << "Pre-Order traversal of BST: ";
    preorder(root);
    return 0;
}

आउटपुट

Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9

कोड व्याख्या

Node संरचना

सेल्फ-रेफरेंशियल: data, left, right पॉइंटर्स।

createNode() फ़ंक्शन

malloc से मेमोरी आवंटित करता है, डेटा सेट करता है, बच्चों को NULL करता है।

preorder() फ़ंक्शन (इटरेटिव)

1. रूट को स्टैक में पुश करें
2. जब तक स्टैक खाली नहीं:
   • टॉप नोड पॉप करें, डेटा प्रिंट करें
   • दाएं बच्चे को पुश करें (यदि मौजूद)
   • बाएं बच्चे को पुश करें (यदि मौजूद)

नोट: दाएं को पहले पुश करने से बाएं पहले प्रोसेस होता है (स्टैक LIFO)।

insertNode() फ़ंक्शन

बाइनरी सर्च ट्री प्रॉपर्टी के अनुसार रिकर्सिव इन्सर्शन: छोटा बाएं, बड़ा दाएं।

मुख्य फ़ंक्शन

BST बनाता है: 5, 8, 3, 2, 6, 9, 4 इन्सर्ट करता है, फिर प्रीऑर्डर ट्रैवर्सल कॉल करता है।

रिकर्सिव बनाम इटरेटिव प्रीऑर्डर

अन्य ट्रैवर्सल क्रम

• इनऑर्डर (Inorder): बाएं → रूट → दाएं (BST के लिए क्रमबद्ध क्रम)
• पोस्टऑर्डर (Postorder): बाएं → दाएं → रूट
• लेवल ऑर्डर: क्यू का उपयोग करके ब्रेडथ-फर्स्ट