< Back

Lecture 29 - Binary Tree Finale

As usual, create a directory to hold today's activities: 

$ mkdir ~/cs170/labs/lab29 
$ cd ~/cs170/labs/lab29

Program Outline

It's that time once again. Please hand in your class outlines for the Akinator program! I will try my best to get these back to you later today, if not by tomorrow morning.

Breadth First traversal

You saw last week that depth-first traversal explores the entirety of a branch before it explores the rest of the tree. This is great a majority of the time. However, there are times where this is less desirable. One final type of traversal is a Breadth-First traversal. A breadth-first traversal essentially explores the entirety of a level of the tree before moving on to further elements.

We can easily write the depth-first traversals using recursion because the simplest manner of performing that type of exploration is using a stack. Breadth-first, however, uses a queue for its exploration mechanism.

Lab Activity 1
Breadth-First Traversal

In depth first traversal, we always traversed all the way down one entire branch, before starting to explore another branch of the tree. This led us to having essentially three different forms of depth-first traversals: in-order, pre-order, and post-order. Another form of traversal is known and Breadth-First: It explores all of the nodes at the same depth, before exploring the nodes at a subsequent depth.

We saw this same mechanism at work in our paint bucket programs. If we used a stack, we would essentially try to fill in a weird spiral pattern. With a queue, we would radiate out from the central point. This analogue applies here as well: depth-first uses a stack, which breadth-first uses a queue.

Details

Copy your binary_tree.py file from last class into your current directory: 

$ cd ~/cs170/labs/lab29
$ cp ../lab28/binary_tree.py .

Add a new method to your BinaryTree class called breadth_first(self). This function should return a string, representing the breadth-first traversal of the current tree.

Example

>>> my_tree = BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(4)
>>> my_tree.insert(8)
>>> my_tree.insert(7)
>>> my_tree.insert(6)
>>> print(my_tree.breadth_first())
5 3 8 4 7 6

Hint

  • For once, I am going to urge you to not write this function recursively. It is possible, but adds unnecessary complications to the entire function.

  • Create a queue at the beginning of the program, and add the root of the tree to the queue. This is going to be the initialization of your entire algorithm.

  • You are going to loop through the entire queue. You will pull the front element off the queue, and concatenate that to the end of a string you will return from this function. Then, you will try to enqueue the two children of that node into the queue. Make sure you don't enqueue any None nodes!

 

Challenge

One of the issues with breadth-first traversal is it is unclear which elements are children of other elements. This is partially because an element could appear in multiple places in the tree, depending on when it was inserted. This is especially true for trees that are not well balanced: The tree structure is completely abstracted away!

One simple solution is to make sure that the entire tree is represented in the traversals....even "None" leaves. Write a new method called breadth_traversal_complete(self), which also inserts "None" into the output string for locations that terminate within the tree. Does this completely solve the problem?

Submission

When you have finished, create a tar file of your lab29 directory. To create a tar file, execute the following commands: 

cd ~/cs170/labs
tar czvf lab29.tgz lab29/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 29. Make sure you include a header listing the authors of the file.

Class Notes