SEARCH ENGINE - BINARY SEARCH TREE

Hello.

I need to apply a SEARCH engine to this assignment:

/* PROBLEM4.C ; Code from Mr. Vic Gagnon

   PROBLEM4 contains the code for 'Project #3',
   Intro. to Data Strutures with C.

   PROBLEM4.C reads the data from an input file and stores it in a
   BINARY tree.
   It is capable of searching for one of the 32 reserved words in C.

   It demonstrates preorder, postorder and inorder tree traversals.

   It tells the height of the tree after the data has been stored in
   the tree under the following conditions:

            Read from the input file in ascending order.

            Read from the input file in random order starting somewhere
            in the middle of the list of reserved words.


*/



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#define MAXARRAY 80

/* The following struct, typedef-ed to be TREE_NODE, sets up
   the binary search tree.
*/


typedef struct tnode {
      char *key;
      struct tnode *left, *right;
} TREE_NODE;


/* FUNCTION PROTOTYPES */


TREE_NODE *addtree(TREE_NODE *, char *);
char *strdup(char*);
TREE_NODE *talloc(void);
void inorder_treeprint(TREE_NODE *);
void visit_node(TREE_NODE *);
void free_node_mem(TREE_NODE *p);



int main(void)
{
 TREE_NODE *root = NULL;

 FILE *infp;     /* Pointer to input stream of type FILE. */

 char i_file_name[MAXARRAY], file_buffer[MAXARRAY];

 /* Get the complete path name and file name. */

 printf("Please enter a file name for processing.\n");
 scanf("%s", i_file_name);


 /* Open input file. Test for good file name. */

 if ((infp = fopen(i_file_name,"r")) == NULL) {
     printf("Error in input file name : '%s'\n",i_file_name);
     return 0;    /* Stop processing. */
 }

 /* Read lines from input file, invoke addtree function */

 printf("\n\n\t\tT H E   F I L E, '%s' ,   A S   E N T E R E D .  .  .  .\n\n", i_file_name);

 while( fgets(file_buffer,MAXARRAY , infp) != NULL ) {
     file_buffer[strlen(file_buffer) - 1] = '\0';
     printf("%s\n",file_buffer);
     root = addtree(root, file_buffer);

 } /* End while. */


 printf("\n\n\t\tT R A V E R S E   T H E   T R E E   I N O R D E R\n\n");
 printf("\n\n\t\t\t USING THE FILENAME: '%s', AS INPUT.\n", i_file_name );
 inorder_treeprint(root);

 return 0;

} /* End main. */

/* Add a node with w, at or below pointer p. */

TREE_NODE *addtree(TREE_NODE *p, char *w)
{
  int cond;

  if (p == NULL) {
      p= talloc();      /* Make a new node. */
      p->key = strdup(w);
      p->left = p->right = NULL;
  } else if ((cond = strcmp(w, p->key)) == 0) {
      printf("Error: key \"%s\" already in tree structure\n", w);
      exit(-1);
    }
  else if (cond < 0) /* go into left subtree. */
      p->left = addtree(p->left, w);
  else               /* go into right subtree. */
      p->right = addtree(p->right, w);

  return p;
}  /* End addtree. */



char *strdup(char *w)
/* Copy the string w to a safe place in memory, return the location
   pointer to caller. strdup allocates the EXACT memory needed, no more,
   no less.
*/

{
  char *p;

  p = (char *) malloc(strlen(w)+1); /* 1 added for null terminator. */
  if (p != NULL)
      strcpy(p, w);
  return p;
}

TREE_NODE *talloc(void)

/* Cast pointer , return NULL if malloc fails. */

{
/*  printf("size of TREE_NODE is %d\n",sizeof(TREE_NODE)); */

  return (TREE_NODE *) malloc(sizeof(TREE_NODE));
}



/* inorder_treeprint - use in-order traversal of tree p */
void inorder_treeprint(TREE_NODE *p)
{
  if (p != NULL) {
    inorder_treeprint(p->left);
    visit_node(p);
    inorder_treeprint(p->right);
  }
  free(p);
}  /* End inorder_treeprint. */




void visit_node(TREE_NODE *p)
{
 printf("%s\n", p->key);
}


void free_node_mem(TREE_NODE *p)
{
  free(p);
}




Is there one search engine which is best suited for this
type of problem than others?
jnowlinAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
jos010697Connect With a Mentor Commented:
Well, just because you're stuck to a binary tree, implies that
there's just one search engine available: a binary tree 'walker'.

You've almost already written it, i.e. it resembles the addtree
function. Here it is:

TREE_NODE* findtree(TREE_NODE* root, char* word) {

int r;

if (!root)
   return 0;

r= strcmp(root->key, word);

if (!r)
   return root;

if (r < 0)
   return findtree(root->left, word);

return findtree(root->right, word);

}

does you help you out a bit?

kind regards,

Jos

ps. There might be some typos in the stuff above; I'm typing
this in a silly little window which uses an even sillier tiny font ;-)
 
0
All Courses

From novice to tech pro — start learning today.