C Binary Search Tree

bnixon10 · 04-04-2008, 07:27 PM

Hi everyone. I'm back here again with another problem I'm having on a programming assignment. What is required is that I prompt the user for a name, over and over again in a loop until they enter "quit", which then would consequently display the results of the binary tree. Here is what I have so far, with errors that I cannot seem to figure out.

Code:

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

#define merror() {printf("memory allocation problem\n"); exit(1);}

struct NODE_STRUCT {
  char* name;
  struct NODE_STRUCT *left, *right;
};
typedef struct NODE_STRUCT NODE;

NODE* MakeNode(char* name) {
  NODE* tree;
  tree=(NODE*)malloc(sizeof(NODE));
  tree->name=name;
  tree->left=tree->right=0;
  return tree;
}

NODE* Insert(NODE* tree,char* string);
void Display(NODE* tree);
void Display1(NODE* node);


/* function main ---------------------------------------------------- */
int main() {
 char buf[21];
 char name;
  int i;

  while(1) {
    printf("Enter a name:");
    fflush(stdout);
    for(i=0; i<20; i++) {
      buf[i]=fgetc(stdin);
      if (buf[i]=='\n') {
        buf[i]='\0';
        break;
      }
    }
    if (buf[0]==NULL) {
      printf("empty entry\n");
      continue;
    }
    if (i==20) {
      printf("entry too long\n");
      while(fgetc(stdin)!='\n');
      continue;
    }
    if (strcmp(buf,"quit")==0) break;
    name = atoi(buf);
    tree = Insert(tree,name);
  }//end while
  Display(tree);
	return 0;
}/* end main */

