CISC220, 06J Homework 02

Due Monday 08/06

NOTE! See note at end of file about problem 7

References

Malik, p. 631ff, about binary tree terminology
Malik, p. 639ff, about binary tree traversals

Note: In case you are not familiar with it, the abbreviation "ff" means "and following pages".

So p. 631ff means "start reading on page 631, and don't stop until you see that the material is no longer relevant to the topic you are looking up.

Exercises:

(15 pts) Provide a preorder, inorder and postorder traversal of the following binary tree:
(10 pts) Provide a preorder, inorder and postorder traversal of the following binary tree:
(10 pts) Provide a preorder, inorder and postorder traversal of the following binary tree:
(10 pts) What is the maximum and minimum number of elements in a heap that has height=3?

Hints:
- Use Malik's definition of "height" for a binary tree, namely "the number of nodes on the longest path from the root to a leaf" (p. 637).
- A min-heap is a binary tree with the min-heap property, and the "heap shape", i.e. it is a so-called "complete" tree.
- As defined in lecture--note that "complete" is not the same thing as "full".
(10 pts) If a heap has exactly 500 elements, what is the height of that heap?
Suppose Foo_C and Bar_C are both C++ classes. Further, suppose Foo_C contains a private data member of type Bar_C. Answer the following questions:
1. (5 pts) Is the relationship between Foo_C and Bar_C composition or inheritance?
2. (5 pts) When an instance of Foo_C is created, what is the order in which the two classes constructors are called?
3. (5 pts) When a local variable of type Foo_C goes out of scope, what is the order in which the two classes destructors are called?
NOTE! See note at end of file about problem 7

(Continuing from the previous question). Now there is a new class Fum_C> that is declared with the following code:
```
class Fum_C : public Foo_C
{
 ...
}
```
Answer the following questions about the three classes Foo_C, Bar_C and Fum_C.
1. (5 pts) Is the relationship between Foo_C and Fum_C composition or inheritance?
2. (5 pts) When an instance of Fum_C is created, what is the order in which the three classes constructors are called?
3. (5 pts) When a local variable of type Fum_C goes out of scope, what is the order in which the three classes destructors are called?
4. (5 pts) The relationships among Foo_C, Bar_C and Fum_C correspond to the relationships that might exist among three "real-world" classes, representing a GPA (grade point average), a Person, and a Student, but not necessarily in that order.
  
  Give the correct mapping---that is:
  1. Which of these (GPA,Person,Student) would be Foo_C
  2. Which would be Bar_C
  3. Which would be Fum_C?
5. (10 pts) Give another practical example of the relationship between Foo_C, Bar_C and Fum_C.

Total: 100 pts. Due beginning of class on Monday. 10 pts off if you are more than 10 minutes late for class (this is to encourage you not to skip class to finish your homework).

Note about problem 7:

Anshu sent the following email:

Hello Professor,


I was doing the homework ahead of time because I will be 
out of town this weekend and I ran into a problem with 
#7 which I don't think you intended.  You ask us to draw 
an analogy between Foo_C, Fum_C, Bar_C and a Person, a 
Student, and a GPA.


The problem is, with the intended relationships, 
Foo_C is the person, Fum_C is the Student, and Bar_C is the GPA, so...

Fum_C is a Foo_C. -> Student is a Person
Foo_C has a Bar_C. -> Person has a GPA

So Fum_C should have a private data member Bar_C, 
not Foo_C, so problem #6 might have to change as well.

This change will also affect the order of the 
constructors/destructors in problem #7 if I'm not mistaken.

Here is my reply:

You are exactly right.

So, please change the problem as follows: instead of GPA, think of some example of an attribute that WOULD fit the stated relationships among Foo_C, Fum_C and Bar_C, and substitute that in place of GPA.