Files talked about: int-bst.h.: int-bst.c.: Makefile.: test-int-bst.c, : test-he

Question

Files talked about:

int-bst.h.:

int-bst.c.:

Makefile.:

test-int-bst.c, :

test-helper.c

test-helper.h.:

Programming Problems Do the following programming problems. You will end up with at least one code file per problem. Submit your program source (and any other needed files) by sending mail to bmassing cs.trinity.edu with each file as an attachment. Please use a subject line that mentions the course and the assignment (e.g., csci 1120 hw 9" or "LL hw 9"). You can develop your programs on any system that provides the needed functionality, but I will test them on one of the department's Linux machines, so you should probably make sure they work in that environment before turning them in. 1. (20 points) Your mission for this assignment is to complete a partial implementation in C of a binary search tree (a.k.a. sorted binary tree) of ints. (I'm hoping that all of you know about this data structure from CS2 or another course. If not, the Wikipedia article is a reasonable description (but I recommend that you not read the example code until you try to write your own). This partial implementation consists of a number of files: o Function declarations for tree: int-bst.h. o Starter file for function definitions: int-bst.c. o Test program and supporting files: test-int-bst.c, test-helper.c, test-helper.h. o Makefile for compiling (comments in the file tell you how to use it): Makefile. I've made a ZIP file containing all of these files, so it will probably be simplest just to download that and unzip it (command unzip on our machines). If you prefer to download individual files, NOTE that you should use your browser's download" or "save" function to obtain the Makefile rather than copying and pasting text. This is because copy-and-paste will likely replace the tab characters in the file with spaces, with bad consequences (since tabs are semantically significant in makefiles.) Your job is to modify the file int-bst.c so it includes function definitions for all the functions declared in int-bst.h. The test program is self-contained and contains code to call the functions you will write, so you don't need to write any input/output code, aside from implementing two print functions. You compile the test program by typing make test-int-bst and run it by typing test- int-bst. Notice that the function that removes a single element of the tree (int_bst_remove) is optional -- you can provide an actually implement this operation. implementation" that just prints an error message, or for extra credit you can You should not modify any other files, unless you want to add additional tests to test-int-bot.c. Sample output of the test program:

Explanation / Answer

here is your int_bst.c : ----------->>>>>>>>>>>

#include "bst_node.h"

bool int_bst_insert(int_bst_node_t **t_p,int n){
int_bst_node_t *new_t = (int_bst_node_t *)malloc(sizeof(int_bst_node_t));
new_t->data = n;
new_t->left = NULL;
new_t->right = NULL;
if(*t_p == NULL){
  *t_p = new_t;
  return true;
}
int_bst_node_t *temp = *t_p;
while(true){
  if(temp->data > n){
   if(temp->right == NULL){
    temp->right = new_t;
    return true;
   }
   temp = temp->right;
  }else if(temp->data < n){
   if(temp->left == NULL){
    temp->left = new_t;
    return true;
   }
   temp = temp->left;
  }else{
   return false;
  }
}
}

bool int_bst_find(int_bst_node_t * t, int n){
int_bst_node_t *temp = t;
if(temp == NULL){
  return false;
}
while(true){
  if(temp->data > n){
   if(temp->right == NULL){
    return false;
   }
   temp = temp->right;
  }else if(temp->data < n){
   if(temp->left == NULL){
    return false;
   }
   temp = temp->left;
  }else{
   return true;
  }
}
}

void int_bst_remove(int_bst_node_t ** t_p, int n){
int_bst_node_t *temp = *t_p;
int_bst_node_t *prev = NULL;
if(temp == NULL){
  return;
}
int st = 0;
while(true){
  if(temp->data > n){
   if(temp->right == NULL){
    return;
   }
   prev = temp;
   st = 1;
   temp = temp->right;
  }else if(temp->data < n){
   if(temp->left == NULL){
    return;
   }
   prev = temp;
   st = 2;
   temp = temp->left;
  }else{
   if(prev == NULL){
    if(temp->right == NULL && temp->left == NULL){
     free(temp);
     *t_p = NULL;
     return;
    }else if(temp->right == NULL){
     *t_p = temp->left;
     free(temp);
     return;
    }else if(temp->left == NULL){
     *t_p = temp->right;
     free(temp);
     return;
    }else{
     int_bst_node_t *tt = temp->right;
     while(tt->left != NULL){
      tt->left;
     }
     tt->left = temp->left;
     *t_p = temp->right;
     free(temp);
     return;
    }
   }else{
    if(temp->right == NULL && temp->left == NULL){
     free(temp);
     if(st == 1)
     prev->right = NULL;
     else
     prev->left = NULL;
     return;
    }else if(temp->right == NULL){
     if(st == 1)
     prev->right = temp->left;
     else
     prev->left = temp->left;
     free(temp);
     return;
    }else if(temp->left == NULL){
     if(st == 1)
     prev->right = temp->right;
     else
     prev->left = temp->right;
     free(temp);
     return;
    }else{
     int_bst_node_t *tt = temp->right;
     while(tt->left != NULL){
      tt->left;
     }
     tt->left = temp->left;
     if(st == 1)
     prev->right = temp->right;
     else
     prev->left = temp->right;
     free(temp);
     return;
    }
   }
  }
}
}

void int_bst_remove_all(int_bst_node_t ** t_p){
int_bst_node_t *temp = *t_p;
while(temp != NULL){
  int_bst_remove(&temp,temp->data);
}
*t_p = NULL;
}

void int_bst_print_elements(int_bst_node_t *t, FILE * f, char * fmt){
if(t == NULL){
  return;
}
fprintf(f,fmt,t->data);
int_bst_print_elements(t->left,f,fmt);
int_bst_print_elements(t->right,f,fmt);
}

void int_bst_print_as_tree(int_bst_node_t * t, FILE * f){
//give the sample output we can change here the format
int_bst_print_elements(t,f,"%d ");
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.