मान लीजिए कि हमारे पास एक प्री-ऑर्डर ट्रैवर्सल है। इस ट्रैवर्सल से। हमें पेड़ उत्पन्न करना है तो अगर ट्रैवर्सल [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<node*> 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