#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
/* node definition */
typedef struct node {
struct node *left, *right, *parent;
void *info;
size_t info_size;
}
node;
/* enumerated type to signify tree traversal order */
typedef enum tree_order {
NO_ORDER, PRE_ORDER, IN_ORDER, POST_ORDER } tree_order;
tree_order t_order = IN_ORDER;
/* enumerated type for error checking */
typedef enum tree_error {
OK, LINK_ERROR, NULL_PTR, NO_MEMORY } tree_error;
tree_error t_error = OK;
/* function prototypes */
void (*report)();
int tree_insert(node **root, void *info, size_t info_size,
int (*info_cmp)());
void tree_trace(node *root);
node *tree_find(node *root, void *info, int (*info_cmp)());
node *tree_delete(node *root, node *this_node);
void tree_free(node *root);
/* non-recursive tree insertion, if duplicate key */
* then new data substituted returns 1 on success */
* 0 on failure */
int tree_insert(node **root, void *info, size_t info_size,
int (*info_cmp)())
{
node *this_node = *root;
int dif;
t_error = OK;
/* does not enter while loop when instantiating root */
while(this_node) {
if(! (dif = info_cmp (info, this_node->info))) {
free(this_node->info);
goto tree_load;
}
else if(dif < 0) {
if(this_node->left)
this_node = this_node->left;
else {
this_node->left = (node *) calloc(1,
sizeof(node));
if(this_node->left)
this_node->left->parent = this_node;
this_node = this_node->left;
goto tree_load;
}
}
else {
if(this_node->right)
this_node = this_node->right;
else {
this_node->right = (node *) calloc(1, sizeof(node));
if(this_node->right)
this_node->right->parent = this_node;
this_node = this_node->right;
goto tree_load;
}
}
}
/* only arrives here when instantiating root */
this_node = (node *) calloc(1, sizeof(node));
*root = this_node;
tree_load:
if(! this_node) {
t_error = NO_MEMORY;
return 0;
}
this_node->info = calloc(1, info_size);
if(! this_node->info) {
t_error = NO_MEMORY;
free(this_node);
return 0;
}
memmove(this_node->info, info, info_size);
this_node->info_size = info_size;
return 1;
}
/* recursive tree traversal function with 3 traversing modes */
void tree_trace(node *root)
{
if(! root)
return;
switch(t_order) {
case PRE_ORDER :
report(root->info);
tree_trace(root->left);
tree_trace(root->right);
return;
case IN_ORDER :
tree_trace(root->left);
report(root->info);
tree_trace(root->right);
return;
case POST_ORDER :
tree_trace(root->left);
tree_trace(root->right);
report(root->info);
return;
default:
return;
}
}
/* non-recursive find, returns first matching entry or NULL */
node *tree_find(node *root, void *info, int (*info_ cmp)())
{
int cmp_val;
node *this_node = root;
while(this_node) {
if(! (cmp_val = info_cmp(info, this_node->info)))
return this_node;
else if(cmp_val < 0)
this_node = this_node->left;
else
this_node = this_node->right;
}
t_error = (root) ? OK : NULL_PTR;
return this_node;
}
node *tree_delete(node *root, node *this_node)
{
typedef enum tree_child {
NOT_CHILD, LEFT_CHILD, RIGHT_CHILD } tree_child;
tree_child child;
node *temp;
t_error = OK;
if((!this_node) || (! root)) {
t_error = NULL_PTR;
return root;
}
if(root == this_node)
child = NOT_CHILD;
else if(this_node->parent->left == this_node)
child = LEFT_CHILD;
else if(this_node->parent->right == this_node)
child = RIGHT_CHILD;
else {
t_error = LINK_ERROR;
return root;
}
if(! this_node->right) {
temp = this_node;
this_node = this_node->left;
}
else if(! this_node->left) {
temp = this_node;
this_node = this_node->right;
}
else {
temp = this_node->right;
while(temp->left)
temp = temp->left;
temp->left = this_node->left;
temp->left->parent = temp;
temp = this_node;
this_node = this_node->right;
}
switch(child) {
case NOT_CHILD :
free(temp->info);
free(temp);
if(this_node)
this_node->parent = NULL;
return this_node;
case LEFT_CHILD :
temp->parent->left = this_node;
if(this_node)
this_node->parent = temp->parent;
free(temp->info);
free(temp);
break;
case RIGHT_CHILD :
temp->parent->right = this_node;
if(this_node)
this_node->parent = temp->parent;
free(temp->info);
free(temp);
/* drop through to return */
}
return root;
}
/* recursive post-order traversal to deallocate tree memory */
void tree_free(node *root)
{
if(! root)
return;
tree_free(root->left);
tree_free(root->right);
if(root->info)
free(root->)info);
free(root);
}
/*
* interactive tree test driver */
*/
#define KEYSIZE 80
typedef struct {
char key[KEYSIZE];
int id;
}
record;
record rec;
void prompt(char *verb)
{
printf("\nEnter String to %s\t( <Enter> for none )\n>",
verb);
}
int rec_cmp(record *rec1, record *rec2)
{
return strcmp(rec1->key, rec2->key);
}
void tree_print(record *this_record)
{
if(! this_record)
return;
printf("Key: %s\nRecord Number: %d\n",this_record->key,
this_record->id);
}
void main(void)
{
node *tree_root = NULL;
node *found = NULL;
char *orders[4] = { "no-order", "pre-order", "in-order",
"post-order" };
char buf[KEYSIZE] = "";
int record num = 0;
int count = 0;
int ch;
prompt("Insert");
while(*gets(buf)) {
strncpy(rec.key, buf, KEYSIZE);
rec.key[KEYSIZE] = '\0';
rec.id = ++record_num;
if(! (tree_insert(&tree_root, &rec,
sizeof rec, rec_cmp))) {
printf("\n\tTree Insertion Failure!\n");
exit(1);
}
prompt("Insert");
}
prompt("Delete");
gets(buf);
rec.key[0] = '\0';
strncpy(rec.key, buf, KEYSIZE);
rec.key[KEYSIZE] = '\0';
while(found = tree_find(tree_root, &rec; rec_cmp)) {
tree_print(found->info);
tree_root = tree_delete(tree_root,found);
++count;
}
printf("\n\t%d String(s) Deleted\n", count);
printf("\n\tSelect Tree Traversal Type\n");
printf(
"\n\t\t1) pre-order\n\t\t2) in-order\n\t\t3)
post-order\n\n\t>");
ch = getch();
ch -= '0';
if((ch < PRE_ORDER) || (ch > POST_ORDER))
ch = NO_ORDER;
printf("\n\t... Walking Tree %s ...\n\n", orders[ch]);
t_order = ch;
report = tree_print;
tree_trace(tree_root);
tree_free(tree_root);
}
/* End of File */