Solved

SEARCH ENGINE - BINARY SEARCH TREE

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

Migrating Your Company's PCs

To keep pace with competitors, businesses must keep employees productive, and that means providing them with the latest technology. This document provides the tips and tricks you need to help you migrate an outdated PC fleet to new desktops, laptops, and tablets.

Question has a verified solution.

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

I previously wrote an article addressing the use of UBCD4WIN and SARDU. All are great, but I have always been an advocate of SARDU. Recently it was suggested that I go back and take a look at Easy2Boot in comparison.
Let’s list some of the technologies that enable smooth teleworking. 
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.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

770 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