You are given a skeleton C code in the following files:

-------------------avl.h---------------------------

#ifndef __AVL_H

#define __AVL_H

# ifndef TYPE

# define TYPE int

# endif

#ifndef EQ

#define EQ(a, b) (a == b)

#endif

#ifndef LT

#define LT(a, b) (a < b)

#endif

struct AVLnode {

TYPE val;

struct AVLnode *left;

struct AVLnode *right;

int height;

};

struct AVLTree {

struct AVLnode *root;

int cnt;

};

/* the public interface */

/* Alocate and initialize AVL tree structure. */

struct AVLTree * newAVLTree();

/* Initialize AVL tree structure. */

void initAVLTree(struct AVLTree *tree);

/* Deallocate nodes in AVL tree and deallocate the AVL tree structure. */

void deleteAVLTree(struct AVLTree *tree);

/* Deallocate nodes in AVL tree. */

void clearAVLTree(struct AVLTree *tree);

void addAVLTree(struct AVLTree *tree, TYPE val);

void removeAVLTree(struct AVLTree * tree, TYPE val);

void removeAllAVLTree(struct AVLTree * tree, TYPE val);

int containsAVLTree(struct AVLTree *tree, TYPE val);

/* the internal interface */

void _freeAVL(struct AVLnode *node);

int h(struct AVLnode *current);

void setHeight (struct AVLnode * current);

int bf(struct AVLnode * current);

struct AVLnode * rotateLeft(struct AVLnode * current);

struct AVLnode * rotateRight(struct AVLnode * current);

struct AVLnode * _balance(struct AVLnode * current);

TYPE _leftMost(struct AVLnode *cur);

struct AVLnode * _removeLeftmost(struct AVLnode * cur);

struct AVLnode * _removeNode(struct AVLnode * cur, TYPE val);

struct AVLnode * _removeAllNodes(struct AVLTree * tree, struct AVLnode *

cur, TYPE val);

struct AVLnode * AVLnodeAdd(structAVLnode * current, TYPE newValue);

#endif

----------------------------------------------------------------------------------------------------------------

--------------------------------------avl.c----------------------------------------------

#include

#include

#include

#include "avl.h"

/* Alocate and initialize AVL tree structure. */

struct AVLTree * newAVLTree()

{

struct AVLTree *tree = (struct AVLTree *)malloc(sizeof(struct

AVLTree));

assert(tree != 0);

initAVLTree(tree);

return tree;

}

/* Initialize AVL tree structure. */

void initAVLTree(struct AVLTree *tree)

{

tree->cnt = 0;

tree->root = 0;

}

void _freeAVL(struct AVLnode *node)

{

if (node != 0) {

_freeAVL(node->left);

_freeAVL(node->right);

free(node);

}

}

/* Deallocate nodes in AVL tree. */

void clearAVLTree(struct AVLTree *tree)

{

_freeAVL(tree->root);

tree->root = 0;

tree->cnt = 0;

}

/* Deallocate nodes in AVL tree and deallocate the AVL tree structure. */

void deleteAVLTree(struct AVLTree *tree)

{

clearAVLTree(tree);

free(tree);

}

/* return height of current node */

int h(struct AVLnode *current)

{

if (current == 0)

return -1;

return current->height;

}

/* set height for current node */

void setHeight (struct AVLnode * current)

{

int lch = h(current->left);

int rch = h(current->right);

if (lch < rch)

current->height = 1 + rch;

else

current->height = 1 + lch;

}

/* return balance factor value */

int bf(struct AVLnode * current)

{

return h(current->right) - h(current->left);

}

/* left-rotate subtree of current node */

struct AVLnode * rotateLeft(struct AVLnode * current)

{

struct AVLnode * newtop = current->right;

current->right = newtop->left;

newtop->left = current;

setHeight(current);

setHeight(newtop);

return newtop;

}

/* right-rotate subtree of current node */

struct AVLnode * rotateRight(struct AVLnode * current)

{

struct AVLnode * newtop = current->left;

current->left = newtop->right;

newtop->right = current;

setHeight(current);

setHeight(newtop);

return newtop;

}

/* balance subtree of current node */

