a. The annotation in Display 17.36 says that a real SearchTree template class should have a copy constructor, an overloaded assignment operator, other overloaded operators, and other member functions. Obtain the code for Display 17.36 and add declarations for the following functions and overloaded operators: the default constructor, copy constructor, delete, overloaded operator, =, makeEmpty, height, size, preOrderTraversal, inOrderTraversal, and postOrderTraversal. The functions preOrderTraversal, inOrderTraversal, and postOrderTraversal each call a global function process to process the nodes as they are encountered. The function process is a friend of the SearchTree class. For this exercise, it is only a stub.

Supply preconditions and postconditions for these functions describing what each function should do.

The function height has no parameters and returns the height of the tree. The height of the tree is the maximum of the heights of all the nodes. The height of a node is the number of links between it and the root node.

The function size has no parameters and returns the number of nodes in the tree.

The function makeEmpty removes all the nodes from the tree and returns the memory used by the nodes for reuse. The makeEmpty function leaves the root pointer with the value NULL .

b. Implement the member and friend functions and overloaded operators. Note that some of the functions listed here are already implemented in the text. You should make full use of the text’s code. You should test your package thoroughly.

c. Design and implement an iterator class for the tree class. You will need to decide what a begin and end element means for your searchTree , and what will be the next element the ++ operator will point to.

Hint 1: You might maintain a private size variable that is increased by insertion and decreased by deletion, and whose value is returned by the size function. An alternative (use this if you know calls to size will be quite infrequent) is to calculate the size when you need it by traversing the tree. Similar techniques, though with more sophisticated details, can be used to implement the height function.

Hint 2: Do these a few members at a time. Compile and test after doing each group of a few members. You will be glad you did it this way.

Hint 3: Before you write the operator, =, and copy constructor, note that their jobs have a common task— uplicating another tree. Write a copyTree function that abstracts out the common task of the copy constructor and operator, =. Then write these two important functions using the common code.

Hint 4: The function makeEmpty and the destructor have a common tree destruction task.