Late assignments will be penalized 10% per day, and will not be accepted after .
Name, Student Number, Assignment Number, Course Number (T26)
Assignments which are not in an envelope will not be marked
Deposit your envelope in .
Your program must conform to the programming standards. These are described in a separate sheet.
In this assignment, you are given a complete implementation of the abstract type `binary tree' as well as some application code for exercising your answer to each question. Your job, in each question, is to write one application procedure that is missing.
Your procedures must be completely independent of the way binary trees are implemented - they must do all their tree manipulations using the abstract operations defined in the tree specification (the marker may use a different implementation of binary trees when she marks your program). You must use the given parts of the program without changing them.
Note that the main program writes out information about:
The file you are given (Partial7.c) contains application code for
both questions. In order to select the application code relevant to
the question you are working on, you must remember to define the macro
QUESTION appropriately at the top of the file. For
question 1 it should be:
#define QUESTION 1whereas for question 2 it should be:
#define QUESTION 2Also make sure you have correctly redefined
WhoAmIto contain information by which you can be identified.
The program you are given does everything except step (2). You must write
void bst_to_array (binary_tree b,element array,int *n);that copies the values from binary search tree
arrayin increasing order. The procedure also sets
*n, the number of values in the array. You may assume that
*nhas been initialized to zero by the user.
rotate_tree(t)which `rotates' the subtree
taccording to the general algorithm described below. This procedure must be independent of the exact way trees are implemented; it must do all its tree manipulations using the abstract operations defined in the tree specification.
rotate_tree(t)is the rotator node. The pivot node is the deepest node at which there is an imbalance. The rotator node is the root of the pivot's taller subtree.
There may be more nodes above the pivot's parent. Step 3 prunes the rotator's `inside' subtree, i.e. the one on the pivot's side. For example, if the rotator is the pivot's right subtree, then the inside subtree is the rotator's left subtree (towards the pivot rather than away from it).
Step 4: Join the pruned inside subtree to the pivot (in the place where the rotator had been).
Step 5: Join the pivot to the rotator (in the place where inside had been).
Step 6: Join the rotator to the pivot's (original) parent (in the place where the pivot had been).
Following these steps, the result of the rotation is this: the rotator has rotated up, the pivot has rotated down on the other side, and the inside subtree has jumped across to join the pivot:
After steps 1-3, the tree is the same but the parts that will be re-arranged have been pruned from the main tree and from one another:
Step 4: Join the pruned inside subtree to the pivot:
Step 5: Join the pivot to the rotator (in the place where inside had been):
Step 6: Join the rotator to the pivot's (original) parent:
The result of the rotation in this example is: `1' rotates up, `5' rotates down on the other side, and `2' jumps across to join `5'.
[left subtree root value right subtree
[[[[* -1 *] 0 *] 1 [[* 2 *] 5 [* 6 *]]] 9 [* 10 [* 11 *]]]
After each step, the tree should be balanced - a tree is balanced
if it is empty or if the heights of its left and right subtrees are
within 1. The height of a tree is the number of nodes on its longest
branch - in order to do the `balancing', the program calls your
rotate_tree procedure. If the resulting tree is not
balanced, the program will let you know, and that means there is a bug
rotate_tree procedure. The printed version of the
tree may (or may not) give you a clue.