Bộ lặp cây tìm kiếm nhị phân trong C++

Giả sử chúng ta muốn tạo một bộ lặp cho cây nhị phân. Sẽ có hai phương thức. Phương thức next() trả về phần tử tiếp theo, và hasNext() trả về giá trị Boolean cho biết phần tử tiếp theo có tồn tại hay không. Vì vậy, nếu cây như sau:

Và chuỗi các lời 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 bài toán này, chúng ta sẽ làm theo các bước sau:

• Có hai phương thức next và hasNext,
• Phương thức next() sẽ như sau:
• curr := phần tử đỉnh stack, và pop đỉnh stack
• nếu phải của curr không null, thì đẩy kế thừa inorder từ phải của node
• trả về giá trị của current
• Phương thức hasNext() sẽ như sau:
• trả về true, khi stack không rỗng, ngược lại false.

Hãy xem 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