Hi,
I am working on a C implementation of a BST. Every function I've written so far appears to work. I have the following structure for BST nodes:
Code:
typedef struct node {
Employee *element;
struct node *left, *right;
} NODE;
Where Employee is the following structure:
Code:
typedef struct {
char name[30];
long ID;
char address[40];
char city[20];
int age;
} Employee;
So far, this is what my implementation looks like:
Code:
/* for file i/o and debugging */
#include <stdio.h>
/* for assert() */
#include <assert.h>
/* for memory allocation */
#include <stdlib.h>
/* print a tree */
void printInOrder(FILE *fpout, NODE *root, int depth) {
/* if the node is empty, do nothing */
if (root == NULL || (root != NULL && root->element == NULL)) return;
/* print left subtree */
printInOrder(fpout, root->left, depth + 1);
/* print node */
int i;
for (i = 0; i < depth; i++) fprintf(fpout, " ");
fprintf(fpout, "[%ld] [%s] [%s]\n", root->element->ID, root->element->name, root->element->address);
/* print right subtree */
printInOrder(fpout, root->right, depth + 1);
}
/* compare two employees */
static boolean empcmp(Employee emp1, Employee emp2) {
return emp1.ID > emp2.ID;
}
static NODE *minNode(NODE *root) {
NODE *node = root;
while (node->left != NULL) node = node->left;
return node;
}
/* delete a node */
static void deleteNode(NODE **node) {
/* if this node is a leaf node */
if ((*node)->left == NULL && (*node)->right == NULL) {
free((*node)->element);
free(*node);
}
/* if this node has 1 left child */
else if ((*node)->left != NULL && (*node)->right == NULL) {
NODE *old_root = *node;
*node = (*node)->left;
free(old_root->element);
free(old_root);
}
/* if this node has 1 right child */
else if ((*node)->right != NULL && (*node)->left == NULL) {
NODE *old_root = *node;
*node = (*node)->right;
free(old_root->element);
free(old_root);
}
/* if this node has both children */
else {
NODE *successor = minNode((*node)->right);
*((*node)->element) = *(successor->element);
free(successor->element);
free(successor);
}
}
/* return the maximum of two integers */
static int max(int num1, int num2) {
return (num1 > num2 ? num1 : num2);
}
/* compare two nodes */
static boolean nodecmp(NODE *node1, NODE *node2) {
/* if node1 has an employee element associated with it */
if (node1->element != NULL) {
if (node2->element != NULL) return empcmp(*(node1->element), *(node2->element));
else return TRUE;
}
/* otherwise, return false */
else return FALSE;
}
/* initialize a new binary search tree. */
void initialize(NODE **root) {
*root = (NODE *) malloc(sizeof(NODE));
(*root)->left = (*root)->right = NULL;
}
/* insert a new employee at the tree rooted at `root`. */
boolean insert(NODE **root, Employee e) {
/* create the node to be added to the tree */
NODE *new_node = (NODE *) malloc(sizeof(NODE));
assert(new_node != NULL);
new_node->right = new_node->left = NULL;
/* create the employee pointer */
new_node->element = (Employee *) malloc(sizeof(Employee));
assert(new_node != NULL);
/* copy over the employee record to the node */
*(new_node->element) = e;
/* if this tree is empty */
if (*root == NULL || (*root != NULL && (*root)->element == NULL)) {
*root = new_node;
return TRUE;
}
/* if *root > new_node */
else if (nodecmp(*root, new_node)) {
free(new_node->element);
free(new_node);
/* insert into left subtree of root */
return insert(&((*root)->left), e);
}
/* if new_node > *root */
else if (nodecmp(new_node, *root)) {
free(new_node->element);
free(new_node);
/* insert into right subtree */
return insert(&((*root)->right), e);
}
/* node already exists in the tree */
else return FALSE;
}
boolean delete(NODE **root, long id, Employee *result) {
if (*root == NULL) return FALSE;
if ((*root)->element->ID == id) {
*result = *((*root)->element);
deleteNode(root);
return TRUE;
}
else if ((*root)->left && (*root)->left->element->ID == id) {
*result = *((*root)->element);
deleteNode(&((*root)->left));
(*root)->left = NULL;
return TRUE;
}
else if ((*root)->right && (*root)->right->element->ID == id) {
NODE *old_left = (*root)->right->left;
*result = *((*root)->right->element);
deleteNode(&((*root)->right));
return TRUE;
}
else if ((*root)->element->ID > id) return delete(&((*root)->left), id, result);
else return delete(&((*root)->right), id, result);
}
boolean search(NODE *root, long id, int *comp, Employee *result) {
/* bump the number of three-way comps done */
(*comp)++;
/* if the tree is empty, we were unable to find the matching ID. */
if (root == NULL) return FALSE;
/* search the left subtree */
else if (root->element->ID > id) return search(root->left, id, comp, result);
/* search the right subtree */
else if (root->element->ID < id) return search(root->right, id, comp, result);
/* found it! */
else {
*result = *(root->element);
return TRUE;
}
}
unsigned elementCount(NODE *root) {
/* if this is an empty node, return 0 */
if (root == NULL) return 0;
/* otherwise, return the element count of the count of the two subtrees */
else return 1 + elementCount(root->left) + elementCount(root->right);
}
int height(NODE *root) {
/* if this is an empty node, return 0 */
if (root == NULL) return 0;
/* otherwise, return the hight of the maz of two subtrees */
else return (1 + max(height(root->left), height(root->right)));
}
I'm having trouble with the delete() function, which works in the following situation: Whenever the node has two children, and the right child has no left child. However, delete() does not work in the following situation: Where the node has two children, and the right child DOES have a left child, the left child of that right child just disappears.
I understand why this happens, but I cannot quite figure out a way to solve the problem cleanly. I am open to any suggestions. Thanks for reading such a long post!