Lab 12

Wed, Sep 30, 2015

Binary Tree Lab

Objectives

The goal of this lab is to gain experience with the implementation of binary trees.

Introduction

Download the lab starter files here:

Don’t forget to download and customize your machine-specific makefile. For this lab, you will need to add three code modules to the MODS line: turtle.o, bintree.o, and drawtree.o.

In the drawtree.c file, 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:

turtle_draw_bintree - Draw a binary tree using turtle graphics

For this lab, you will modify the bintree.c file. We have provided a basic binary tree implementation with recursive size and height calculation routines: bintree_size and bintree_height, along with their recursive helper functions. Look over these definitions and functions and make sure you understand how they work. There are other stub methods in this file that you will be implementing in this lab.

In the main.c file, we also provide several routines for generating binary trees for testing. Two binary tree test cases 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. The main function also 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.
Implement the three recursive traversals (preorder, postorder, and inorder). This will require you to implement recursive traversal functions that take a bintree_node_t parameter, as well as a wrapper routine that takes a bintree_t parameter and delegates to the recursive function (starting at the root). Here are the three traversals:

bintree_preorder - Visit the current node first (i.e., print its value), then recursively traverse the left child and the right child if they are present.

bintree_postorder - Recursively traverse the left and right child subtrees, then visit the current node.

bintree_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 bintree_breadth_first function. Here is the pseudocode for a breadth-first traversal:
```
Algorithm breadth_first(T):
    initialize queue to contain T.root
    while queue not empty do
        p = dequeue()
        visit p
        for each child c in p.children do
            enqueue(c)
```
We recommend using a simple array-based queue implementation, because the maximum element count can be calculated using bintree_size.
Implement bintree_free, which should recursively free all of the nodes in the tree. Should this be a preorder traversal or a postorder traversal?

(Challenge) Random Binary Trees

Implement the random_add function, which should add the given element at a randomly-selected (as described below) leaf location in the binary tree.

At the bintree_t 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 bintree_node_t 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 simulate a coin flip:

    if (rand() % 2 == 0) {
        // go left
    } else {
        // go right
    }

After you have implemented these routines, you should be able to 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?

John Bowers