मान लीजिए हमारे पास एक प्रीऑर्डर ट्रैवर्सल है। इस ट्रैवर्सल से हमें ट्री उत्पन्न करना है। तो यदि ट्रैवर्सल [10, 5, 1, 7, 40, 50] जैसा है, तो ट्री इस तरह होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
खाली स्टैक बनाएं
पहले मान को रूट बनाएं, और इसे स्टैक में पुश करें।
अब स्टैक खाली न होने और अगला मान स्टैक के शीर्ष तत्व से बड़ा होने तक पॉप करते रहें, इसे अंतिम पॉप किए गए नोड का राइट चाइल्ड बनाएं। अब नए नोड को स्टैक में पुश करें।
जब अगला मान शीर्ष तत्व से कम हो, तो इसे स्टैक के शीर्ष तत्व का लेफ्ट चाइल्ड बनाएं। अब नए नोड को स्टैक में पुश करें।
चरण 2 और 3 को तब तक दोहराएं जब तक हमने प्रीऑर्डर सूची के सभी तत्वों की जांच नहीं कर ली।
उदाहरण
#include <iostream>
#include <stack>
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* constructTree(int pre[], int size) {
stack stk;
node* root = getNode(pre[0]);
stk.push(root);
int i;
node* temp;
for (i = 1; i < size; ++i) {
temp = NULL;
while (!stk.empty() && pre[i] > stk.top()->data) {
temp = stk.top();
stk.pop();
}
if (temp != NULL) {
temp->right = getNode(pre[i]);
stk.push(temp->right);
} else {
node* peek_node = stk.top();
peek_node->left = getNode(pre[i]);
stk.push(stk.top()->left);
}
}
return root;
}
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 = constructTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
}
आउटपुट
Inorder traversal: 1 5 7 10 40 50
