/*---------------------------------------------------------------------- File : bst_test.c Contents: test of binary search trees Author : Christian Borgelt History : 21.06.1998 file created 10.07.1998 access to traversal orders added 02.09.1998 adapted to changes of module bstree ----------------------------------------------------------------------*/ #include #include #include #include "bstree.h" /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define NAMELEN 256 /* maximal length of names */ /*---------------------------------------------------------------------- Auxiliary Functions ----------------------------------------------------------------------*/ static char* getname (char *buf, int maxlen) { /* --- read a name */ char *dst, *src; /* to traverse the name read */ fgets(buf, maxlen, stdin); /* read a string from stdin */ dst = src = buf; /* traverse the name read */ while ((*src == ' ') || (*src == '\t')) src++; /* skip leading blanks */ while (*src) *dst++ = *src++; /* copy name to front */ if ((dst > buf) && (*(dst-1) == '\n')) dst--; /* if there is a newline, remove it */ *dst = '\0'; /* terminate the string */ return buf; /* return buffer read into */ } /* getname() */ /*--------------------------------------------------------------------*/ static void putname (void *obj, void *client) { /* --- print a name from a tree node */ static int i = 0; /* counter */ if (!obj) { i = 0; return; } /* if no name given, reset counter */ if (client) printf((char*)obj); /* otherwise print string */ else printf("%2d: \"%s\"\n", i++, (char*)obj); } /* putname() */ /*---------------------------------------------------------------------- Main Functions ----------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ int r; /* buffer for results */ BSTREE *bst; /* binary search tree */ char name[NAMELEN]; /* name to insert/remove/look up */ char *tmp; /* buffer for name to insert */ int cmd; /* command */ bst = bst_create((BST_CMPFN*)strcmp, free); if (!bst) { printf("%s: not enough memory\n", argv[0]); return -1; } /* create a sect. sorted vector */ printf("%s --- test of binary search trees\n", argv[0]); printf("type l for a list of commands\n"); while (1) { /* command loop */ printf("> "); fflush(stdout); do { cmd = getchar(); /* get next command */ } while (strchr(" \t\n", cmd) != NULL); switch (cmd) { /* evaluate command */ case 'i': /* --- insert into binary search tree */ tmp = (char*)malloc(strlen(getname(name, NAMELEN)) +1); if (!tmp) { printf("not enough memory\n"); break; } r = bst_insert(bst, strcpy(tmp, name)); if (r >= 0) break; /* insert name into tree */ if (r < -1) printf("name already exists\n"); else printf("not enough memory\n"); free(tmp); break; /* if an error occured, delete name */ case 'r': /* --- remove from binary search tree */ r = bst_remove(bst, getname(name, NAMELEN)); if (r < 0) printf("not found\n"); else printf("removed\n"); break; /* remove name and print result */ case 'o': /* --- look up in binary search tree */ tmp = (char*)bst_lookup(bst, getname(name, NAMELEN)); if (!tmp) printf("not "); /* look up name */ printf("found\n"); break; /* and print result */ case 'n': /* --- determine number of nodes */ printf("%d\n", bst_count(bst)); break; case 'h': /* --- determine tree height */ printf("%d\n", bst_height(bst)); break; case 'b': /* --- check balance */ if (!bst_balanced(bst)) printf("not "); printf("balanced\n"); break; case 'c': /* --- clear binary search tree */ bst_clear(bst); break; case 's': /* --- show all names in tree */ #ifdef DEBUG bst_show(bst, putname, (void*)1); break; #else putname(NULL, NULL); /* clear object counter */ bst_apply(bst, BST_INORDER, putname, (void*)0); break; #endif case 't': /* --- traverse nodes */ do { cmd = getchar(); /* get next character */ } while (strchr(" \t\n", cmd) != NULL); putname(NULL, NULL); /* clear object counter */ switch (cmd) { /* evaluate order */ case '<': cmd = BST_PREORDER; break; case '>': cmd = BST_POSTORDER; break; default : cmd = BST_INORDER; break; } /* get order identifier */ bst_apply(bst, cmd, putname, (void*)0); break; /* print tree elements */ case 'l': /* --- print help */ printf("commands:\n"); /* (i.e. a list of commands) */ printf("i n --- insert name n into binary search tree\n"); printf("r n --- remove name n from binary search tree\n"); printf("o n --- look up name n in binary search tree\n"); printf("n --- determine number of nodes\n"); printf("h --- determine tree height\n"); printf("b --- check whether tree is balanced\n"); printf("c --- clear binary search tree " "(remove all names)\n"); printf("s --- show all names in binary search tree\n"); printf("t --- traverse nodes: < - preorder\n"); printf(" : - inorder\n"); printf(" > - postorder\n"); printf("l --- print this list of commands\n"); printf("q --- quit program\n"); break; case 'q': /* --- quit program */ bst_delete(bst); /* delete binary search tree */ return 0; /* and return `ok' */ default: /* --- unknown command */ printf("unknown command --- type l for a list\n"); break; } } /* while (1) */ } /* main() */ /*---------------------------------------------------------------------- Compile this program with gcc -DBST_EXTFN bst_test.c bstree.c to get the AVL tree version. Add the option -DBST_NOAVL to get the normal binary search tree version. If the option -DDEBUG is added, the tree output function uses indentation to indicate the depth of a node. ----------------------------------------------------------------------*/