Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORD_SIZE 30
/*
program to read a set of words from a file, store them in a binary
search tree and then preform an in-order traversal of the tree
during traversal contents of nodes are displayed - word and count
assumes potential duplicates in original file; only writes one copy
back
*/
typedef struct Treenode
{
char word[WORD_SIZE];
int count;
struct Treenode *left;
struct Treenode *right;
} Treenode;
Treenode* new_node(Treenode*, char*);
void inorder(Treenode*);
void to_file_preorder(Treenode*, FILE*);
void menu();
void check_choice(Treenode* tree, char);
void search(Treenode* tree,char*);
Treenode* del_node(Treenode* tree, char*);
int main()
{
char str[30];
FILE* fptr;
int check =0;
char ch;
Treenode* root =NULL;
if ( (fptr = fopen("test.txt","r")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt");
return(0);
}
while(fscanf(fptr, "%s", str) != EOF)
root = new_node(root, str);
menu();
scanf(" %c", &ch);
while ((ch != 'e') && (ch != 'E'))
{
check_choice(root, ch);
menu();
scanf(" %c", &ch);
}
fclose(fptr);
if ( (fptr = fopen("test.txt","w")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt for writing");
return(0);
}
to_file_preorder(root, fptr);
fclose(fptr);
return(1);
}
Treenode* new_node(Treenode* root, char word[30])
{
if(root == NULL)
{
root = (Treenode *) malloc(sizeof(Treenode));
strcpy(root->word, word);
root->left = NULL;
root->right = NULL;
root->count = 1;
}
else
{
if((strcmp(word,root->word))==0)
{
root->count++;
}
else if((strcmp(word,root->word)) < 0)
{
root->left = new_node(root->left, word);
}
else if((strcmp(word,root->word)) > 0)
{
root->right = new_node(root->right, word);
}
}
return(root);
}
void search(Treenode *root, char *term)
{
int l;
if (root == NULL)
{
printf("Term not found\n");
return;
}
else if ((l = strcmp (root->word, term)) == 0)
{
printf("Term found in tree\n");
return;
}
else if (l > 0)
search(root->left, term);
else
search(root->right, term);
}
void inorder(Treenode* root)
{
if(root != NULL)
{
inorder(root->left);
printf("\n %s %d",root->word, root->count);
inorder(root->right);
}
}
void to_file_preorder(Treenode *root, FILE *fptr)
{
if (root != NULL)
{
fprintf(fptr, "%s ",root->word);
to_file_preorder(root->left, fptr);
to_file_preorder(root->right, fptr);
}
}
void menu()
{
printf("\n\tExit program (e)\n");
printf("\tview tree (v)\n");
printf("\tSearch tree for string (s)\n");
printf("\tAdd new string to tree (a)\n");
printf("\tDelete string from tree(d)\n");
return;
}
void check_choice(Treenode *tree, char choice)
{
char term[WORD_SIZE];
switch(choice)
{
case 'e' : printf("Exiting ...\n");
break;
case 'v' : inorder(tree);
break;
case 's' : printf("Please enter search term\n");
scanf ("%s", term);
search(tree, term);
break;
case 'a' : printf("Please enter term to be added\n");
scanf ("%s", term);
tree = new_node(tree, term);
break;
case 'd': printf("Please enter term to be deleted\n");
scanf("%s", &term);
tree=del_node(tree,term);
break;
}
}
//begin del_node function
Treenode* del_node(Treenode *T, char *term)
{
Treenode *tmp, *tmp1, *prev1, *prev;
int l;
int found = 0; //boolean variable
int direction;
int delete_root = 0;
tmp = prev = T;
//search for node to be deleted
while((tmp!=NULL) && (!found))
{
if((l = strcmp(tmp->word,term))==0)
found = 1;
else if(l>0)
{
prev = tmp;
tmp = tmp->left;
direction = 0;
}
else
{
prev = tmp;
tmp = tmp->right;
direction = 1;
}
}
if(!found)
{
fprintf(stderr, "Value not found in tree\n");
return(T);
}
if(tmp==T)
{
delete_root = 1;
}
//node to be deleted is pointed to by tmp; it's parent by prev;
//case 1: no children
if((tmp->left==NULL) && (tmp->right==NULL))
{
if(delete_root)
{
free(T);
return(NULL);
}
if(direction==1)
prev->right=NULL;
else
prev->left=NULL;
free(tmp);
return(T);
}
//case 2: one child
if((tmp->left!=NULL) && (tmp->right==NULL))
{
if(delete_root)
{
tmp=tmp->left;
free(prev);
return(tmp);
}
if(direction==1)
prev->right=tmp->left;
else
prev->left=tmp->left;
free(tmp);
return(T);
}
if((tmp->left==NULL) && (tmp->right!=NULL))
{
if(delete_root)
{
tmp=tmp->right;
free(prev);
return(tmp);
}
if(direction==1)
prev->right=tmp->right;
else
prev->left=tmp->right;
free(tmp);
return(T);
}
//case 3: two children
if((tmp->left!=NULL) && (tmp->right!=NULL))
{
direction = 0;
prev1=tmp;
tmp1=tmp->right;
//find value to move up the tree
while(tmp1->left!=NULL)
{
direction = 1;
prev1 = tmp1;
tmp1 = tmp1->left;
}
//move it ot place of value being deleted
tmp->count=tmp1->count;
strcpy(tmp->word,tmp1->word);
//remove this value from its original location
if(direction)
prev1->left=NULL;
else
prev1->right=NULL;
free(tmp1);
return(T);
}
}