#ifndef BTREE_C_FILE_H #define BTREE_C_FILE_H /* rcs revision information */ /* $Id: btree_c_file.h,v 1.2.4.1 1999/05/04 17:00:28 jkarner Exp $ */ /* revisions : Nov 2001: modified to fix warnings for BDE - sjaganat */ static char *p_btree_c = { "\ /* \n\ ************************************************************ \n\ * Function : btree_print_node \n\ * \n\ * Abstract : This is a recursive function to print out \n\ * the nodes of a binary tree in depth first order. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/14/93 \n\ * \n\ * Modified : \n\ * \n\ ************************************************************ \n\ */ \n\ int \n\ btree_print_node(p_node) \n\ btree_node_st *p_node; \n\ { \n\ /* local variables */ \n\ \n\ \n\ \n\ /**************************************/ \n\ if(p_node == NULL) \n\ { \n\ return(0); \n\ } \n\ \n\ printf(\"%8s %7d %6d\\n\",p_node->name, p_node->num, p_node->weight); \n\ \n\ btree_print_node(p_node->p_left); \n\ btree_print_node(p_node->p_right); \n\ \n\ return(0); \n\ \n\ } /* end btree_print_node */ \n\ \n\ \n\ \n\ \n\ /* \n\ *********************************************************** \n\ * Function : btree_display_nodes \n\ * \n\ * Abstract : Function to traverse the btree and print out \n\ * each node in a depth first fashion. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/14/93 \n\ * \n\ * Modified : \n\ * \n\ ************************************************************ \n\ */ \n\ int \n\ btree_display_nodes(p_root) \n\ btree_node_st *p_root; \n\ { \n\ /* local variables */ \n\ \n\ \n\ /**************************************/ \n\ printf(\"\\n\\nAbbreviation Index Weight - Binary Tree Output\\n\"); \n\ printf( \"------------ ----- ------\\n\\n\"); \n\ \n\ btree_print_node(p_root); \n\ \n\ return(0); \n\ \n\ } /* end btree_display_nodes */ \n\ \n\ \n\ \n\ \n\ /* \n\ *********************************************************** \n\ * Function : btree_does_node_exist \n\ * \n\ * Abstract : Function to determine if abbreviation exists \n\ * in the lut binary tree. \n\ * \n\ * returns : index number of abbreviation \n\ * or ERROR if it does not exist. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/14/93 \n\ * \n\ * Modified : \n\ * \n\ ************************************************************ \n\ */ \n\ int \n\ btree_does_node_exist(p_node, name) \n\ btree_node_st *p_node; \n\ char name[]; \n\ { \n\ /* local variables */ \n\ \n\ int test, \n\ ret_stat; \n\ \n\ /**************************************/ \n\ \n\ if(p_node == NULL) \n\ { \n\ return(ERROR); \n\ } \n\ \n\ if( (test = strcmp(p_node->name, name)) == 0) \n\ { \n\ return(p_node->num); \n\ } \n\ \n\ ret_stat = btree_does_node_exist(p_node->p_left, name); \n\ if(ret_stat >= 0) \n\ { \n\ return(ret_stat); \n\ } \n\ \n\ \n\ ret_stat = btree_does_node_exist(p_node->p_right, name); \n\ if(ret_stat >= 0) \n\ { \n\ return(ret_stat); \n\ } \n\ else \n\ { \n\ return(ERROR); \n\ } \n\ \n\ } /* end btree_does_node_exist */ \n\ \n\ \n\ /* \n\ ************************************************************ \n\ * Function : btree_insert_node \n\ * \n\ * Abstract : Function to insert a node into an existing btree, \n\ * or if btree does not exist create a new one and \n\ * insert the node as the root. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/14/93 \n\ * \n\ * Modified : \n\ * \n\ ************************************************************ \n\ */ \n\ int \n\ btree_insert_node(p_new, abbr, index) \n\ btree_node_st **p_new; \n\ char abbr[]; \n\ int index; \n\ { \n\ /* local variables */ \n\ \n\ int test; \n\ \n\ /**************************************/ \n\ \n\ btree_node_st *p_temp, \n\ *p_node; \n\ \n\ /**************************************************/ \n\ /* first check if btree exists - if not create it */ \n\ /**************************************************/ \n\ if(*p_new == NULL) \n\ { \n\ p_node = (btree_node_st *) calloc(sizeof(btree_node_st), 1); \n\ \n\ strcpy(p_node->name, abbr); \n\ \n\ p_node->num = index; \n\ p_node->weight = 2; \n\ p_node->p_right = NULL; \n\ p_node->p_left = NULL; \n\ \n\ \n\ *p_new = p_node; \n\ return(0); \n\ } \n\ \n\ \n\ /* insert into existing binary tree */ \n\ \n\ p_temp = *p_new; \n\ \n\ /*******************************************/ \n\ /* check out if abbreviation already exists */ \n\ /* if so return the index of the abbrev */ \n\ /********************************************/ \n\ test = strcmp(p_temp->name, abbr); \n\ \n\ if(test == 0) \n\ { \n\ /* node exists */ \n\ printf(\"Node : %s Already exists...\\n\", p_temp->name); \n\ return(0); \n\ } \n\ else if (test < 0) /* insert into right child */ \n\ { \n\ btree_insert_node(&p_temp->p_right, abbr, index); \n\ } \n\ else if (test > 0) /* insert into left child */ \n\ { \n\ btree_insert_node(&p_temp->p_left, abbr, index); \n\ } \n\ \n\ \n\ p_temp->weight = btree_wt(p_temp->p_left) + btree_wt(p_temp->p_right); \n\ \n\ return(0); \n\ \n\ } /* end btree_insert_node */ \n\ \n\ \n\ \n\ /* \n\ ************************************************************ \n\ * Function : btree_create \n\ * \n\ * Abstract : Function to create the btree from the look up table. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/14/93 \n\ * \n\ * Modified : \n\ * \n\ ************************************************************ \n\ */ \n\ int \n\ btree_create(p_lut) \n\ lut_st *p_lut; \n\ { \n\ /* local variables */ \n\ \n\ int idx; \n\ \n\ char *p_abbr; /* ptr to abbreviation */ \n\ \n\ /**************************************/ \n\ \n\ /* traverse the lut */ \n\ \n\ for(idx=0; idx < LUT_NUM_ELEMENTS; idx++) \n\ { \n\ /* get next element in the lut */ \n\ \n\ p_abbr = lut_get_name(p_lut, idx); \n\ if(p_abbr != NULL) \n\ { \n\ /* add to btree */ \n\ \n\ btree_insert_node(&p_lut->p_btree_root, p_abbr, idx); \n\ } \n\ \n\ } /* end for */ \n\ \n\ \n\ return(0); \n\ \n\ } /* end btree_create */ \n\ \n\ \n\ /* \n\ ************************************************************ \n\ * Function : btree_destroy \n\ * \n\ * Abstract : Function to delete the binary tree and \n\ * free up the memory allocated to the tree. \n\ * \n\ * Created by : T. Cunningham \n\ * \n\ * Creation Date : 4/15/93 \n\ * \n\ * Modified : \n\ * \n\ *********************************************************** \n\ */ \n\ int \n\ btree_destroy(p_node, p_back) \n\ btree_node_st *p_node; \n\ btree_node_st *p_back; \n\ { \n\ /* local variables */ \n\ \n\ char child_dir; \n\ /**************************************/ \n\ \n\ if(p_back == NULL) \n\ { \n\ /* this is a root node */ \n\ child_dir = 'N'; \n\ } \n\ else if(p_back->p_right == p_node) \n\ { \n\ /* this is a right child of the parent */ \n\ \n\ child_dir = 'R'; \n\ } \n\ else if(p_back->p_left == p_node) \n\ { \n\ /* this is a left child of the parent */ \n\ \n\ child_dir = 'L'; \n\ } \n\ \n\ \n\ \n\ /* if leaf node */ \n\ if( (p_node->p_left == NULL) && (p_node->p_right == NULL)) \n\ { \n\ /***********************/ \n\ /* this is a leaf node */ \n\ /***********************/ \n\ \n\ /* set parent ptr to this node to NULL */ \n\ \n\ if(child_dir == 'R') \n\ { \n\ p_back->p_right = NULL; \n\ } \n\ else if(child_dir == 'L') \n\ { \n\ p_back->p_left = NULL; \n\ } \n\ else \n\ { \n\ /* node is root */ \n\ } \n\ \n\ free(p_node); \n\ \n\ return(0); \n\ } \n\ \n\ \n\ /* not a leaf node */ \n\ \n\ if(p_node->p_left == NULL) \n\ { \n\ /*****************************/ \n\ /* node has right child only */ \n\ /*****************************/ \n\ \n\ btree_destroy(p_node->p_right, p_node); \n\ } \n\ else /* left node exists */ \n\ { \n\ if(p_node->p_right == NULL) \n\ { \n\ /****************************/ \n\ /* node has left child only */ \n\ /****************************/ \n\ btree_destroy(p_node->p_left, p_node); \n\ } \n\ else \n\ { \n\ /***********************************/ \n\ /* node has two children */ \n\ /***********************************/ \n\ \n\ btree_destroy(p_node->p_left, p_node); \n\ btree_destroy(p_node->p_right, p_node); \n\ } \n\ } \n\ \n\ \n\ \n\ \n\ /*******************************************/ \n\ /* If you get here you are now a leaf node */ \n\ /* All of your subtrees have been deleted */ \n\ /*******************************************/ \n\ \n\ /* set parent ptr to this node to NULL */ \n\ \n\ if(child_dir == 'R') \n\ { \n\ p_back->p_right = NULL; \n\ } \n\ else if(child_dir == 'L') \n\ { \n\ p_back->p_left = NULL; \n\ } \n\ else \n\ { \n\ /* node is root */ \n\ } \n\ \n\ free(p_node); \n\ \n\ return(0); \n\ \n\ } /* end btree_destroy */ \n\ \n\ \n\ \n\ \n\ \n\ \n\ \n\ /* \n\ **************************************************************** \n\ * Function : btree_wt \n\ * \n\ * Abstract : Function to give a weight to each node in the tree \n\ * The weight is based on number of nodes below it. \n\ * This is used for balencing btrees - however the \n\ * the balence code was not included in this gen \n\ * version due to a lack of time to debug it... \n\ * \n\ * Created by : D. Pinkney \n\ * \n\ * Creation Date :?????? \n\ * \n\ * Modified : \n\ * \n\ ********************************************************** \n\ */ \n\ int \n\ btree_wt(t) /* returns weight of tree or 1 otherwise */ \n\ btree_node_st *t; \n\ { \n\ if (t == (btree_node_st *) NULL) \n\ { \n\ return(1); \n\ } \n\ else \n\ { \n\ return(t->weight); \n\ } \n\ \n\ } /* end btree_wt */ \n\ \n\ \n\ " }; #endif