UCR CS 14: Introduction to Data Structures and Algorithms

Summer 2003 / Class webpage

Lab 05

Remember:

• All programming assignments will be done under the Linux operating system, using standard programming tools for that environment.
• All programming assignments will be evaluated with the -Wall -Werror compilation options. If your program does not compile with these flags, it will not be evaluated.
• Concentrate some effort on style and documentation. A significant portion of your grade will be based on these aspects of your submission.
• You have to turnin your codes before you leave.
• Every part of your assignment (every file) must begin with our report template header:

// Course:            CS 14

// Lecture Section:   Enter your lecture section number here (1, 2, etc)
// Lab Section:       Enter your lab section number here (21, 22, etc)
// Assignment #:      Enter the assignment number here (1, 2, etc)

// First Name:        Enter your FIRST name here (eg, John)
// Last Name:         Enter your LAST name here (eg, Doe)
// ID Number:         Enter your ID number here (eg, 12-345-678)
// Email address:     Enter your UCR email address here (eg, jdoe@cs.ucr.edu)

// ===============================================================

In this lab, we will work with ADT binary search tree (chapter 10). Searching for a particular item is one operation for which the ADT binary tree is ill suited. The binary search tree is a binary tree that corrects this deficiency by organizing its data by value. Recall that each node n in a binary search tree satisfies the following three properties:

• n's value is greater than all values in its left subree T_L.
• n's value is less than all values in its right subree T_R.
• Both T_L and T_R are binbary search trees.

In this lab you will work using an implementation of a binary search tree. You will need the following files:

• BST.h - ADT binary search tree header.
• BST.cc - ADT binary search tree implementation.
• KeyedItem.h - KeyedItem header.
• TreeNodeBST.h - ADT binary search tree node header.
• TreeException.h - TreeException.h header.
• lab5.cc - program that reads values from keyboard and stores them in a binary search tree.
• makefile

Figure 1. UML diagram for the class BinarySearchTree

Given the recursive nature of a binary (search) tree, a good strategy for writing a C++ function that operates on a binary (search) tree is often first to write a recursive definition of the task. Given such a recursive defition, a C++ implementation is often straightforward. Today, you will implement a set of functions considering an ADT Binary Search Tree. You may implement each of the exercises in one function and print their results as a report, for example:

Enter a positive value (negative value to stop): 10
Enter a positive value (negative value to stop): 8
Enter a positive value (negative value to stop): 12
Enter a positive value (negative value to stop): 7
Enter a positive value (negative value to stop): 9
Enter a positive value (negative value to stop): 11
Enter a positive value (negative value to stop): 13
Enter a positive value (negative value to stop): 15
Enter a positive value (negative value to stop): -1

-------------------------------------------------
IN ORDER TRAVERSE:
7
8
9
10
11
12
13
15

a) ROOT: 10

b) NUMBER OF NODES: 8

c) SUM OF NODES: 85

d) SEARCH AND COUNT FOR VALUE: 13
   NUMBER OF COMPARISONS = 3

e) HEIGHT: 4

f) SEARCH FOR VALUES BETWEEN: 8
   AND: 12
   RESULT:
     8
     9
     10
     11
     12

g) PRINT STRUCTURED TREE:
     10
      8
       7
       9
      12
       11
       13
        15

h) INORDER TRAVERSE2:
7
8
9
10
11
12
13
15

i) INSERT NEW ITEM: 14
   NEW TREE:
     10
      8
       7
       9
      12
       11
       13
        15
         14

j) SAVE TREE IN THE FILE: out.txt

k) RESTORE TREE FROM FILE: out.txt
   NEW TREE:
     10
      8
       7
       9
      12
       11
       13
        15
         14

Note that some of these functions (a, b, c, e, f) will be added to lab5.cc, and others (d, g, h, i, j) to the ADT files (BST.cc, BST.h). Also, even though you do not have enough time to finish all bonus exercises during the lab, you should try to do them by yourself. The practice you will get from these exercises will help you with the Ternary Search Tree assignment. Keep in mind that only those exercises that you turn in during the lab will be considered in your grade.

Turn-in

Implement recursive functions that perform the following tasks on arbitrary binary search trees. Add this functionalities to the file lab5.cc:

a) Show the root value (Hint: this is straighforward without using recursivity).
b) Count the number of nodes in the tree. (Hint: If the tree is empty, the count is 0. If the tree is not empty, the count is 1 plus the number of nodes in the root's left subtree plus the number of nodes in the root's right subtree).
c) Find the sum of the elements.

Add the following function to the ADT Binary search tree (BST.h and BST.cc):

d) int searchCount (int value): If the value is not in the tree, return 0. Otherwise, return the number of comparisons until the value is found. Then, add a function to your lab5.cc that calls this implementation. Interesting experiment: create at least 3 different trees with the same numbers, and search for one of them. For example, search for 11 in the trees: 10, 8, 12, 7, 9, 11, 13; 9, 7,12, 10, 13, 8, 11; and 7, 8, 9, 10, 11, 12, 13. Try to understand the results.

Bonus, 2 points each

Add these functionalities to the file lab5.cc:

e) Find the height of the tree.
f) Show all items that have a search key in a given range of values.

Add these functions to the ADT Binary search tree:

g) printTree: print a tree according to the following schema:

1
 2
  4
  5
 3
  6
  7

which means, 1 is the root and has two children (2 and 3), 2 has two children (4 and 5) and 3 has two children (6 and 7).
h) inorderTraverse2: iterative version (non-recursive version) of inorderTraverse using a stack as auxiliary variable.
i) insertItem2: iterative version of insertItem.
j) saveTree: save a binary search tree in a given file.
k) restoreTree: restore a binary search tree from a given file.

NOTE: for the ADT bonus functions, implement an extra function (in lab5.cc) that calls each one of them and print their results.

Hints and considerations

Important ADT functions. Note that you may implement most part of the main exercises using the functions: rightSubtree(), leftSubtree(), rootData(), getKey(), and isEmpty().