MENU

CS225 Exam3 Walkthrough

October 18, 2022 • Read: 1410 • Practice Exam,CS 225

exam3_1.png
 


Helper function add()

template <class T>
void Tree<T>::Iterator::add(Node* root) {
    /* first we move to the left child of the root */
    Node* node = root->left_;
    /* then we traverse all the way to the right, and
     adding all the nodes along the way if it is not nullptr*/
    while (node != nullptr) {
        stk.push(node);
        node = node->right_;
    }
}

 


Tree::Iterator constructor

template <class T>
Tree<T>::Iterator::Iterator(Tree::Node *root) : curr_(root) {
    // TODO: your code here

    /* if root == nullptr, just return it */
    if (root == nullptr) {
        return;
    }

    /* add all the nodes from right branch to the stack */
    Node* node = root;
    while (node != nullptr) {
        stk.push(node);
        node = node->right_;
    }

    /* Since the initlization "curr_(root)" is not the place we 
    want to start, the place we want is at the right most nodes, so we 
    have to reset curr_ to whatever on the top of the stack (which is 
    the rightmost node) */
    curr_ = stk.top(); 
    stk.pop();

    /* check the curr_->data_ != NULL, and during the loop we want 
    to make sure that stk never goes empty */
    while (curr_->data_ == NULL && !stk.empty()) {
        curr_ = stk.top(); // replace with top elements
        stk.pop(); // remove used nodes
        add(curr_); /* add all neighbors from curr_ (or previous top elements)
                in the stack */
    }

    /* if curr_ make to this point, curr_->data != NULL or curr_->data_ is 
    still NULL, since we do not know nodes in our stack is valid or not, 
    so we have to do a final check */
    if (stk.empty() && curr_->data_ == NULL) {
        curr_ = nullptr;
    }
    /* if code reaches here, curr is not nullptr and curr_->data_ != NULL */
}

 


Tree::Iterator::operator++

template <class T>
typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
    // TODO: your code here

    /* make sure stack is not empty before traverse */
    if (!stk.empty()) {
        curr_ = stk.top(); // replace curr_ with top()
        stk.pop(); // remove used node from stack
        add(curr_); // add curr_'s neighbors 

        /* same code to check curr_->data_ */
        while (curr_->data_ == NULL && !stk.empty()) {
            curr_ = stk.top(); // replace with top elements
            stk.pop(); // remove used nodes
            add(curr_); // add all its neighbors in 
        }

        /* same code to check curr_->data_ */
        if (stk.empty() && curr_->data_ == NULL) {
            curr_ = nullptr;
        }

    } else {
        curr_ = nullptr; /* set curr_ = nullptr if stack is empty 
                    (which means we are done) */
    }
    return *this;
}

 


Tree::Iterator::operator*()

template <class T>
T Tree<T>::Iterator::operator*() const {
    // TODO: your code here

    /* return default T if curr_ is nullptr (at the end) */
    if (curr_ == nullptr) {
        return T();
    }
    /* return the data otherwise */
    return curr_->data_; 
}
Last Modified: October 4, 2023
Archives QR Code
QR Code for this page
Tipping QR Code