Name ___________________

**CPTR246 Spring '99 (**100 total points)** Exam 3**

__Trees__: Answer the following questions based on the tree given.

(picture won't display - substitute any old tree with integers labeling the nodes.)

- What is the value located at the
*root*of the tree? (5 points) - How many
*leaves*does the tree have? (5 points) - Give the
*breadth-first*listing of the nodes. (5 points) - Give the
*preorder*listing of the nodes. (5 points) - Give the
*postorder*listing of the nodes. (5 points) - Give the
*inorder*listing of the nodes. (5 points)

- Template functions: (10 points)
- Operator overloading: (10 points)

Write a template function called *displayArray* that displays arrays of objects. It should take two parameters: the array of objects and the number of objects in the array. Examples of its use would be as follows:

int testScores[100];

int numberOfScores;

double monthlyAverages[12];

printArray(testScores, numberOfScores);

printArray(monthlyAverages, 12);

Below is the definition for the *employee* structure along with the definitions for two employee objects. We want to be able to "compare" two employee objects to see which is "less" using the '<' operator. You are to give the necessary C++ code to overload the '<' operator - but **YOU** define what is means for one employee to be less than another.

struct employee { // defines employee "type"

int ID; // employee id number

double hourlyRate; // pay rate

char name[30]; // employee's first name

double hoursThisWeek; // hours this week

};

employee emp1;

employee emp2;

. . .

if (emp1 < emp2){ . . . .

- In English, what do you mean when you say one employee is "less than" another? (NOTE: There are many, many correct answers here!)
- Give the C++ code to overload the '<' operator for employees.

- Recursion: There is an interesting series of integers known as the Fibonacci numbers. The first Fibonacci number is 0; the second is 1. As for the rest of the numbers in the series, each is equal to the sum of the previous two numbers. That is,
__Recursion__: (20 points)- Referring again to the class definition for the BinaryTree class,
__rewrite____the InTree member function as a__. Because of the special tree structure (that is, all nodes in the left subtree have values less than this node and all nodes in the right subtree have values greater than this node), we can determine if a value is in the tree directly, that is without using recursion. (15 points)**non-recursive**function

Fib(0) = 0

Fib(1) = 1

Fib(2) = 1 (It is 0 + 1)

Fib(3) = 2 (It is 1 + 1)

Fib(4) = 3 (It is 1 + 2)

Fib(5) = 5 (It is 2 + 3)

Fib(6) = 8 (It is 3 + 5)

Fib(7) = 13 (It is 5 + 8)

Fib(8) = 21 (It is 8 + 13)

and so on ....

**If you don't see that the next two Fibonacci numbers are 34 and 55, ASK!!!** In order to answer this question correctly, you must understand the series.

Write a recursive function called *Fib* that takes one integer parameter *n* and returns *Fib(n)*. For example, *Fib(8)* should return *21*. (HINT: There are two base cases.) (15 points)

You have been given a copy of the code that defines the BinaryTree class. What modifications would be necessary to the code for the BinaryTree class to include a recursive member function SumOfEvenNodes that returns the sum of all nodes in the tree whose integer value is an even number. (NOTE: An integer object *x* is even if the following condition is true: (x % 2 == 0))

Changes to the *public* section:

Changes to the *private* section:

Code for the * function definitions*:

int BinaryTree::InTree(int x){

// pre: none

// post: return true if x is in the tree, false if not

}