मान लीजिए हम बाइनरी ट्री के लिए एक इटरेटर बनाना चाहते हैं। दो मेथड होंगे। अगला एलिमेंट लौटाने के लिए next() मेथड, और बूलियन मान लौटाने के लिए hasNext() मेथड, जो इंगित करेगा कि अगला एलिमेंट मौजूद है या नहीं। तो यदि ट्री इस तरह है −
और फंक्शन कॉल्स का अनुक्रम [next(), next(), hasNext(), next(), hasNext(),next(), hasNext(),next(), hasNext()] है। आउटपुट [3,7,true,9,true,15,true,20,false] होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- दो मेथड next और hasNext हैं,
- next() मेथड इस तरह होगा −
- curr := स्टैक टॉप एलिमेंट, और टॉप एलिमेंट पॉप करें
- यदि curr का राइट null नहीं है, तो नोड के राइट से इनऑर्डर सक्सेसर पुश करें
- करंट का मान लौटाएं
- hasNext() मेथड इस तरह होगा −
- सच लौटाएं, जब स्टैक खाली न हो, अन्यथा गलत।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else { q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; }else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class BSTIterator { public: stack <TreeNode*> st; void fillStack(TreeNode* node){ while(node && node->val != 0){ st.push(node); node=node->left; } } BSTIterator(TreeNode* root) { fillStack(root); } /** @return the next smallest number */ int next() { TreeNode* curr = st.top(); st.pop(); if(curr->right && curr->right->val != 0){ fillStack(curr->right); } return curr->val; } /** @return whether we have a next smallest number */ bool hasNext() { return !st.empty(); } }; main(){ vector<int> v = {7,3,15,NULL,NULL,9,20}; TreeNode *root = make_tree(v); BSTIterator ob(root); cout << "Next: " << ob.next() << endl; cout << "Next: " << ob.next() << endl; cout << ob.hasNext() << endl; cout << "Next: " << ob.next() << endl; cout << ob.hasNext() << endl; cout << "Next: " << ob.next() << endl; cout << ob.hasNext() << endl; cout << "Next: " << ob.next() << endl; cout << ob.hasNext() << endl; }इनपुट
BSTIterator ob(root); ob.next() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext()
आउटपुट
Next: 3 Next: 7 1 Next: 9 1 Next: 15 1 Next: 20 0
