This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review “Unity” is a trademark or registered trademark of Unity Technologies or its affiliates in the U.S. and elsewhere. This course is an independent work and is not sponsored by, authorized by, or affiliated with Unity Technologies or its affiliates
Tree Traversal
Loading...
From the course by University of Colorado System
Data Structures and Design Patterns for Game Developers
12 ratings
University of Colorado System
12 ratings
Course 4 of 5 in the Specialization C# Programming for Unity Game Development
From the lesson
Stacks, Queues, and Trees
Meet the Instructors
Dr. Tim "Dr. T" ChamillardAssociate Professor
Computer Science
In this lecture, we'll look at a number of different ways that we can traverse a tree.
Specifically, we'll look at three different kinds of depth-first traversal,
we'll look at pre-order traversal,
we'll look at in order traversal,
and we'll look at post-order traversal and we'll
also look at breadth-first traversal of a tree.
This is the tree that we'll be traversing and I snagged this tree from
the tree traversal page on Wikipedia so you can
compare our results with those on the Wikipedia page if you'd like to do so.
This is a binary tree,
so each node can only have zero,
one or two children.
To support this lecture,
I implemented binary tree node and
binary tree classes so if you download
the lecture code for this lecture you can see how that works.
We regularly talk about left child and right child for each node,
we don't have a list of children we just have a left child and a right child.
Okay, let's go see how these traversal techniques work.
In the main method of our lecture code,
the first thing we do is we call a method that I wrote
to build the tree that I showed you a picture of.
And then we're going to demonstrate the pre-order traversal by
calling the pre-order traversal method and then we'll do an in-order traversal,
a post-ordered traversal, and then will do a breadth-first traversal as well.
So let's take a look at the pre-order traversal,
the pre-order traversal method is pretty straightforward.
First, we checked to make sure the node that was passed in and I'm calling
this perimeter tree because it really is a tree that is rooted at that node.
So we make sure the node that was passed in isn't
know that will be our indication that we should stop recursing,
we process the node first and by process here I just
mean we write the value of the node and then if
the left child isn't know we recursively call this method with the left child
and then if the right child isn't know
we recursively call the method with the right child.
So this is using recursion to do a traversal of the tree and
the pre-order part of the traversal means that we do the node then we do the left child,
then we do the right child.
So for the graph that are traversing you can see
that node F is marked as one so we process node F,
then we recursively call the method on the left child.
So here we are at Node B and we process that node and we
recursively call the method on the left child so we get to
A and we process that and then we return from
this recursion and now we call the method on the right child.
So we do D and then we recursively call on the left child.
So we have C on the right child so we have E and then we back up all the way through
these recursion back up to our root and that was just processing the left sub-tree.
So now we process the right sub-tree.
So we first get to G and we process G and G doesn't have a left child.
This is actually a right child of G so we will immediately process
the right child and that's I we process the node and then we go to the left child.
When I run the code,
if you look at the output of the node values in
the pre-order traversal that is
exactly what I said it would be as we walked our way through the picture.
So a pre-order traversal means we do the node then we do the left side,
then we do the right side,
and we do that recursively.
For an in-order traversal,
we traverse the left child first,
then we process the node,
then we traverse the right child.
So we don't do the node at the beginning here we do
the node between the left child and the right child.
For the graph where processing, as you can see,
we go as far down on the left as we can.
So we process A first and then we do B the node,
then we work our way down the right side,
but once we get to D remember we do left first so C
is next and then the node and then the right side,
and then we come all the way back up.
So we already did all this stuff on the left so we now
process F and we do the same thing on the right hand side.
Running the code again if you look at the in-order traversal output.
That's what I just said.
And by the way,
these are now in alphabetical order,
from A to I,
and for the last depth first traversal technique will look at
post order traversal and the difference here is we do the left side,
then we do the right side,
then we do the node.
So again we go as far down as we can on the left side,
so we do A and then we move up through B to D and go down on the left side.
So we do C next then we come up to D and back down and do the right side.
And then finally we do D and now we've done the left and the right side of B.
So we come process B backup the root.
Now we're going do the right side before we process the root.
So we come down here and we can still do
the right side before we process G and we can still do
the left side before we process I so left
side of I and back up here and I doesn't have a right child.
So now we just process I and back up to G and we've
done the non-existent left child into the existing right child.
So now we can process G and now because we did
the left side of the tree and the right side of the tree we can finally process the root.
And this time, you should look at the post-order traversal output and
see that that is the order that I said that this would be in.
And those are the three depth first traversal techniques
and you should recognize them as depth first
because we were working our way as deeply down
the tree as we could before we were doing things.
We do have a breadth-first traversal technique as well,
where we'll process the root,
and then we'll process everything one step away from the root,
and then we'll process everything two steps away from the root, and so on.
I implemented the breadth-first traversal method using
the technique that we used before when we were searching a graph.
So I have a search list here,
I don't need a path,
I'm just going to process each node so this is a little more simple than looking for
a path through the graph but I am using a search list and I'm adding to the end of it,
and I'm adding to the end of it because I'm doing
breadth-first search and I'm just gonna process that search list and
each time I'll pull the first thing off the front of
the search list and I'll process it and if there is a left child,
I'll add it at the end of the search list and if there's a right child,
I'll add it and the end of the search list.
And remember, this was the difference between depth first and breadth-first search.
In depth first search,
if we're using a search list we add to the front of the list but because we're doing
breadth-first search here I'm adding new nodes to the back of the list instead.
So this picture should not surprise you,
we process F first,
then we process B and G,
those nodes that are one step away from F,
then we process A, D, and I,
the nodes that are two steps away from F and then finally,
we process C, E,
and H. And as you can see,
for the output for the breadth-first traversal
that is exactly the order that I said it would be in.
To recap, in this lecture,
we saw a number of different ways to traverse a binary tree and we also saw
numerous examples of recursion in the depth first traversals that we implemented.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
