Question: Please complete the following functions in C language: int FindMinPath(struct AVLTree *tree, TYPE *path) = 10 points void preorder(struct AVLnode *node, TYPE *min_cost, TYPE *path,
Please complete the following functions in C language:
int FindMinPath(struct AVLTree *tree, TYPE *path) = 10 points
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) = 20 points
void printBreadthFirstTree(struct AVLTree *tree) = 20 points
--------------------------------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;
}
----------------------------------------------------------------------------------------------------
------------------------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);
}
-----------------------------------------------------------------------------------------------------------
Initializes an empty AVL tree.
Reads values from an input file and adds them to the AVL tree.
Prints on the terminal all values of the AVL tree in the breadth-first fashion.
Finds the minimum-cost path in the AVL tree (see details below).
Prints on the terminal the execution time for finding the min-cost path.
Prints on the terminal values of nodes that lie on the minimum-cost path in the AVL tree. The order of nodes in the print-out must strictly follow their order in the min-cost path from the root to the leaf.
Prints on the terminal a cost of the min-cost path of the AVL tree.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help