Reference no: EM131667067

Question: 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 traversal 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 numbered 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 outputs the tree to your favorite device.