struct AVLnode * _balance(struct AVLnode * current)

{

int cbf = bf(current);

if (cbf < -1){

if (bf(current->left) > 0) /* double rotation */

current->left = rotateLeft(current->left);

return rotateRight(current); /* single rotation */

} else if(cbf > 1){

if(bf(current->right) < 0)

current->right = rotateRight(current->right);

return rotateLeft(current);

}

setHeight(current);

return current;

}

/* add newValue to subtree of current node */

struct AVLnode * AVLnodeAdd(structAVLnode * current, TYPE newValue)

{

/* FIX ME */

}

/* add val to AVL tree */

void addAVLTree(struct AVLTree *tree, TYPE val)

{

tree->root = AVLnodeAdd(tree->root, val);

tree->cnt++;

}

/* determine if val is contained in the AVL tree */

int containsAVLTree(struct AVLTree *tree, TYPE val)

{

struct AVLnode* cur = tree->root;

while(cur != 0){

if (EQ(cur->val, val))

return 1;

else if (LT(val, cur->val))

cur = cur->left;

else

cur = cur->right;

}

return 0;

}

/* find leftmost value from subtree of current node */

TYPE _leftMost(struct AVLnode *cur)

{

while(cur->left != 0)

cur = cur->left;

return cur->val;

}

/* remove leftmost node from subtree of current node */

struct AVLnode * _removeLeftmost(struct AVLnode * cur)

{

struct AVLnode * temp;

if(cur->left != 0){

cur->left = _removeLeftmost(cur->left);

return _balance(cur);

}

temp = cur->right;

free(cur);

return temp;

}

/* remove val from subtree of cur node */

struct AVLnode * _removeNode(struct AVLnode * cur, TYPE val)

{

struct AVLnode * temp;

if(EQ(val, cur->val)){

if(cur->right != 0){

cur->val = _leftMost(cur->right);

cur->right = _removeLeftmost(cur->right);

return _balance(cur);

} else {

temp = cur->left;

free(cur);

return temp;

}

} else if (LT(val, cur->val))

cur->left = _removeNode(cur->left, val);

else cur->right = _removeNode(cur->right, val);

return _balance(cur);

}

/* remove val from AVL tree */

void removeAVLTree(struct AVLTree * tree, TYPE val)

{

if(containsAVLTree(tree, val)){

tree->root = _removeNode(tree->root, val);

tree->cnt--;

}

}

/* remove val from AVL tree */

void removeAllAVLTree(struct AVLTree * tree, TYPE val)

{

if(containsAVLTree(tree, val))

tree->root = _removeAllNodes(tree, tree->root, val);

}

struct AVLnode * _removeAllNodes(struct AVLTree * tree, struct AVLnode *

cur, TYPE val){

struct AVLnode * temp = NULL;

while(EQ(val, cur->val)){

if(cur->right != 0){

cur->val = _leftMost(cur->right);

cur->right = _removeLeftmost(cur->right);

tree->cnt--;

} else {

temp = cur->left;

free(cur);

tree->cnt--;

cur = temp;

}

}

if (cur){

if (LT(val, cur->val))

cur->left = _removeAllNodes(tree,cur->left, val);

else

cur->right = _removeAllNodes(tree,cur->right, val);

}

return _balance(cur);

}

------------------------------------------------------------------------------------------------

---------------main.c-----------------------------------------------------------

#include

#include

#include

#include

#include "avl.h"

void preorder(struct AVLnode *node, TYPE *min_cost, TYPE *path, int *m,

TYPE *candidate_path, int *n, TYPE sumDiff, TYPE parent_value);

TYPE absoluteDiff(TYPE a, TYPE b);

int FindMinPath(struct AVLTree *tree, TYPE *path);

void printBreadthFirstTree(struct AVLTree *tree);

/* --------------------

Finds the minimum-cost path in an AVL tree

Input arguments:

tree = pointer to the tree,

path = pointer to array that stores values of nodes along the min-

cost path,

Output: return the min-cost path length

pre: assume that

path is already allocated sufficient memory space

tree exists and is not NULL

*/

int FindMinPath(struct AVLTree *tree, TYPE *path)

