CS 2420-20 Homework 8

Due: Tuesday, February 14th, 2012 9:10am

Start with avl.c from bst.zip.

Part 1 – Strings

Change the integer tree to a string tree, change the tests to use strings, and change the loop in main to work with string lines instead of integers from lines.

As a reminder, you’ll need to #include <string.h> and use the following C library functions:

1. strcmp(a, b) takes strings a and b and returns a negative number if a is less than b, a positive number if a is greater than b, and 0 if a is the same as b.
2. strdup(a) allocates a copy of the string a. You’ll need to use strdup(buffer) after reading a line in main, since the content of buffer as a string changes with each line read. Before calling strdup, you may want to remove a newline with buffer[strlen(buffer)-1] = 0.

Part 2 – Max and Min

Add (and test) get_max and get_min functions on non-empty trees that return a tree’s smallest and largest values, respectively.

Change main so that it prints the smallest and largest values in its tree (if the tree is not empty) before exiting.

For example, if you run the program with - as the command-line argument and then type apple, coconut, and banana followed by Ctl-D, then the program should print apple and coconut.