Solved

SEARCH ENGINE - BINARY SEARCH TREE

Posted on 1997-04-10
1
467 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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

A high-level exploration of how our ever-increasing access to information has changed the way we do our jobs.
I use more than 1 computer in my office for various reasons. Multiple keyboards and mice take up more than just extra space, they make working a little more complicated. Using one mouse and keyboard for all of my computers makes life easier. This co…
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
This video shows how use content aware, what it’s used for, and when to use it over other tools.

747 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now