IUP Computer Science
CO 310 Spring 1993

Assignment #6
(Due   3 May 1993)


1.  Assume that TNODE and TPTR have been declared as types - tree node and pointer to a tree node, respectively; also, assume that the binary trees mentioned below are represented using these nodes.  TNODE has LEFT, DATA, and RIGHT fields.  You may assume that the binary trees have no more than 20 levels. Write a Pascal procedure to do each of the following tasks.  Show all statements for each procedure, including the procedure statement and any local variable declarations.  It is recommended that you type or word process your answers so that I can easily read them.

a. Write a procedure that will make a duplicate of a binary tree. The duplicate tree must have the same structure as the original tree and must contain the same DATA field values in corresponding nodes; however, the duplicate must be completely separate from the original. Let T point to the root of the original tree and make D point to the root of the duplicate tree.  Neither T nor D may be global.

b. Write a procedure to count the number of leaves in a binary tree. Assume that T points to the root of the tree; T must be a parameter.  Return the number of leaves as a parameter of the procedure.  

c. Write a procedure to determine the width of a binary tree. The width is the maximum number of nodes on any one level.  Assume that T points to the root of the tree and is a parameter.   Return the width as a parameter of the procedure.

2.  Write down 10 names, like JEAN, TERRY, LUCY, etc.  Using the names in the order you have written them, build a binary search tree by repeated inserting the names into the tree.  Draw a picture of the resulting search tree.  Don't make any special attempt to choose "good" names; just take the first 10 names you think of.  After the tree is complete, calculate the average number of comparisons needed to find a name that is in the tree.   For example, the number of comparisons to find the root is one; to find the children of the root, two comparisons are needed.   Show the name list, as well as the tree.

3.  Construct an AVL tree by inserting the names of the 12 months, in order, i.e., JAN, FEB, MAR, etc. into a binary search tree.  Just use 3-letter names.  Draw a picture of the tree EACH TIME A ROTATION IS DONE (before and after); and draw the final AVL tree holding all months.


    Please put the drawings for number 2 and 3 on paper that is the same size as that used in number 1.  8 1/2 x 11 paper is recommended.