CPSC 170 A

Lecture 28 - Binary Trees

$ 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.

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

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

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:

• 1 2 3 4 5
• 1 5 4 2 3

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

>>> 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

• priority_queue.py
• binary_tree.py