Lecture 28 - Binary Trees


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

$ mkdir ~/cs170/labs/lab28
$ cd ~/cs170/labs/lab28

Class Outlines

It's that time to submit your class outlines for the sudoku solver programs. Are there any lingering questions before we get started? I will try to get comments uploaded as quickly as I can today, so you can start working on your solvers!


Priority Queues

Since Priority Queues went so terribly on Friday, let's go over them again today, with a more guided approach. I'll write the Priority Queue from scratch again today, and show you how the maze problem would have needed to have been solved on Friday.


Trees

Lists and Linked Lists are linear data structures. Data is associated with each other via the continuous nature of the structure. To get from one element, you need to traverse through all of the previous elements. However, not all information is related in such a linear way. Some data is better represented in a heirarchical manner. Today, you will begin learning about Trees: a heirarchical data structure similar to linked lists.


Lab Activity 1
Building a Binary Tree

A Binary Tree is a simple heirarchical data structure. In a Binary Tree, all nodes have at most 2 children. These are commonly referred to as the left and right children of that node. Another aspect of Binary Trees are the ordering of data: All of the data in the left sub-tree is less than (or equal to) the data in the parent, while all of the data in the right sub-tree is greater than the data in the parent.

Given this restriction on the ordering of data, you need to make sure things get inserted into the tree in the correct order. Luckly, this process is going to sound fairly familiar.

Details

In the binary_tree.py file, create a method in the BinaryTree class called insert(self, data). This method will take some data, and insert it into the correct location in the tree. Remember that all data is to be inserted at a leaf: Once the internal nodes are set, they cannot be changed.

Note that there are a couple of methods to accomplish this, but the easiest solution might (surprisingly) be recursive! You might need to write a helper function to accomplish this, however.

Example

>>> my_tree = binary_tree.BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(8)
>>> print(my_tree.root.data)
5
>>> print(my_tree.root.left.data)
3
>>> print(my_tree.root.right.data)
8
>>> my_tree.insert(4)
>>> print(my_tree.root.left.right.data)
4

Hint

  • You will need a special case for inserting the first element into the tree: Just create a node to represent the root of the tree.

  • You can only insert data at the leaves of a binary tree. This means you need to traverse down the tree until you locate a leaf that you can insert it. Given a node r, if data is less than or equal to r.data, and r.left is None, create a node at r.left for data. Otherwise, try the same process on r.left.

    the process for r.right is very similar.

  • I know it may seem counter-intuitive for most of you, but the recursive definition is so elegant that I even have trouble thinking of the iterative manner of insertion. It is possible, however.

 

Challenge

Binary Trees are actually how binary search gets its name. For a properly formatted tree, you can perform binary search in a tree in the same amount of time that we could perform it on a list. However, this requires a properly formatted tree...which is not a given with the above structure.

Write a method insert_list(self, a_sorted_list), which takes an ordered list of elements, and inserts them in the correct order for the binary tree for a "correct" binary search. Do you notice anything interesting about this code?


Lab Assignment 28
Depth-First Traversal

Just like with linked lists, we have a mechanism for building our tree. However, we don't have a good way of visualizing it. We need some method for printing out the structure to the terminal. That was easy to think of for a linked list. However, that's less obvious for a tree...how do we represent a tree in text as a string.

There are actually a couple of ways to print a tree out to the terminal: Depth-first or Breadth-first. Usually, we stick to Depth-first. In depth-first traversals, we traverse down an entire branch before we cover another branch. The nice thing about depth-first traversal are that they can be written recursively.

There are three versions of Depth-first traversals: pre-order, in-order, and post-order. We are going to focus on pre-order for today. I will show off the other two in class on Wednesday.

Details

In the binary_tree.py file, write a method called pre_order(self), which returns a string representation of the tree using pre-order traversal techniques. You want the entire string to be represented on one line: You should not insert any new lines in the string.

Pre-order traversals print the data at the root of the tree before they print the data from the children. Consider the following tree

Thanks Wikipedia!

Pre-order traversal would first output an 'F', since F is at the root. Then, It would perform the same operation on the left child. This would produce a 'B'. And again, the same process would execute on the left child of 'B', producing 'A'. 'A' Doesn't have any children, so we would backtrack to 'B', and run that process on the right child of 'B', producing 'D'. The full, pre-order traversal is:

F B A D C E G I H

Create some additional test cases to the one that I provide you below. Does the pre-order method of printing make sense? Can you easily draw the tree that a pre-order output represents? For the following pre-order strings, draw the represented tree in comments at the bottom of the binary_tree file:

Example

>>> my_tree = binary_tree.BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(8)
>>> my_tree.insert(4)
>>> print(my_tree.pre_order())
5 3 4 8

Hint

Again, this function is much easier to write recursively than iteratively. Again, you will need to write a helper function pre_order_helper(self, node), which takes a node and returns the string representation of the pre-order traversal from that node.

 

Challenge

The strings produced by the above algorithm are unambiguous. However, they can still take some time to parse. This is because a 2-dimensional structure is being represented by a 1-dimensional string. Maybe we can make this 2-dimensional?

Write a new method pre_order_2D(self), which returns a new string representation. Each piece of data will appear on its own line in this output, so if there are n nodes in the tree, there will be n lines in the output. For each piece of data output, you should output some number of spaces before the data. 2 spaces per depth seems to work well. You will need to write a helper function to accomplish this, and it will need to take additional parameters.

Example

>>> print(my_tree.pre_order_2D())
5 
  3 
    4 
  8 

Submission

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

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

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


In-Class Notes


Last modified: Mon Mar 31 14:02:16 EDT 2014