binary search tree removal in C

[drwoo123]

Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working, even the removal, I just don't know how to keep track of the parent, so that I can set its child to the child of the node to be removed.

IE - if I had




A
/ \
B C
/
D
\
E


And I wanted to remove D, then I would set the left of C to E (the child of D).

Correct??

I'll post the following code which is specifically the remove function first - followed by the rest of it.




Also the assignment spec is as follows

Write a C program in a single file that implements a binary search tree of words in a dictionary. Your program should have a pointer variable that references the root of the binary tree. Initially the tree will be empty.

Your program should ask the user if he or she wants to insert a data value, remove a data value or print the content of the tree. Use integers to indicate which option the user wants (1 for insert, 2 for remove, 3 for printing the inorder traversal of the tree, 4 for printing the preorder traversal of the tree and 5 for exiting the program).
If the user wants to insert a data value, the program should prompt the user for the word to insert, and it should then insert the word into the binary search tree at its proper position. If the word is already in the tree, print an appropriate message.
If the user wants to remove a data value, the program should prompt the user for the word to remove, and it should then try to locate the word in the binary search tree, and if it is there, remove it from the tree. Otherwise, display an appropriate message for the user. To simply the assignment, you are not required to remove a node with two children, so if the user wants to remove such a node, print an appropriate message and ignore the entry.
You should implement the insert operation, remove operation, inorder traversal and the preorder traversal as separate functions in your C program.
NOTES:
1. All declarations (variable, type, define, etc.) before the main program are global. Make sure you define the variables for your main program within main (to make them local to main) and do NOT make all variables global.

2. Although your code can be saved in separate files, but do not do this for this assignment. Submit your program in a single file named "dictionary.c".

3. Each word contains only letters and its maximum length is 15. Following statement shows how you can define this maximum value:



#define WORD_SIZE 15

4. Since debugging in C will be significantly harder than in Java, you may include debugging code in your program that can be "turned off" when you don't need it anymore (instead of commenting it out or erasing it). See HW4 for the idea.

5. You will need to use dynamic memory allocation for this assignment. Whenever a node is removed from the tree, be sure to free its memory allocation. Also, once the user exits the program, if there are nodes still in the tree, these must be de-allocated as well!



Thanks in advance to anyone who can help me out - my background is really more in java, and this is my first C project, but I figured this is what I should really learn, if I ever want to be any good.



void removeNode(node **tree, char removeData[WORD_SIZE])
{
// Traverse Tree to find node to remove
// If Node has both children, dont remove throw error
// If not, remove node and bring up proper child.
int leftChild = 0; // 0 is false 1 is true
int rightChild = 0;
int bothChild = 0; // 0 is false and 1 is true
int compareValue = 0;

if ( ((*tree)->left) != NULL)
leftChild=1;
if ( ((*tree)->right) != NULL)
rightChild=1;
if ( (leftChild==1) && (rightChild==1) )
bothChild = 1;

if (*tree == NULL)
{
printf("\nEmpty Tree Nothing to Remove.\n");
return;
}
compareValue = strcmp(removeData, (*tree)->data);

// String is found and does not have two children
if ( (compareValue == 0) && (bothChild == 0) )
{
if (leftChild == 1)
{
printf("\nData Found, and it has a left Child.");
// Set the left of the parent to the
return;
}



if (rightChild == 1)
{
printf("\nData found, and it has a right child.\n");
return;
}
// Remove Current and Make right the current

else
{
printf("\nData found, and it has no children\n");
return;
}
// Remove Current Node

}

if ( (compareValue == 0) && (bothChild == 1) )
{
printf("\nNode found but has both children, cannot be removed.\n");
}

if ( (compareValue < 0) && (leftChild == 0) )
{
printf("\nData is not in left child of the tree.\n");
return;
}

if ( (compareValue > 0) && (rightChild == 0) )
{
printf("\nData is not in right child of the tree.\n");
return;
}


if ( (compareValue < 0) && (leftChild == 1) )
{
//Go Left while there is a left
printf("\nLeft going remove.\n");
removeNode( &(*tree)->left, removeData);
}

if ( (compareValue > 0) && (rightChild == 1) )
{
//Go right while there is a right
printf("\nRight going remove.\n");
removeNode( &(*tree)->right, removeData);

}
}

 

