CIT 595 - Computer Systems II

Spring 2011

C Refresher Lab #2


Introduction
This lab is intended for students who need a refresher in C programming, particularly with arrays and pointers. Choose the assignment that seems most appropriate for you. Be sure to ask the instructor if you need help!

You can attempt any of the tasks from the first refresher lab if you'd like, or try one of these:


EASY
Write a function that reverses a string. For instance, if the input string is "abc123", the string should be changed to "321cba". The function should modify the string, not create a new one. Use pointer notation in the function, not array notation. Test your function from "main" and show that the string is reversed.


HARD
A "binary search tree" is a data structure that consists of "nodes" that have associated values and pointers to two other nodes, specifically the "left" and "right" children. A root node is at the top of the tree, and the binary search tree has the property that, for any given node, the left child has a value that is less than that of the parent, and the right node has a value that is greater than that of its parent. For instance, you may have a binary search tree where the values are ints, like this:
root -> 7
       / \
      4   8
     / \   \
    1   5   9
Note that the node with 8 as its value does not have a left child (i.e., the pointer is null), and the nodes with 1, 5, and 9 as their values are leaf nodes (they have no children).

Implement a binary search tree by first creating a struct to represent a single node, and then a pointer called "root" to the root node of the tree. Then implement functions to add a value to the tree (being sure to put it in the appropriate place) and to determine whether the tree contains a particular value (by searching for it starting at the root).