C++ में दिए गए प्रीऑर्डर ट्रैवर्सल से BST का निर्माण (सेट 1)

मान लीजिए हमारे पास एक प्रीऑर्डर ट्रैवर्सल है। इस ट्रैवर्सल से हमें ट्री उत्पन्न करना है। तो यदि ट्रैवर्सल [10, 5, 1, 7, 40, 50] जैसा है, तो ट्री इस तरह होगा -

इसे हल करने के लिए, हम इस ट्रिक का उपयोग करेंगे। ट्रिक प्रत्येक नोड के लिए एक रेंज {min... max} सेट करना है। सबसे पहले हम रेंज को {INT_MIN... INT_MAX} के रूप में इनिशियलाइज़ करेंगे। पहला नोड निश्चित रूप से रेंज में होगा, इसलिए उसके बाद हम रूट नोड बनाएंगे। लेफ्ट सबट्री बनाने के लिए, रेंज को {INT_MIN... root->data} के रूप में सेट करें। यदि कोई मान रेंज {INT_MIN... root->data} में है, तो वह मान लेफ्ट सबट्री का हिस्सा है। राइट सबट्री बनाने के लिए, रेंज को {root->data... max... INT_MAX} के रूप में सेट करें।

उदाहरण

#include <iostream> 
using namespace std; 

class node {
public:
    int data;
    node *left;
    node *right;
};

node* getNode(int data) {
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

node* makeTreeUtil(int pre[], int* preord_index, int key, int min, int max, int size) {
    if (*preord_index >= size)
        return NULL;
    
    node* root = NULL;
    
    if (key > min && key < max) {
        root = getNode(key);
        *preord_index += 1;
        
        if (*preord_index < size) {
            root->left = makeTreeUtil(pre, preord_index, pre[*preord_index], min, key, size);
            root->right = makeTreeUtil(pre, preord_index, pre[*preord_index], key, max, size);
        }
    }
    
    return root;
}

node* makeTree(int pre[], int size) {
    int preord_index = 0;
    return makeTreeUtil(pre, &preord_index, pre[0], INT_MIN, INT_MAX, size);
}

void inord(node* node) {
    if (node == NULL)
        return;
    inord(node->left);
    cout << node->data << " ";
    inord(node->right);
}

int main() {
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof(pre) / sizeof(pre[0]);
    node* root = makeTree(pre, size);
    cout << "Inorder traversal: ";
    inord(root);
}

आउटपुट

Inorder traversal: 1 5 7 10 40 50