In a previous lesson I've basically skipped talking about how the traversal was actually implemented.
So if we kind of go up and look at the operator plus plus here you can see that it's a lot of manipulations
around the current pointer.
Now why is this so ugly.
I mean if you study computer science you know that the different kinds of tree traversals are very simple
because of procedures.
Now the problem is that we're not getting any recursion done here.
There is absolutely no recursion.
In actual fact and the reason why there's no recursion is because you simply have an operator plus plus
which gets executed one sort of plus plus at a time and you need to somehow preserve the state.
But there is no way of suspending execution and then resuming because if you could do that you could
write a proper recursive algorithm that people could actually read.
And instead we have this monstrosity which I'm not going to go through.
So is it possible to have your cake and eat it.
Is it possible to have an iterator which is actually recursive.
You might think.
No because operator plus plus is just you know a single thing that you call one at a time.
So how would you preserve the state of way you are in the overall recursion algorithm.
But it is actually possible it is possible things to code routines and code routines are a really cool
addition to C++ So we're going to take a look at how we can implement post order traversal.
But instead of writing all this horrible pointer manipulation code what we're going to do is we're going
to just write a normal readable algorithm.
So let's include a couple of things here.
I'm going to include experimental headers for code routine as soon as the line is happy to complete
things.
And also for the generator.
There we go.
OK so what we're going to do is we're going to implement a much simpler kind of iterator we're basically
going to reuse certain functionality that's available as part of the implementation of our core routines
and we're going to plug it into our tree class down below here somewhere and just augment it without
So what I'm going to do is I'm going to have a function called postal order and what it's going to do
is it's going to return a generator now a generator is iterable which means you can go through the generator
and generate all of these wonderful elements pointing to the right to the right structures basically.
So here we go experimental generators so we're going to return pointers to of.
And I'm going to call this post order.
So notice I'm not making a class I'm not implementing operator plus plus I'm not doing any of that essentially
because I'm really using existing functionality now in order to actually implement the generator we
need.
The whole thing to be recursive and a recursive function has to start somewhere.
So it has to start in our case at the root of the tree.
So I'm going to say I'm going to have a post order impulse I'm going to have an implementation which
will also take the route and that can be a private section of the class so let's have a private section
here.
And what I'm going to do is I'll have the generator it's going to be a signature similar to this one
post order imposed.
But I'm going to take the root node node of T.
No there we go.
So what I'm going to do is I'm going to check whether a node is now and if it's not now then I'm going
to go through all of the left elements and I'm going to yield every one of the left elements and this
is going to be a recursive operation.
So what I'm going to say is I'm going to say for Auto X in the first order simple of node left I'm going
to code yield x.
Don't worry about Cofield turning red.
It's not broken it's it's actually just fine.
So without them centrally doing as I'm recursively iterating the left elements and returning them in
a kind of suspended mechanism as I'm going through them.
So here is the code yield for the last parts and then I can copy this and I can simply code yield the
right bar.
So here we see.
Right.
And while I can call them something else I can call them white.
So you see that there is a difference between the two.
So I'm using those.
And and finally for a post or the traversal of the last element you traverse is the actual know that
you're wrong.
So Cofield code yield the node itself.
So this is how you would implement a post or the Traverse So you'll notice how much simpler and how
much cleaner the whole approach is compared to just essentially having one pointer and then manipulating
it in all sorts of different ways.
This is rather difficult to understand.
So with this implementation we can actually try it out.
We can actually go ahead and print something out or comment out just print it out so it doesn't distract
us.
So what you would say is you would say for Otto it's in family don't post war.
And that's pretty much it.
That's how you would do it.
And you get an iterator so you get a pointer and have to get the pointer value here because essentially
in this case in this particular case what the iterated variable itself is a pointer.
So you have an iterator to a pointer is a slight indirection here but that's OK.
We can get the value and we can print it.
Let's actually execute this just to see this wonderful thing work.
There we go.
So we have post all the traversal mother's mother mothers father mother father.
And finally me.
So what I'm trying to illustrate here is that this horrible idea of traversing a tree can be written
in idiomatic kind of way in a way where you can actually read the algorithm and it looks like the algorithm
reflects what you read in Wikipedia or computer science books and the way this is made possible is thanks
to coroutines.