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

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

इसे हल करने के लिए, हम रिकर्सिव दृष्टिकोण का उपयोग करेंगे। पहला तत्व रूट होगा। दूसरा तत्व लेफ्ट चाइल्ड होगा, और तीसरा तत्व राइट चाइल्ड होगा (यदि BST की शर्त पूरी होती है), यह गुण सभी तत्वों के लिए संतुष्ट होगा। तो हम इन चरणों का पालन करेंगे -

• सबसे पहले हमें ऐरे का पहला तत्व लेना होगा, और इसे रूट बनाना होगा।

• फिर दूसरा तत्व लें। यदि यह रूट से छोटा है, तो इसे लेफ्ट चाइल्ड बनाएं अन्यथा राइट चाइल्ड

• फिर चरण 2 को रिकर्सिवली कॉल करके BST बनाएं।

उदाहरण

#include <iostream> 
using namespace std; 

class Node {
public:
    int data;
    Node *left, *right;
};

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

Node* lvlOrd(Node* root, int data) {
    if (root == NULL) {
        root = getNode(data);
        return root;
    }
    if (data <= root->data)
        root->left = lvlOrd(root->left, data);
    else
        root->right = lvlOrd(root->right, data);
    return root;
}

Node* makeTree(int arr[], int n) {
    if (n == 0)
        return NULL;
    Node* root = NULL;
    for (int i = 0; i < n; i++)
        root = lvlOrd(root, arr[i]);
    return root;
}

void inord(Node* root) {
    if (!root)
        return;
    inord(root->left);
    cout << root->data << " ";
    inord(root->right);
}

int main() {
    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = makeTree(arr, n);
    cout << "Inorder Traversal: ";
    inord(root);
}

आउटपुट

Inorder Traversal: 1 3 4 5 6 7 8 10 12