Solved

SEARCH ENGINE - BINARY SEARCH TREE

Posted on 1997-04-10
1
470 Views
Last Modified: 2013-11-15
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
Comment
Question by:jnowlin
1 Comment
 
LVL 4

Accepted Solution

by:
jos010697 earned 50 total points
ID: 1249876
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

Back Up Your Microsoft Windows Server®

Back up all your Microsoft Windows Server – on-premises, in remote locations, in private and hybrid clouds. Your entire Windows Server will be backed up in one easy step with patented, block-level disk imaging. We achieve RTOs (recovery time objectives) as low as 15 seconds.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In our personal lives, we have well-designed consumer apps to delight us and make even the most complex transactions simple. Many enterprise applications, however, are a bit behind the times. For an enterprise app to be successful in today's tech wo…
The article will include the best Data Recovery Tools along with their Features, Capabilities, and their Download Links. Hope you’ll enjoy it and will choose the one as required by you.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
This video demonstrates basic masking and how to edit the mask to reveal the desired image.

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question