मान लीजिए कि हमारे पास एक स्तर का ऑर्डर ट्रैवर्सल है। इस ट्रैवर्सल से। हमें पेड़ उत्पन्न करना है तो अगर ट्रैवर्सल [7, 4, 12, 3, 6, 8, 1, 5, 10] जैसा है, तो पेड़ जैसा होगा -
इसे हल करने के लिए, हम पुनरावर्ती दृष्टिकोण का उपयोग करेंगे। पहला तत्व जड़ होगा। दूसरा तत्व लेफ्ट चाइल्ड होगा, और तीसरा तत्व राइट चाइल्ड होगा (यदि बीएसटी की स्थिति संतुष्ट होती है), यह गुण सभी तत्वों के लिए संतुष्ट होगा। तो हम इन चरणों का पालन करेंगे -
-
सबसे पहले हमें सरणी का पहला तत्व लेना होगा, और इसे रूट बनाना होगा।
-
फिर दूसरा तत्व लें। अगर वह जड़ से छोटा है, तो उसे बायां बच्चा बना दें अन्यथा दायां बच्चा
-
फिर बीएसटी बनाने के लिए चरण 2 को दोबारा कॉल करें।
उदाहरण
#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