CS 211 - Programming Practicum

Lab 12 - Binary Trees

Due Wednesday, 11/28/12

For ths lab you are to write a C program that will perform the following operations on a binary tree.

  • add
  • empty
  • list items in "in-order"
  • list items in "pre-order"
  • list items in "post-order"
The binary tree is to contain one integer vaue per node. A structure for the binary tree could be:
typedef struct bnodestruct
{
int elem;
struct bnodestruct* left;
struct bnodestruct* right;
} bnode;

typedef bnode* bnodePtr;
We will be using a binary tree form called a "binary search tree". The items in the tree are to be stored in increasing order from "left" to "right" in the tree. What this means is that all values in the left subtree of a node will be less than the element of the node, while all values in the right subtree of a node will be greater than or equal to the element of the node. Consider the following tree:

Binary_search_tree.png

Note that the node at the top (or "root") of the tree has the value of 8. The left subtree of this node contains only values less than 8. The right subtree contains only values greater than (or equal) to 8.

To determine if a value is in the tree, we start seaching at the root. If the root pointer is empty (i.e. is a NULL pointer), we return a FALSE value and stop. If the root node contains the value we are looking for, we return a TRUE value and stop. If we are looking for a value that is less than the value in this node, we search the left subtree. Otherwise we search the right subtree. We treat the subtree as its own tree with the top node of he subtree as the new root.

If we wanted to determine if 4 was in the above tree, we would

  1. first check the node with element of 8. Since 4 is less than 8, we search the left subtree and
  2. then check the node with element of 3. Since 4 is greater than 3, we search the right subtree and
  3. then check the node with element of 6. Since 4 is less than 6, we search the left subtree and
  4. then check the node with element of 4. Since 4 equals 4, we return TRUE and stop.
If we wanted to determine if 5 was in the above tree, we would
  1. first check the node with element of 8. Since 5 is less than 8, we search the left subtree and
  2. then check the node with element of 3. Since 5 is greater than 3, we search the right subtree and
  3. then check the node with element of 6. Since 5 is less than 6, we search the left subtree and
  4. then check the node with element of 4. Since 5 is greater than 4, we seach the right subtree and
  5. then we find this subtree is empty. We return FALSE and stop.
When inserting a value into the tree, we all insert a new node at an "empty" spot in the tree. The "empty spots" are those positions that have a NULL value in the left or right pointer values. If this was a linked link, the similar idea would be to insert a new node at the end of the linked list.

To determine which NULL pointer to have point to the newly inserted node, we must properly search through the tree until we find a NULL pointer. The then replace this NULL pointer with a pointer to the newly inserted node. The following is psuedocode describing this action:

set curr to root of tree

while ( curr is not NULL)
{
if (value to insert is less than element at curr)
set curr to left subtree of curr
else
set curr to right subtree of curr
}
Insert new node at curr
Thus inserting the value of 5 into the above tree, we would following the same search routine as described above. Once we found that the right subtree of the node with 4 is empty, we would replace that NULL pointer with a pointer to the newly create node contain the value of 5.

The input for the operations will be as follows:

q - quit the program

a <int> - add the integer value into the binary tree. The items in the tree are to be stored in increasing order from "left" to "right" in the tree. What this means is that all values in the left subtree of a node will be less than the element of the node, while all values in the right subtree of a node will be greater than or equal to the element of the node.

e - empty all values from the binary tree. Be sure to properly deallocate the nodes.

i - list the items contained in the binary tree in "in-order". This means that for every node in the tree, you list the values in the left subtree first, then list the element in the node next, and finally list the values in the right subtree. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

r - list the items contained in the binary tree in "pre-order". This means that for every node in the tree, you list the element in the node first, then list the values in the left subtree next, and finally list the values in the right subtree. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

p - list the items contained in the binary tree in "post-order". This means that for every node in the tree, you list the values in the left subtree first, then list values in the right subtree next, and finally list the element in the node. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

The "in-order" listing of the above tree would be: 1 3 4 6 7 8 10 13 14

The "pre-order" listing of the above tree would be: 8 3 1 6 4 7 10 14 13

The "post-order" listing of the above tree would be: 1 4 7 6 3 13 14 10 8

Program Submission

Your are to submit the programs for this lab via the Assignments Page in Blackboard.

To help the TA, name your file with your net-id and the assignment name, like:

  • ptroy1LabX.c

Submit this file via the Assignment Link for the Lab in Blackboard.

  1. In the CS 211 Web Pages in Blackboard, go to the Assignments Page
  2. Click on the link for the correct lab. This will open a web page with the title: "Upload Assignment: Lab X", where X is the number of the lab
  3. Scroll down and click on the button "Browse for Local File"
  4. Select the file that you created that contains the program. Then click OK.
  5. Repeat steps 3 and 4 for your second program.
  6. Click the submit button on the "Upload Assignment: Lab X" page.
  7. You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.
-- Main.troy - 2012-11-20
Topic attachments
I Attachment Action Size Date Who Comment
PNGpng Binary_search_tree.png manage 6.3 K 2012-11-20 - 18:51 UnknownUser  
Topic revision: r2 - 2012-11-21 - 17:33:34 - Main.iswift2
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF