In this lesson we're going to take a look at how to actually implement a fully fledged iterator and
we're going to build an iterator for a binary tree so in order to construct a binary tree we have to
begin with a single node of that tree.
So let me define that no.
So I'm going to have a template type name T struct node and the node is going to store the values will
have t value can be initialized with the default constructor but we're also going to have different
kinds of pointers.
So if you have a no that may actually Droi a very simplistic diagram here.
So we have a tree with the Roots element A and then we have a bunch of children let's call them B and
C like so sarcastic B in here.
Stick seen here is so A is the root node and then it has children B and C but of course it can also
have parents of its own.
And we might also want to keep a reference to the overall tree right inside every single node.
So I'm going to have a couple of points here to know if t.
So I'm going to have a pointer to the left child which I will initialize with now PTO are going to be
a right child.
Also know ETR and then also in reference to the parent.
Now while a pointer to the parent to be precise.
And then we'll have a pointer to the overall tree.
So let me forward declare it here template tightening the struct binary tree.
And now I can make a pointer to it so binary tree of type.
He pointed to tree once again with no PDR so we can build some constructors for the node.
Let's first of all make a constructor which just takes a value so we just take the value and assign
it basically.
But we also have a constructor which takes the value as well as the left and right child.
So let's have a constructor which takes the value of the left and the right and in here what we can
do is we can for example set the tree of the children because remember everybody has a pointer to the
tree so we can share our own pointer by doing this left tree equals this right tree equals tree.
And we can also set the parent of the children of this node to ourselves so that we can save this left
parent equals this right parent equals this.
There we go.
So this is how you can set up a tree as well as set some of the important properties of its children.
OK.
Well I also have a utility function for setting the tree pointer
so we'll take a binary tree pointer like this T and said it it was say tree equals t..
But in addition what we'll do is we'll also said it recursively.
So we say get left.
So we have a left child then we call left said tree C and we'll duplicate this for the right
go right.
So there we go.
OK so let's have a destructor where we delete the left and right nodes.
Now I'm not using smart pointers here so I'm going to just assume that the node owns all of its children
so the destructor for the node is basically going to say if left delete left right.
Right.
There we go.
All right so now we can build a binary tree which is simply a wrapper around the root node because remember
it could just be using ordinary nodes to build the entire tree but we're going to have a wrapper so
that we have a place where we can give out the iterator.
So let's have that template type named the struct binary tree and here will just have a pointer to the
root element.
So it will have no t pointer called Root initially and LPT are.
And then we can build the constructor so we can build a constructor where we take the root.
And here in addition to assigning the root we can also do a couple of other things like for example
we can set the tree we can take the root and say roots tree this.
So that way the entire tree every single element in that tree can set the appropriate root and has a
pointer to the tree itself and we can have a destructor here.
So if fruit really works.
Right.
So having said this up what we can do is we can finally build an iterator.
So we're going to build a pre order iterator and I'm not going to go in-depth as to the implementation
because the implementation using the begin and end paradigm is actually particularly unpleasant.
But what we need in the iterator is we need a few simple things like OPERATOR A plus plus an operator
store for example.
That's that's pretty much all that we're going to need here.
So let me define the iterator.
So I'm going to have a template type name.
Let's use the letter you here.
Struct pre order iterator.
There we go and I'll have I pointed to the current note the know that we are currently iterating.
So that's going to be no the view point at current.
So when we construct the iterator we need to set the current No.
Let me actually make the constructor here like so.
OK so having said this.
But we can do is we can then implement a few other operators like for example we can implement operator
not equals.
Comparing it to some other iterator.
So bool operator not equals where we take a cost or their order iterator.
Have you reference other and we simply make sure that when pointing to the same element so we return
current is not equal to the current.
That's all that we need to do because remember when we do these four loops where we say until something
is not equal to whatever.
And that's the not equals operator that's when it comes into play and we simply compare the elements
we're actually pointing to.
That's pretty much all that we can do in this particular case.
So what we can now do is we can do the difficult thing which is implementing operator plus plus So when
we're traversing the tree and we're traversing it pre order.
What's happening is every time somebody calls plus plus we need to move to the subsequent elements of
the tree and this is a particularly tricky operation.
So instead of actually going through the motions here I'm going to just paste in an example that I've
done already.
So as you can see because we don't have any way of kind of asynchronously yielding the elements it becomes
a really ugly chunk of code.
I mean I could go through this particular implementation with you but essentially this is the preorder
traversal as you would do it if you just had a pointer that you would keep on modifying as you go through
the elements.
OK so finally we need operator star for sort of dereferencing the iterator so I know the view reference
operator star where you would return star current remember using the current variable to point to the
note that we're currently on.
So operators are here would simply go in front of current and that would give you a reference to the
to the appropriate node.
So this is how you essentially make a preorder iterator and then coming back to the binary tree let's
suppose that we make the preorder is radio the default iterator on the binary tree.
So if somebody uses a range base for loop they get pretty order iteration.
So the question is well how do we do this.
Well in order to do this what we can do.
And let me actually just verify that this is the end of the iterator so to put the order iterator here
the way we do this is let's first of all do a typedef where we define our iterator.
So I'm going to kibe def create order iterator of T integrate.
Now we need to implement the begin and end functions.
So essentially we can say iterator begin.
So when we actually begin once again the implementation here is going to look something like the following.
Let me just paste this in here.
So what we're doing is we're getting a pointer to the roots and then we're following the left element
until the end.
So we follow until the leftmost element and that's when we return the iterator.
So notice the iterator doesn't start at the start so the left most element because that's the most efficient
way of doing pre order iteration and then of course if you want iterator and and the end function here
we don't do anything sophisticated here because remember there is no one after the last element for
a tree.
So what happens typically is you would after you've exhausted all the options you would have a null
PDR as the terminating element and that's exactly what we had here.
So we return an iterator which takes a LPT or.
And remember we have operator not equals which is going to be fine in terms of figuring out that we've
actually reached the very end.
So having constructed all of this we can now try and build what let's say let's build a family tree.
So what I'm going to build is something like the following.
So I'm going to build a family tree that's defined like this.
So there is me on top and then I have two leaves mother and father and mother has two leaves mother's
mother and mother's father.
So in order to define the actual binary tree I'm going to define it in terms of node nodes obviously.
And here is the kind of definition that I would typically use so you have a family.
I'm at the top of the tree and then sort of the parents are the children of the tree it's kind of reversed
not how you would do a typical genealogy diagram it's kind of in reverse but it doesn't really matter
we have this tree and we want to traverse it and the traversal is very easy.
What we can say is we can say for auto It was a family begin.
So that's calling our implementation of begin.
It's not equal to a family dog.
And plus plus it.
And then we can print out the names so we can see out star its star its value followed by a line break
here.
OK.
So this is pretty much it.
Let's actually execute this and see what we get.
All right.
And as you can see we're getting the correct order of iteration so we're starting at the leftmost node
which is here and we'll getting mothers mother and mother then mother's father then me and then father
and in a similar fashion you can implement other modes of iteration by simply making other iterator
classes.
Here I've used a nested class so we have a class called binary tree and inside that we have the preorder
iterator that I've just been using as the default because that's how I implemented beginning and end.
But boy you could do is you could get rid of begin and you could say that there is no default iteration
mechanism for a tree but you could then subsequently expose different kinds of iterators and allow people
to basically instantiate the iterator that they want and then go through it to print out the actual
elements.
So for example let's suppose that you wanted to communicate the idea of supporting print or traversal
of what you could do right inside of the class that we have here which is the order.
While the binary tree itself what you can do is you can make another class.
Let's find a place to stick it maybe in here.
You could make a class called pre the traversal for example.
So class three quarter traverse So where you would have the binary tree reference for example by tree
reference tree.
And then let's have some public members so this is where you would maybe initialize that reference and
you would also expose begin and end so iterator begin where you return to the begin.
And similarly iterator and the way you would return tree and tree not.
And like so and then you would make a variable of this type right inside the class or you could call
this for example preorder and then what you can do is if you go up here you could initialize preorder
in the constructor of the tree itself.
So here I notice it's already complaining so add a field called pre order and well let's actually just
do this by hand so you would say pre order stop this because you want any reference to yourself in pre
order.
And as a consequence instead of writing it in the following fashion instead of going through auto I-T
equal family begin family thought and what you could do is you could use that pre order member as a
way off iterating so you could say something like the following you say for example Konst auto it in
family doc preorder and then you could proceed to iterate the members as before and you would get you
would get the same results basically at least in this case.
So this is how you would essentially simplify things if you wanted to expose multiple iterators of different
kinds.