Hello, I am currently working on a binary search tree that acts as a phone book. I am nearly completed with it and all functions seem to work properly except in two cases:
An error message will not print to the screen when trying to delete or edit for a node that does not exist.
And if a node has a left and right branch, it can't be deleted.
I've been trying to fix these problems, and I was hoping that you fine folk could assist me. If you feel uncomfortable with direct answers, just giving a nudge in the right direction would be great.
Here is my code.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*Create phone book entry structure.*/
typedef struct pbentry {
char lastname[16];
char firstname[11];
char phone[11];
char email[26]; }
Entry;
/*Create tree node structure.*/
struct tree_node {
Entry data;
struct tree_node *left;
struct tree_node *right; };
/*Necessary functions.*/
struct tree_node * insert(struct tree_node *p, Entry e);
struct tree_node * create_node (struct tree_node *q, struct tree_node *r, Entry e);
struct tree_node * delete_node (struct tree_node *p, char l[], char f[]);
struct tree_node * findmin(struct tree_node *p);
struct tree_node * edit_node (struct tree_node *p, char l[], char f[]);
void search_node(struct tree_node *p, char l[], char f[]);
void print_tree(struct tree_node *p);
int main(void) {
int option = 0; /*Variable for option selection.*/
Entry e; /*Basic phone book entry*/
struct tree_node *p = NULL; /*Basic tree node*/
char ln[16]; /*Used for deletions, editing, and searching*/
char fn[11]; /*Used for deletions, editing, and searching*/
/*Return to menu after each instruction until the user quits.*/
while (option != 6) { /*Show user the option menu.*/
printf("MENU\n");
printf("1. Add\n");
printf("2. Delete\n");
printf("3. Edit\n");
printf("4. Search\n");
printf("5. List\n");
printf("6. Quit\n");
/*Get option from the user.*/
printf("\nPlease select an option: ");
scanf("%d", &option);
/*If option is 1 (Add):*/
if (option == 1) {
/*Take in subject data from the user.*/
printf("Please enter the last name: ");
scanf("%s", &e.lastname);
printf("Please enter the first name: ");
scanf("%s", &e.firstname);
printf("Please enter the phone number: ");
scanf("%s", &e.phone);
printf("Please enter the e-mail address: ");
scanf("%s", &e.email);
/*Create a new node.*/
p = insert(p, e);
/*Confirm node creation.*/
printf("Record added successfully.\n\n");
}
/*If option is 2 (Delete):*/
else if (option == 2) {
/*Take in subject data from the user.*/
printf("Please enter the last name: ");
scanf("%s", &ln);
printf("Please enter the first name: ");
scanf("%s", &fn);
/*Delete a node.*/
p = delete_node(p, ln, fn);
}
/*If option is 3 (Edit):*/
else if (option == 3) {
/*Take in subject data from the user.*/
printf("Please enter the last name: ");
scanf("%s", &ln);
printf("Please enter the first name: ");
scanf("%s", &fn);
/*Edit a node.*/
p = edit_node(p, ln, fn);
}
/*If option is 4 (Search):*/
else if (option == 4) {
/*Take in subject data from the user.*/
printf("Please enter the last name: ");
scanf("%s", &ln);
printf("Please enter the first name: ");
scanf("%s", &fn);
/*Search for a node.*/
search_node(p, ln, fn);
}
/*If option is 5 (List):*/
else if (option == 5) {
print_tree(p);
}
/*If option is 6 (Quit):*/
else if (option == 6) {
/*End the program.*/
break;
}
/*If the user does not select an existing option.*/
else {
/*Print error message.*/
printf("That option does not exist. Please try again.\n\n");
}
}
return 0; }
/*Adds a node to the tree.*/
struct tree_node * insert(struct tree_node *p, Entry e)
{
/*If there is no root:*/
if (p == NULL) {
/*Create a root.*/
p = create_node(NULL, NULL, e);
}
/*If there is a root, and the entry belongs before the root:*/
else if (strcmp(e.lastname, p->data.lastname) < 0) {
/*Add before root.*/
p->left = insert(p->left, e);
}
/*If there is a root, and the entry belongs after the root:*/
else if (strcmp(e.lastname, p->data.lastname) > 0) {
/*Add after root.*/
p->right = insert(p->right, e);
}
/*If there is a root, and the lastnames are identical: */
else {
/*If entry belongs before root: */
if (strcmp(e.firstname, p->data.firstname) < 0) {
/*Add before root.*/
p->left = insert(p->left, e);
}
/*If entry belongs after root: */
else if (strcmp(e.firstname, p->data.firstname) > 0) {
/*Add after root.*/
p->right = insert(p->right, e);
}
/*If entries are the same: */
else {
/*Do nothing.*/
return p;
}
}
/*Return revised tree.*/
return p;
}
/*Creates a new node.*/
struct tree_node * create_node (struct tree_node *q, struct tree_node *r, Entry e) {
struct tree_node* newnode;
newnode = (struct tree_node*)(malloc(sizeof(struct tree_node)));
newnode->data = e;
newnode->left = q;
newnode->right = r;
return newnode; }
/*Deletes a node from the tree.*/
struct tree_node * delete_node (struct tree_node *p, char l[], char f[]) {
if (p == NULL) { return NULL; }
/*If entry is before root:*/
if (strcmp(l, p->data.lastname) < 0 || strcmp(f, p->data.firstname) != 0)
{
/*Delete from before root.*/
p->left = delete_node(p->left, l, f);
}
/*If entry is after root:*/
else if (strcmp(l, p->data.lastname) > 0 || strcmp(f, p->data.firstname) != 0) {
/*Delete from after root.*/
p->right = delete_node(p->right, l, f);
}
/*If entry is located and has a left and right branch:*/
else if (p->left != NULL && p->right != NULL) {
/*Find which branch moves up in the tree.*/
p->data = findmin(p->right)->data;
p->right = delete_node(p->right, l, f);
/*Confirm node deletion.*/
printf("Record deleted successfully.\n\n");
}
/*If entry is located and has a left branch:*/
else if (p->left != NULL) {
/*Move left branch up.*/
p = p->left;
/*Confirm node deletion.*/
printf("Record deleted successfully.\n\n");
}
/*If entry is located and has a right branch:*/
else if (p->right != NULL) {
/*Move right branch up.*/
p = p->right;
/*Confirm node deletion.*/
printf("Record deleted successfully.\n\n");
}
/*If entry is not found:*/
else {
/*Error.*/
printf("Record could not be found.\n\n");
}
/*Return revised tree.*/
return p; }
/*Finds the leftmost node in the right branch.*/
struct tree_node * findmin(struct tree_node *p) {
/*If left node is not empty.*/
if (p->left != NULL) {
/*Go to the left node.*/
findmin(p->left); }
/*Return leftmost node.*/
return p; }
/*Edits a node's data.*/
struct tree_node * edit_node (struct tree_node *p, char l[], char f[]) {
char num[11];
/*Used to determine course of action.*/
char e[26];
/*Used to determine course of action.*/
/*If entry is before root:*/
if (p == NULL) { return NULL; }
if (strcmp(l, p->data.lastname) < 0) {
/*Check before root.*/
edit_node(p->left, l, f); }
/*If entry is after root:*/
else if (strcmp(l, p->data.lastname) > 0) {
/*Check after root.*/
edit_node(p->right, l, f);
}
/*If last name is found and first names are different:*/
else if (strcmp(l, p->data.lastname) == 0 && strcmp(f, p->data.firstname) != 0) {
/*If entry is before root.*/
if (strcmp(f, p->data.firstname) < 0) {
/*Check before root.*/
edit_node(p->left, l, f);
}
/*If entry is after root.*/
if (strcmp(f, p->data.firstname) > 0) {
/*Check after root.*/
edit_node(p->right, l, f);
}
}
/*If entry is located:*/
else if (strcmp(l, p->data.lastname) == 0 && strcmp(f, p->data.firstname) == 0) {
/*Ask for new phone number and retreive.*/
printf("New phone number (Enter s to skip): ");
scanf("%s", &num);
/*If skipped:*/
if (strcmp(num, "s") == 0) {
/*Ask for new email address and retreive.*/
printf("New email address (Enter s to skip): ");
scanf("%s", &e);
/*If skipped:*/
if (strcmp(e, "s") == 0) {
/*Confirm node edit.*/
printf("Record edited successfully.\n\n");
/*Return revised tree.*/
return p;
}
/*If email address is to be changed:*/
else {
/*Change email*/
strcpy(p->data.email, e);
/*Confirm node edit.*/
printf("Record edited successfully.\n\n");
}
}
/*If phone number is to be changed:*/
else {
/*Change phone number.*/
strcpy(p->data.phone, num);
/*Ask for new email address and retreive.*/
printf("New email address (Enter s to skip): ");
scanf("%s", &e);
/*If skipped:*/
if (strcmp(e, "s") == 0) {
/*Confirm node edit.*/
printf("Record edited successfully.\n\n");
/*Return revised tree.*/
return p;
}
/*If email address is to be changed:*/
else {
/*Change email.*/
strcpy(p->data.email, e);
/*Confirm node edit.*/
printf("Record edited successfully.\n\n");
}
}
}
/*If entry is not found:*/
else {
/*Error.*/
printf("Record could not be found.\n\n");
}
/*Return revised tree.*/
return p; }
/*Searches for a node and retrieves data.*/
void search_node(struct tree_node *p, char l[], char f[]) {
/*If entry is before root:*/
if (p == NULL) { printf("Member not found.\n"); return; }
if (strcmp(l, p->data.lastname) < 0) {
/*Check before root.*/
search_node(p->left, l, f);
}
/*If entry is after root:*/
else if (strcmp(l, p->data.lastname) > 0) {
/*Check after root.*/
search_node(p->right, l, f);
}
/*If last name is found and first names are different:*/
else if (strcmp(l, p->data.lastname) == 0 && strcmp(f, p->data.firstname) != 0) {
/*If entry is before root.*/
if (strcmp(f, p->data.firstname) < 0) {
/*Check before root.*/
search_node(p->left, l, f);
}
/*If entry is after root.*/
if (strcmp(f, p->data.firstname) > 0) {
/*Check after root.*/
search_node(p->right, l, f);
}
}
/*If entry is located:*/
else if (strcmp(l, p->data.lastname) == 0 && strcmp(f, p->data.firstname) == 0) {
/*Print out data.*/
printf("%s, %s, %s, %s\n\n", p->data.lastname, p->data.firstname, p->data.phone, p->data.email);
}
/*If entry is not found:*/
else {
/*Error.*/
printf("Record could not be found.\n\n");
}
}
/*Prints contents of tree.*/
void print_tree(struct tree_node *p) {
/*if tree has nodes:*/
if (p != NULL) {
/*Print node data.*/
print_tree(p->left);
printf("%s, %s, %s, %s\n\n", p->data.lastname, p->data.firstname, p->data.phone, p->data.email);
print_tree(p->right); }
}