मान लीजिए हम बाइनरी ट्री के लिए एक इटरेटर बनाना चाहते हैं। दो तरीके होंगे। अगला () विधि अगले तत्व को वापस करने के लिए है, और hasNext () विधि बूलियन मान वापस करने के लिए है, जो इंगित करेगा कि अगला तत्व मौजूद है या नहीं। तो अगर पेड़ जैसा है -
और फ़ंक्शन कॉल का क्रम [अगला (), अगला (), है नेक्स्ट (), अगला (), है नेक्स्ट (), अगला (), हैनेक्स्ट (), अगला (), हैनेक्स्ट ()] है। आउटपुट [3,7,true,9,true,15,true,20,false]
होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- आगे दो तरीके हैं और अगला है,
- अगला() तरीका इस तरह होगा -
- curr:=स्टैक टॉप एलिमेंट, और पॉप टॉप एलिमेंट
- यदि curr का अधिकार शून्य नहीं है, तो नोड के दाईं ओर से क्रमागत उत्तराधिकारी को धक्का दें
- वर्तमान का वापसी मूल्य
- है नेक्स्ट () विधि इस तरह होगी -
- सही लौटें, जब स्टैक खाली न हो, अन्यथा गलत।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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