class const_iterator {
public:
Node *current;
const_iterator (Node *n) : current{n}
{
/* the body can remain blank, the initialization is carried
* the the constructor init list above
*/
}
/* copy assignment */
const_iterator operator= (const const_iterator& rhs) {
this->current = rhs.current;
return *this;
}
bool operator == (const const_iterator& rhs) const {
return this->current == rhs.current;
}
bool operator != (const const_iterator& rhs) const {
return this->current != rhs.current;
}
/* Update the current pointer to advance to the node
* with the next larger value
*/
const_iterator& operator++ () {
/*first step is to go left as far as possible(taken care of by begin())
once you go as left as possible, go right one step at a time*/
if(current->right != nullptr){
current = current->right;
//every step, go left again as far as possible
while(current->left != nullptr){
current = current->left;
}
}else{
bool upFromLeft = false;
bool upFromRight = false;
while(upFromLeft == false && upFromRight == false){
//if you have gone all the way up from the right
if(current->parent == nullptr){
upFromRight = true;
current = current->parent;
return *this;
}
//if you have gone all the way back up left
if(current->parent->left == current){
upFromLeft = true;
current = current->parent;
return *this;
}
current = current->parent;
}
}
return *this;
}
Z& operator *() const {
return current->data;
}
};
ADD these functions to your tree in order to use the begin() and end() with your iterator
const const_iterator begin() const {
if(rootPtr == nullptr){
return nullptr;
}
Node* temp = rootPtr;
while(temp->left != nullptr){
temp = temp->left;
}
return const_iterator(temp);
}
/* For the "end" marker
* we will use an iterator initialized to nil */
const const_iterator end() const {
return const_iterator(nullptr);
}
Here's an example of an in-order iterator I wrote in C++...
This iterator assumes that each node in your BST has a pointer to the parent node which is something I don't see in your node class. However, I am not sure its even possible to accomplish an inorder traversal without having a parent pointer.
In short, this example will work if you add a parent pointer to your nodes and update your parent pointers every time you do a node insertion or removal