[drwoo123]

Finally all the code is here

I am wondering, am I approaching this incorrectly, in terms of the algorithm.??


thanks again



#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define WORD_SIZE 15

struct node_type {
char data[WORD_SIZE];
struct node_type *left, *right;
};

typedef struct node_type node;
// Prototypes
void inorder(node *tree);
void preorder(node *tree);
void postorder(node *tree);
void insertNode(node **tree, node **insertData);
void removeNode(node **tree, char removeData[WORD_SIZE]);

// Left - Root - Right
void inorder(node *tree)
{
if (tree->left)
inorder(tree->left);
printf("%s ", tree->data);

if (tree->right)
inorder(tree->right);
}
// Root Left Right
void preorder(node *tree)
{
printf("%s ", tree->data);
if (tree->left)
preorder(tree->left);
if (tree->right)
preorder(tree->right);
}
// Left - Right - Root
void postorder(node *tree)
{
if (tree->left)
preorder(tree->left);
if (tree->right)
preorder(tree->right);
printf("%s ", tree->data);
}
void insertNode(node **tree, node **insertData)
{ // If the root is null put it there
// Otherwise keep going left until you should place data.
// Otherwise go right until you should place data.


if (*tree == NULL)
{
*tree = *insertData;
return;
}
else if ( (strcmp((*tree)->data, (*insertData)->data)) == 0)
{
printf("Same data, cannot overwrite.\n");
}
else if ( (strcmp((*tree)->data, (*insertData)->data)) > 0)
{
printf("Go Left\n");
insertNode(&(*tree)->left, insertData);
}

else if ( (strcmp((*tree)->data, (*insertData)->data)) < 0)
{
printf("Go Right\n");
insertNode( &(*tree)->right, insertData);
}

//printf("\nAfter insertion: %s\n", (*tree)->data);
}
void removeNode(node **tree, char removeData[WORD_SIZE])
{
// Traverse Tree to find node to remove
// If Node has both children, dont remove throw error
// If not, remove node and bring up proper child.
int leftChild = 0; // 0 is false 1 is true
int rightChild = 0;
int bothChild = 0; // 0 is false and 1 is true
int compareValue = 0;

if ( ((*tree)->left) != NULL)
leftChild=1;
if ( ((*tree)->right) != NULL)
rightChild=1;
if ( (leftChild==1) && (rightChild==1) )
bothChild = 1;

if (*tree == NULL)
{
printf("\nEmpty Tree Nothing to Remove.\n");
return;
}
compareValue = strcmp(removeData, (*tree)->data);

// String is found and does not have two children
if ( (compareValue == 0) && (bothChild == 0) )
{
if (leftChild == 1)
{
printf("\nData Found, and it has a left Child.");
// Set the left of the parent to the
return;
}



if (rightChild == 1)
{
printf("\nData found, and it has a right child.\n");
return;
}
// Remove Current and Make right the current

else
{
printf("\nData found, and it has no children\n");
return;
}
// Remove Current Node

}

if ( (compareValue == 0) && (bothChild == 1) )
{
printf("\nNode found but has both children, cannot be removed.\n");
}

if ( (compareValue < 0) && (leftChild == 0) )
{
printf("\nData is not in left child of the tree.\n");
return;
}

if ( (compareValue > 0) && (rightChild == 0) )
{
printf("\nData is not in right child of the tree.\n");
return;
}


if ( (compareValue < 0) && (leftChild == 1) )
{
//Go Left while there is a left
printf("\nLeft going remove.\n");
removeNode( &(*tree)->left, removeData);
}

if ( (compareValue > 0) && (rightChild == 1) )
{
//Go right while there is a right
printf("\nRight going remove.\n");
removeNode( &(*tree)->right, removeData);

}
}
int main(void)
{
char menu[] ="\n(1) Add Word\n(2) Delete Word\n(3) Inorder Print\n(4) Preorder Print\n(5) Postorder Print\n(6) Quit\nYour Choice: ";
int choice=0;
char input[WORD_SIZE];
char removeString[WORD_SIZE];
int debug = 0;

int valid;
node *rootTree, *cursor, *inputNode, *deleteNode;
rootTree = NULL;
cursor = rootTree;
inputNode = NULL;
deleteNode = NULL;

// Begin programatic insert

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "o", WORD_SIZE);
insertNode(&rootTree, &inputNode);


inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "k", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "b", WORD_SIZE);
insertNode(&rootTree, &inputNode);


inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "l", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "g", WORD_SIZE);
insertNode(&rootTree, &inputNode);


inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "r", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "p", WORD_SIZE);
insertNode(&rootTree, &inputNode);


inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "q", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "z", WORD_SIZE);
insertNode(&rootTree, &inputNode);


inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "j", WORD_SIZE);
insertNode(&rootTree, &inputNode);


// End Programatic Insert

do
{
valid=0;
printf("%s", menu);
scanf("%d", &choice);

if (choice == 1)
{
printf("Enter Word: ");
scanf("%s", &input);

if (debug)
printf("\nYou entered: %s\n", input);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, input, WORD_SIZE);

if (debug)
printf("\nData inserted in tree: %s\n", inputNode->data);

insertNode(&rootTree, &inputNode);
valid=1;
}
else if (choice == 2)
{
printf("Enter Word: ");
scanf("%s", &input);

strncpy(removeString, input, WORD_SIZE);
removeNode(&rootTree, removeString);
valid=1;
}
else if (choice == 3)
{
printf("InOrder Tree: ");
inorder(rootTree);
valid=1;
}
else if (choice == 4)
{
printf("PreOrder Tree: ");
preorder(rootTree);
valid=1;
}
else if (choice == 5)
{
printf("PostOrder Tree: ");
postorder(rootTree);
valid=1;
}
else if (choice == 6)
{
printf("Thank you for using the dictionary manager.\n");
valid=1;
}
else if (valid == 0)
{
printf("\nInvalid Choice please try again!!\n");
}
}while(choice != 6);


free(rootTree);
free(inputNode);
free(cursor);

return 0;
}

 

[EagleKeeper]

Option 1)
Add to the node definition structure, a pointer to the parent.

struct node_type {
struct node_type *parent;
char data[WORD_SIZE];
struct node_type *left, *right;
};

When you determine that there is only a single child, then change the childs parent to the parent's parent (grandparent) when removing the parent

Option 2)
Keep a pointer that will always refer to the current grandparent.
Then you can "adopt" the grandchild when you kill the parent.

 

[glugglug]

Originally posted by: drwoo123


A
/ \
B C
/
D
\
E

And I wanted to remove D, then I would set the left of C to E (the child of D).

Correct??

Heh, this is correct, however it doesn't look like it in your post because the forum eats all the spaces -- in the post it looks like D is the left child of B and so E would end up being the left of B. Hold down alt and enter 255 on your keypad to produce a character that looks like a space but isn't. Copy that to the clipboard and replace all your spaces with it.

Edit: nm the stupid forum seems to outsmart me on that and converts the 255 chars to spaces which don't get displayed right! ARGH!

 

[drwoo123]

Much appreciated for the help, could you kind of modify the implementation I posted so that it has the parent, not in the struct, but in the remove method only.

I'm trying but im pulling my hair out .. what little i have left.

thanks
tarique

 

[Barnaby W. Füi]

type & nbsp; to make spaces that will be shown. I had to put a space in it but it's an ampersand, the letters nbsp, and a semicolon, all together.

if(foo)
bar();