create traversal_iterators (high priority!)

[andrealorenzon]

implements and overloads the following operators:

++, --

(maybe) and the following methods:

next, last, begin, end, cbegin, cend

NOTE: end should not return the last element, but the element after the last!!!! probably returning nullptr is just fine. -> https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/treetraversal/page/treetraversal.html

[andrealorenzon]

https://github.com/andrealorenzon/AP_exam/wiki/iterators

[andrealorenzon]

https://stackoverflow.com/questions/4581576/implementing-an-iterator-over-a-binary-search-tree

[andrealorenzon]

Begin finder: return the node with the min(key):

    /**
       * @brief Finds the node with the minimum key
       * @return The node with the minimum key otherwise nullptr
       */
      const std::shared_ptr<Node> minimum() {
        std::shared_ptr<Node> x = root;
        if (x == nullptr) return nullptr;
        while(x->left != nullptr) x = x->left;
        return x;
      }

[andrealorenzon]

End finder:

    /**
       * @brief Finds the node with the maximum key
       * @return The node with the maximum key otherwise nullptr
       */
      const std::shared_ptr<Node> maximum() {
        std::shared_ptr<Node> x = root;
        if (x == nullptr) return nullptr;
        while(x->right != nullptr) x = x->right;
        return x;
      }

[andrealorenzon]

Next finder:

      /**
       * @brief Finds the successor of the node with key specified
       * @return The successor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<Node> successor(const K key) {
        std::shared_ptr<Node> x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->right != nullptr) {
              x = x->right;
              while(x->left != nullptr) x = x->left;
              return x;
            }
            std::shared_ptr<Node> parent = x->parent.lock();  // ????
            while (parent != nullptr && x == parent->right) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }

[andrealorenzon]

Last finder:

      /**
       * @brief Finds the predecessor of the node with key specified
       * @return The predecessor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<Node> predecessor(const K key) {
        std::shared_ptr<Node> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->left != nullptr) {
              x = x->left;
              while(x->right != nullptr) x = x->right;
              return x;
            }
            std::shared_ptr<Node> parent = x->parent.lock();   // ??????????
            while (parent != nullptr && x == parent->left) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }

[andrealorenzon]

A way to create iterators using stack STL data type is described here: https://codereview.stackexchange.com/questions/195919/generic-in-order-traversal-iterator-for-binary-trees