Tree Implementations - Data Structures and Abstractions with Java - page 620

P ROGRAMMING T IPS

•

No cast is needed when you pass an instance of BinaryTree to a method whose parameter has the type
BinaryTreeInterface . The converse, however, requires a cast.

•

An iterator object that has not traversed the entire binary tree can be adversely affected by changes to the tree.

E XERCISES

1.

Implement getHeight in the class BinaryNode , using the approach that Segment 24.11 uses for
getNumberOfNodes . That is, getHeight should not call a private method.

2.

Implement getNumberOfNodes in the class BinaryNode , using the approach that Segment 24.11 uses for
getHeight . That is, getNumberOfNodes should not call a private method.

3.

In Segment 24.12, Question 4 asked you to implement a recursive preorder traversal of a binary tree. Implement a
recursive method postorderTraverse that displays the data in a binary tree in postorder.

4.

Trace the iterative method inorderTraverse given in Segment 24.14 with the binary tree in Figure 24-10. Show
the contents of the stack after each push and pop .

FIGURE 24-10

A binary tree for Exercises 4, 5, 6, and 17

a

c

b

d e

g

f

h

5.

Show the contents of the stack after each push and pop during a preorder traversal of the binary tree in Figure 24-10.
Repeat for a postorder traversal.

6.

Show the contents of the queue after each enqueue and dequeue during a level-order traversal of the binary tree in
Figure 24-10.

7.

Suppose we want to create a method for the class BinaryTree that counts the number of times an object occurs in
the tree. The header of the method could be as follows:
public int count(T anObject)
a. Write this method using a private recursive method of the same name.
b. Write the method using one of the iterators of the binary tree.
c. Compare the efficiencies of the previous two versions of the method.

8.

Trace the method evaluate given in Segment 24.18 for the expression tree in Figure 23-14d of the previous
chapter. What value is returned? Assume that a is 2, b is 4, c is 5, d is 6, and e is 4.

9.

Write a recursive definition for the number of possible binary trees that have distinct shapes and contain n nodes.