BST Iterator ใน C++

สมมติว่าเราต้องการสร้าง Iterator หนึ่งตัวสำหรับต้นไม้ไบนารี จะมีสองเมธอด เมธอด next() เพื่อคืนค่าองค์ประกอบถัดไป และ hasNext() เมธอดเพื่อคืนค่า Boolean ที่บ่งบอกว่ามีองค์ประกอบถัดไปหรือไม่ ดังนั้นถ้าต้นไม้เป็นแบบ -

และลำดับการเรียกฟังก์ชันคือ [next(), next(), hasNext(), next(), hasNext(),next(), hasNext(),next(), hasNext()] ผลลัพธ์จะเป็น [3,7,true,9,true,15,true,20,false]

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• มีสองเมธอด next และ hasNext
• เมธอด next() จะเป็นแบบ -
• curr := โหนดบนสุดของ stack และ pop โหนดบนสุด
• ถ้า right ของ curr ไม่ใช่ null ให้ push inorder successor จาก right ของโหนด
• คืนค่าของ current
• เมธอด hasNext() จะเป็นแบบ -
• คืนค่า true เมื่อ stack ไม่ว่าง มิฉะนั้น false

ลองดูการนำไปใช้ต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่างโค้ด

#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