/* function Insert ------------------------------------------------------- */
NODE* Insert(NODE* tree,char* string) {

NODE *p		

p = tree;
while(1) {
	i = strcmp(p--> name, string);
	if (i == 0) { printf("Duplicate name");
			  return tree;
			}
	if(i<0( {
	if (p -> left == 0) {
		p -> left = (NODE*)malloc(sizeof(NODE));
		p -> left -> name = (char*)malloc(strlen(string)+1);
		strcpy(p->left-->name, string);
		p -> left -> left -> = p -> left -> right = 0;
		return tree;
			}
		p = p --> left;
		continue;
}
	if(i>0( {
	if (p --> right == 0) {
		p --> right = (NODE*)malloc(sizeof(NODE));
		p --> right --> name = (char*)malloc(strlen(string)+1);
		strcpy(p-->right-->name, string);
		p --> right -->  left --> = p --> right --> right = 0;
		return tree;
			}
		p = p --> left;
		continue;
			}
		} // end while
	return 0;
}/* end Insert */


/* function Display ----------------------------------------------------- */

void Display(NODE* tree) {
  if (tree==0) {
    printf("tree is empty\n");
    return;
  }else
    Display1(tree);
}/* end Display */



/* function Display1 ----------------------------------------------------- */
void Display1(NODE* node) {

  if (node==0) return;
 
  Display1(node->left);
  Display1(node->right);


}/* end Display1 */

Any help is appreciated. Thanks

PTrenholme · 04-04-2008, 08:58 PM

If that's the code you're using, check the syntax of the pointer operator. You seem to be using "->" and "-->" as synonyms.

rupertwh · 04-04-2008, 10:04 PM

Hi,

the most obvious flaws that sprang to the eye:

Quote:

Originally Posted by bnixon10

Code:

...

int main() {
 char buf[21];
 char name;

...
    name = atoi(buf);
    tree = Insert(tree,name);
...

The 'name = atoi(buf);' is puzzling. It doesn't make any sense.
I assume you did this to appease the compiler which complained that you are trying to assign a pointer to an integer type? Don't just add/change code to appease a compiler. If the compiler complains, first understand *why* it complains, then change your code to fix the actual problem.

In your case, you declared name to be of type char, which is an integral type. What you meant, though, was char* -- a pointer to char, aka string. (But the variable name is superfluous anyway, you could have just written

Code:

   tree = Insert(tree, buf);

This line:

Code:

if (buf[0]==NULL) {

should throw a compiler warning as well. NULL is a pointer, but buf[0] is an integer.

As to your use of '-->' instead of '->' which has alread been commented, e.g.:

Code:

p = p --> left;

What this code actually means:

check if p is greater than left
decrease p by one
assign 1 to p, if p was greater than left, otherwise assign 0

Probably not what you intented. Great idea for code obfuscation, though.
(Actually, behavior will undefined if I'm not mistaken, as it is not clear whether p is assigned or decreased first.)

bnixon10 · 04-05-2008, 10:38 AM

Ok thanks for the input everyone. I've gone back and revised my code, to come still with just one single error I don't really understand.
First, I really don't know why I was using --> as well as ->, that has been fixed. The error I receive now on compile is the following, and I really do not understand why I am getting it.

Error E2193 coll.c 124: Too few parameters in call to 'Insert' in function main
*** 1 errors in Compile ***

I highlighted the error line

My code is as follows:

Code:

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

#define merror() {printf("memory allocation problem\n"); exit(1);}

struct NODE_STRUCT {
  //int value;
  char *string;
  char* name;
  struct NODE_STRUCT *left, *right;
};
typedef struct NODE_STRUCT NODE;

NODE *TREE=0;


void Display1(NODE* TREE) { // depth first, recursive, inorder
  if (TREE==0) return;
  Display1(TREE->left);
  printf("%c\n",TREE->name);
  Display1(TREE->right);
}


void Display(NODE* TREE) {
  if (TREE==0) {
    printf("tree is empty\n");
    return;
  }else
    Display1(TREE);
}

NODE* Insert(NODE* TREE,char* string, int i, NODE* P) {

if(TREE==0){
TREE=(NODE*)malloc(sizeof(NODE));
	if(TREE==NULL)
	merror();
TREE->name=(char*)malloc(strlen(string)+1);
	if(TREE->name==NULL)
	merror();
strcpy(TREE->name,string);
TREE->left=TREE->right=0;
return TREE;
}


P=TREE;

while(1)
{
i=strcmp(P->name, string);
if(i==0){
printf("duplaicate value, ignored\n");
return P;
}
if(i<0){
if(P->left==0){
P->left=(NODE*)malloc(sizeof(NODE));
	if(P->left==NULL)
	merror();
P->left->name=(char*)malloc(strlen(string)+1);
	if(P->left->name==NULL)
	merror();
strcpy(P->left->name,string);
P->left->left=P->left->right=0;
return P;
}
else{
P=P->left;
continue;
}
}
if(i>0){
	if(P->right==0){
P->right=(NODE*)malloc(sizeof(NODE));
	if(P->right==NULL)
	merror();
P->right->name=(char*)malloc(strlen(string)+1);
	if(P->right->name==NULL)
	merror();
strcpy(P->right->name,string);
P->right->left=P->right->right=0;
return P;
}
else{
P=P->right;
continue;
	}
}
}
}

int main() {
char buf[21];
  char* string;
  
  int i, value; 

  while(1) {
    printf("enter a name or 'quit' to exit: ");
    fflush(stdout);
    for(i=0; i<21; i++) {
      buf[i]=fgetc(stdin);
      if (buf[i]=='\n') {
        buf[i]='\0';
        break;
      }
    }
    if (i==0) {
      printf("empty entry\n");
      continue;
    }
    if (i==10) {
      printf("entry too long\n");
      while(fgetc(stdin)!='\n');
      continue;
    }
    if (strcmp(buf,"quit")==0) break;
	
    strcpy(string,buf);
	
Insert(TREE,string);
  }//end while

  Display(TREE);
  return 0;
}

Thanks, and sorry for my beginner mistakes.

rupertwh · 04-05-2008, 09:46 PM

OK, so you define Insert() with 4 parameters as

Code:

NODE* Insert(NODE* TREE,char* string, int i, NODE* P) {
...

But you call Insert() with only 2 parameters like:

Code:

Insert(TREE,string);

Then the compiler complains "Too few parameters in call to 'Insert' in function".
And you say you cannot figure out why the compiler complains? You cannot be serious.