Binary Tree Lab
Objectives
The goal of this lab is to gain experience with the implementation of binary trees.
Introduction
Download the following files:
In the linked_queue
module, you will find a basic queue
implementation using circularly-linked lists. You may wish to use this
collection during this lab. The class is called LinkedQueue
, and it
has the standard Queue ADT operations:
class LinkedQueue: __init__(self) Create an empty queue __len__(self) Return the size of the queue is_empty(self) Return True if the queue is empty enqueue(self, element) Add element to the back of the queue first(self) Return (but do not remove) the front element dequeue(self) Return and remove front element
In the draw_tree
module, you will find Turtle-based code to
draw visual representations of trees. The details of the implementation are
interesting but unimportant to this particular lab. There is a single top-level
function in this module that we will use:
draw_tree(tree) Draw a binary tree using turtle graphics
For this lab, you will modify the binary_tree
module. We have
provided a basic BinaryTree
and associated _Node
classes as well as constructors and recursive length and height calculation
routines (__len__
and height
, respectively). Look over
these definitions and functions and make sure you understand how they work. There
are other stub methods in these classes that you will be implementing in this
lab.
In this lab, all traversal routines take a function as a parameter. Each
traversal will call the given function once per node in the tree, passing in
that node as a parameter to the function. The order of calls will be determined
by the type of traversal. We have provided a simple print_element
function that you can use in this lab to verify that your traversal routines are
working properly.
We also provide several routines for generating binary trees for testing.
Two test trees are hard-coded and available by calling the
make_small_tree
and make_large_tree
functions. There
is an additional tree generation function (make_random_tree
) that
you can use for testing if you complete the optional portion of this lab. We
also provide a function called do_traversals
that performs four
different traversals on a given binary tree.
Exercises
- Run the code without modification and observe the results. Change the
main
function to disable the small graph and enable the larger graph, then re-run the code and observe the differences in the resulting diagram. Check the "length" and "height" printouts and make sure you understand those numbers. - Visually examine the two graphs and write out the expected traversal orders for preorder, postorder, inorder, and breadth-first traversals.
- Enable the call to
do_traversals
inmain
and implement three different recursive traversals. This will require you to implement those functions in the_Node
class. You should also look at the corresponding functions in theBinaryTree
class to see that they delegate to the recursive implementation, starting with the root node of the tree. Here are the three traversals:preorder
- Visit the current node first (i.e., callfunction
on the current node's element), then recursively traverse the left child and the right child if they are present.postorder
- Recursively traverse the left and right child subtrees, then visit the current node.inorder
- Recursively traverse the left child, then visit the current node, then traverse the right child subtree.
- Implement a breadth-first binary tree traversal. This traversal is not
recursive, so it should be implemented entirely within the
BinaryTree
functionbreadth_first
. Recall the pseudocode for a breadth-first traversal:Algorithm breadth_first(T): initialize queue Q to contain T.root while Q not empty do p = Q.dequeue() visit p for each child c in p.children do Q.enqueue(c)
You should use theLinkedQueue
implementation of the Queue ADT for this part of the lab. - (Optional) Implement
the
random_add
methods in bothBinaryTree
and its_Node
class. This node should add the given element at a randomly-selected (as described below) leaf location in the binary tree.
At theBinaryTree
level, this routine should first check to see if the tree is empty; if it is, it should set the root of the tree to be a new node with the given element. Otherwise, it should begin the recursive process of inserting the element into a randomly-selected subtree, starting with the root.
At the_Node
level, the insertion routine should perform a coin flip to choose between the left and right subtrees. If the current node has no corresponding child on that side, the routine should insert a new leaf child node with the given value. Otherwise, the routine should recursively descend into the appropriate subtree, where it will repeat the process beginning with a new coin flip.
You may use the following code to correctly simulate a coin flip:if random.randrange(2) == 0: go left else: go right
After you have implemented these routines, you should enable the calls tomake_random_tree
to generate and analyze larger random trees. Verify that the length (node count) of the tree is correct and note that the height of the tree grows logarithmically with the total number of nodes. Can you explain why this happens?
Submission
This lab will not be graded so there is nothing to submit. Make sure you keep a copy of your code for future reference. If you would like to discuss your solution or any problems you encounter while working on this lab, please come to office hours or make an appointment.