{

int path_len = 0; /* the initial length of the min-cost path */

struct AVLnode * current = tree->root;

TYPE min_cost = (TYPE) 10^6 * tree->cnt; /* initial high value for

minimum */

int c_path_len = 0; /* length of a candidate path */

TYPE candidate_path[100]; /* candidate path is a static array */

path[path_len] = tree->root->val; /* min-cost path must contain

the root */

path_len++;

/* Write this part of the function */

if (tree->cnt > 1){

/* Traverse the tree and find the min-cost path */

/* FIX ME */

}

return path_len;

}

/* ----------

Finds absolute difference between two input numbers

*/

TYPE absoluteDiff(TYPE a, TYPE b){

if (a<0)

return (TYPE) 0;

else

return (TYPE) abs(a-b);

}

/*-------------------------

Recursively traverses the AVL tree and finds its min cost path

Input argument:

node = pointer to the current node visited by recursion,

min_cost = the latest minimum cost,

path = array of values of nodes along the latest best path,

path_len = number of elements in path array,

candidate_path = currently considered path array

c_path_len = number of elements in the candidate path array

pre: assume that all input arguments are well initialized and have enough

memory space

post:

path points to the array of values in the min-cost path of the AVL

tree

path_len is the number of elements (i.e., nodes) in the min-cost path

of the AVL tree

*/

void preorder(struct AVLnode *node, TYPE *min_cost, TYPE *path, int

*path_len,

TYPE *candidate_path, int *c_path_len, TYPE sumDiff, TYPE

parent_value)

{

int i;

/* put the current node in a candidate path */

candidate_path[*c_path_len] = node->val;

(*c_path_len)++;

/* cumulative cost of the candidate path */

sumDiff = sumDiff + absoluteDiff(parent_value, node->val);

/* Write the recursion case(s) and the stopping-recursion case(s) */

/* FIX ME */

}

/* -----------------------

Printing the contents of an AVL tree in breadth-first fashion

param: pointer to a tree

pre: assume that tree was initialized well before calling this function

*/

void printBreadthFirstTree(struct AVLTree *tree){

struct AVLnode **queue; /* print using a queue, where queue is

implemented as a static array */

struct AVLnode *current = tree->root;

int start = 0; /* start index of queue indicating the first element to

be processed */

int end = 0; /* end index of queue indicating the latest element added

to the queue */

/* allocate memory to queque */

queue = (struct AVLnode **) malloc(100*sizeof(struct AVLnode));

/* FIX ME */

}

/* -----------------------

The main function

param: argv = pointer to the name (and path) of a file that the program

reads for adding elements to the AVL tree

*/

int main(int argc, char** argv) {

FILE *file;

int len, i;

TYPE num; /* value to add to the tree from a file */

struct timeval stop, start; /* variables for measuring execution

time */

int pathArray[50]; /* static array with values along the min-cost

path of the AVL tree */

struct AVLTree *tree;

tree = newAVLTree(); /*initialize and return an empty tree */

file = fopen(argv[1], "r"); /* filename is passed in argv[1] */

assert(file != 0);

/* Read input file and add numbers to the AVL tree */

while((fscanf(file, "%i", &num)) != EOF){

addAVLTree(tree, num);

}

/* Close the file */

fclose(file);

printf(" Printing the tree breadth-first : ");

printBreadthFirstTree(tree);

gettimeofday(&start, NULL);

/* Find the minimum-cost path in the AVL tree*/

len = FindMinPath(tree, pathArray);

gettimeofday(&stop, NULL);

/* Print out all numbers on the minimum-cost path */

printf(" The minimum-cost path is: ");

for(i = 0; i < len; i++)

printf("%d ", pathArray[i]);

printf(" ");

printf(" Your execution time to find the mincost path is %f

microseconds ", (double) (stop.tv_usec - start.tv_usec));

/* Free memory allocated to the tree */

deleteAVLTree(tree);

return 0;

}

and the file with values that should be read and added to the AVL Tree for testing your code:

------------------------input.txt-------------------------------------

50 61 42 21 6 11 23 31 40 41 12 22 16 13 25 34 5 27 30 20 2 7 8 9 4 10 0

43 73 75 74