ধরুন আমরা বাইনারি গাছের জন্য একটি পুনরাবৃত্তি করতে চাই। দুটি পদ্ধতি থাকবে। পরবর্তী এলিমেন্ট রিটার্ন করার জন্য next() মেথড এবং বুলিয়ান ভ্যালু রিটার্ন করার জন্য hasNext() মেথড, যা নির্দেশ করবে যে পরবর্তী এলিমেন্ট উপস্থিত আছে কি না। তাই গাছটি যদি −
এর মত হয়
এবং ফাংশন কলের ক্রম হল [next(), next(), hasNext(), next(), hasNext(),next(), hasNext(),next(), hasNext()]। আউটপুট হবে [3,7,true,9,true,15,true,20,false]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- পরবর্তী এবং hasNext দুটি পদ্ধতি আছে,
- পরবর্তী() পদ্ধতিটি − এর মত হবে
- curr :=স্ট্যাক শীর্ষ উপাদান, এবং পপ শীর্ষ উপাদান
- যদি curr-এর ডানদিকে শূন্য না হয়, তাহলে নোডের ডান দিক থেকে ইনঅর্ডার উত্তরাধিকারীকে চাপুন
- কারেন্টের রিটার্ন মান
- 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
