Trees - Data Structures and Problem Solving Using Java - page 684

c. The number of nodes with two children that contain the same value

d. The length of the longest strictly increasing sequence of numbers

that follow a path down the tree. The path does not have to
include the root.

e. The length of the longest strictly increasing sequence of numbers

that follow a path down the tree. The path must include the root.

Implement some of the recursive routines with tests that ensure that a
recursive call is not made on a null subtree. Compare the running
time with identical routines that defer the test until the first line of the
recursive routine.

18.11

Rewrite the iterator class to throw an exception when first is applied
to an empty tree. Why might this be a bad idea?

18.12

PROGRAMMING PROJECTS
18.13

A binary tree can be generated automatically for desktop publishing by a
program. You can write this program by assigning an x - y coordinate to
each tree node, drawing a circle around each coordinate, and connecting
each nonroot node to its parent. Assume that you have a binary tree stored
in memory and that each node has two extra data members for storing the
coordinates. Assume that (0, 0) is the top-left corner. Do the following.
a. The x -coordinate can be computed by assigning the inorder tra-

versal number. Write a routine to do so for each node in the tree.

b. The y -coordinate can be computed by using the negative of the

depth of the node. Write a routine to do so for each node in the tree.

c. In terms of some imaginary unit, what will be the dimensions of

the picture? Also determine how you can adjust the units so that
the tree is always roughly two-thirds as high as it is wide.

d. Prove that when this system is used, no lines cross and that for

any node X , all elements in X 's left subtree appear to the left of X ,
and all elements in X 's right subtree appear to the right of X .

e. Determine whether both coordinates can be computed in one

recursive method.

f. Write a general-purpose tree-drawing program to convert a tree

into the following graph-assembler instructions (circles are num-
bered in the order in which they are drawn):

circle( x, y ); // Draw circle with center (x, y)
drawLine( i, j ); // Connect circle i to circle j

g. Write a program that reads graph-assembler instructions and out-

puts the tree to your favorite device.