Binary Tree

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

  1. 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.
  2. Visually examine the two graphs and write out the expected traversal orders for preorder, postorder, inorder, and breadth-first traversals.
  3. Enable the call to do_traversals in main 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 the BinaryTree 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., call function 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.
  4. Implement a breadth-first binary tree traversal. This traversal is not recursive, so it should be implemented entirely within the BinaryTree function breadth_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 the LinkedQueue implementation of the Queue ADT for this part of the lab.
  5. (Optional) Implement the random_add methods in both BinaryTree 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 the BinaryTree 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 to make_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.