Giả sử chúng ta muốn tạo một trình lặp cho cây nhị phân. Sẽ có hai phương pháp. Phương thức next () để trả về phần tử tiếp theo và phương thức hasNext () để trả về giá trị Boolean, điều đó sẽ cho biết phần tử tiếp theo có hiện diện hay không. Vì vậy, nếu cây như -
Và chuỗi các lệnh gọi hàm là [next (), next (), hasNext (), next (), hasNext (), next (), hasNext (), next (), hasNext ()]. Đầu ra sẽ là [3,7, true, 9, true, 15, true, 20, false]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Có hai phương pháp next và hasNext,
- Phương thức () tiếp theo sẽ giống như -
- curr:=phần tử trên cùng của ngăn xếp và phần tử ở trên cùng của cửa sổ bật lên
- nếu bên phải của curr không phải là null, thì hãy đẩy phần kế tiếp inorder từ bên phải của nút
- giá trị trả về của hiện tại
- Phương thức hasNext () sẽ giống như -
- trả về true, khi ngăn xếp không trống, ngược lại là false.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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;
} Đầu vào
BSTIterator ob(root); ob.next() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext()
Đầu ra
Next: 3 Next: 7 1 Next: 9 1 Next: 15 1 Next: 20 0