Lecture thumbnail 0:00 / 0:00 As you’ve probably guessed, what we’ve really built in this standalone in order Iterator is a state
machine where the current reference is actually the state, and then we move from one state to another
using the Movenext method.
Now, the thing about C-sharp is that these state machines are actually made for you automatically when
you build something that yields an enumerable, and by using yield return and yield break, you can
control the flow of what this enumeration actually presents you with.
So let’s take a look at how this inorder iterator can actually be just an ordinary method.
So what I’m going to do is I’m make a different class.
Let’s make a class called Binary tree of T, and the binary tree is just going to be a kind of collection
of the different iteration methods.
So here all I really need is I need the root of the tree.
So I need node of t root.
I’ll make a constructor for it.
And then of course, if I want an inorder iteration process, all I have to do is I have to yield some
sort of property which returns an enumerable of node of t and I will call this.
So let’s have I enumerable of node of t and I will simply call this in order.
And in a similar way you can do preorder and post order processing.
So this is going to be a property which will have a getter only.
And here we’re going to yield all of the elements from node of T and we’re going to yield them in order.
Now the thing about this is I’m going to be using a lot of yield return this year would return that
because it’s very convenient and it makes the code more readable.
However, we still have this problem and the problem is that the state machine, which actually reads
the items, has to reference the current item being returned, which is the current item here.
So the question is, well, how do we do it?
Because there is no argument here.
If we had an argument like the current state, then we could do it in a recursive fashion, but we don’t.
So luckily with C-sharp seven, what you can do is you can embed a method right inside a method so you
can have inner methods effectively.
So we’re going to do a traversal, we’re going to implement a method which implements inorder traversal,
and it’s going to keep the state in that argument.
So here I’m going to make a method right in here.
I’ll make a method which returns an enumerable of node of T, and that method is going to be called
traverse in order, or we can just call it traverse because it’s already in order by definition.
So we’re going to traverse, given that we have the node of t current and this argument is going to
be the state part of our state machine effectively.
So what we’re going to do here is a lot more understandable, a lot better than what we had in the manual
implementation because all we have to do for inorder traversal is we first of all have to go to the
leftmost element and just yield return that element.
So if current dot left is not equal to null, then what we do is we go for each var left in and then
we do a recursive call.
So we call traverse with current left and we yield return.
Yield, return left.
That’s all we do.
So essentially this chunk of code, what it does you when you call this traverse and let me just show
you how this is going to be called.
We’re going to be using it like this.
We’re going to be saying for each var node in traverse in order with the root.
Actually we just call it traverse for each var node in traverse, we’re going to yield return node.
Unfortunately, we have to do these folded yield returns because there is no way to yield return an
enumerable, thereby expanding the whole enumerable.
There is no yield return, enumerable, blah blah blah.
Even though they want to add it to C-sharp, maybe it will be there at some point.
Anyways, what we do is we start with the root.
So you start with the root and current is equal to root, and then you go through the left part.
If there are left parts and you yield, return them recursively, then of course you yield return yourself.
So yield.
Return current and then you yield return the right part.
So instead of the left parts here, what you do is you simply yield, return the right parts.
So you say if current dot right is not equal to null, then you traverse on current dot.
Right.
And I’m going to rename this to a right just to be more readable.
So you traverse to the rightmost part and then you return this.
So that’s really it.
That’s all that you need to write in order to implement inorder traversal.
And we can now start using it straight away.
And the great thing is in this case, because we’re yielding an enumerable, we automatically get a
sequence of elements, we automatically get all the benefits of language integrated query so we can
just string them up together and output them.
So let’s do exactly this.
So I’m going to say var tree equals new binary tree of int specifying the root.
And after this, what I can do is I can write line all the elements just comma separated.
So I’ll do string dot join.
So I’ll have a comma separated elements and here all I have to do if I want to do a inorder traversal
is I say tree dot, I say in order which as you can see, returns an enumerable of node event.
And then I do a select where from each value I get x dot value like so.
And that’s really all there is to it.
So if I now execute this, you can see that we’re getting exactly the same result 213.
But the benefit of this, apart from not having to make a separate class, the benefit is that this
is readable, this is absolutely readable.
We have an inner function which does recursion, so we’re doing the whole process recursively.
We’re saying, first of all, we recursively process the left part of any current element and then we
process the right part.
So this is readable, this is understandable.
You can work with this, you can use it as a demo indicating, you know, if you’re teaching people
about the different forms of traversal, this is something you can actually understand, even though,
of course, behind the scenes what C-sharp does is it makes a horrendous state machine to implement
this particular method.
But on the other hand, if you look at the code that we built when we had the context and we had to
manage it between the different invocations of Movenext, we have ugly things like checking whether
or not we yielded the first value and then of course the implementation of traversing up the tree with
the parent temporary variable.
It’s just not understandable.
It doesn’t it doesn’t explain to you how the traversal actually works, whereas in this case, it’s
all nice and neat and understandable.
And this is what makes C-sharp such a great language to use.
Play Play Stop Play Play Start Play information alert