Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 476
  • Last Modified:

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?
0
jnowlin
Asked:
jnowlin
1 Solution
 
jos010697Commented:
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

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now