home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_10_10
/
1010124a
< prev
next >
Wrap
Text File
|
1992-08-12
|
5KB
|
266 lines
/* Figure 3 - Binary Tree with variably sized Data - */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
/* node definition */
typedef struct node {
struct node *left, *right;
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)());
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));
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));
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;
}
/*
* 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("Find");
gets(buf);
rec.key[0] = '\0';
strncpy(rec.key, buf, KEYSIZE);
rec.key[KEYSIZE] = '\0';
found = tree_root;
while(found = tree_find(found, &rec, rec_cmp)) {
tree_print(found->info);
found = found->right;
++count;
}
printf("\n\t%d String(s) Found\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);
}