6 Replies - 1508 Views - Last Post: 13 December 2010 - 06:54 PM Rate Topic: -----

#1 Teph  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 16-October 10

C++ Binary Tree Insertion

Posted 11 December 2010 - 03:54 PM

im stuck on one of the most basic steps, insertion.

when i call insertion function i want it to check if node#1 is empty, if its empty i want it to make a new tree with the input as its info.

the problem is, when i try to write an if statement, the program freezes and says general protection fault.

/*

/* Include Files   */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

/* Preprocessor Constants  */

#define MAX 30
struct node
{
	char info;
	struct node *left;
	struct node *right;
};
typedef struct node *NODEPTR;




NODEPTR insert(NODEPTR p, char x);
void setright(NODEPTR p, char x);
void setleft(NODEPTR p, char x);
int driver (void);
void printmenu (void);
NODEPTR maketree(char x);


void main( void )
{
	int value;

	clrscr();

	do {
		  value = driver ();
	}  while (value != 0);
}

/* This is the driver function which calls the functions */

int driver (void)
{
	NODEPTR p;
	int choice;
	char x;
	do {
	  printmenu ();
	  fflush(stdin);
	  scanf("%d", &choice);

	  switch (choice) {
		 case 0: break;

		 case 1: printf("Enter Letter to be Inserted");
					fflush(stdin);
					scanf("%c", &x);
					insert(p , x);
					getch();
			 break;

		 case 2: printf("Option 2 is selected - Function Call -  Press any key");
					getch();
			 break;

		 case 3: printf("Option 3 is selected - Function Call - Press any key");
					getch();
			 break;

		 case 4: printf("Option 4 is selected - Function Call - Press any key");
					getch();
			 break;

		 default:printf("\n\n\t  Incorrect entry - try again - Press any key\n");
			 getch();     /* holds the output screen */
	  }
	}  while (choice < 0 || choice > 4);
	return (choice);
}


/* This function prints the menu  */

void printmenu (void)
{
	clrscr();
	printf("\n\n\n\n\n\n");
	printf("\t**********************************\n");
	printf("\t*         List of Choices        *\n");
	printf("\t**********************************\n");
	printf("\n\n");
	printf("\t   0 -- quit\n");
	printf("\t   1 -- Option 1\n");
	printf("\t   2 -- Option 2\n");
	printf("\t   3 -- Option 3\n");
	printf("\t   4 -- Option 4\n");
	printf("\n\n\tEnter your selection, 0 through 4 > ");
	return;
}



NODEPTR insert(NODEPTR p, char x)
{
	NODEPTR q,r;
	 if(p->info == NULL){     <---ERROR OCCURS HERE ;( 
		p = maketree(x);
		return(p);
	  }


	  else

	return(p);
}


void setleft(NODEPTR p, char x)
{
	if(p == NULL)
		printf("Void insertion\n");
	else if(p->left !=NULL)
		printf("Invalid insertion\n");
	else
		p->left = maketree(x);
}

void setright(NODEPTR p, char x)
{
	if(p == NULL)
		printf("Void insertion\n");
	else if(p->right !=NULL)
		printf("Invalid insertion\n");
	else
		p->right = maketree(x);
}


NODEPTR maketree(char x)
{
	NODEPTR p;

	p=getnode();
	p->info = x;
	p->left = NULL;
	p->right=NULL;
	return(p);

}

NODEPTR getnode(void )
	{
		 NODEPTR p;
		 p = (NODEPTR)malloc((unsigned) (sizeof(NODEPTR)) );
		 p->info = NULL;
		 return (p);
	}

This post has been edited by Teph: 11 December 2010 - 03:56 PM


Is This A Good Question/Topic? 0
  • +

Replies To: C++ Binary Tree Insertion

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6052
  • View blog
  • Posts: 23,487
  • Joined: 23-August 08

Re: C++ Binary Tree Insertion

Posted 11 December 2010 - 04:30 PM

Think about this: what's the value of p the first time you try to insert?
Was This Post Helpful? 0
  • +
  • -

#3 Teph  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 16-October 10

Re: C++ Binary Tree Insertion

Posted 12 December 2010 - 10:14 AM

View PostJackOfAllTrades, on 11 December 2010 - 03:30 PM, said:

Think about this: what's the value of p the first time you try to insert?

i suppose it was {NULL, \x0, NULL}(which should have just exited the function, not crashed the whole program)

but anyway, ive made some progress since last post, but when i exit my insert function and return to driver function my tree doesnt get returned, it becomes null again... any ideas?

/*

/* Include Files   */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

/* Preprocessor Constants  */

#define MAX 30
struct node
{

	struct node *left;
	char info;
	struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR tree;

NODEPTR getnode(void )
	{
		 NODEPTR p;
		 p = (NODEPTR)malloc((unsigned) (sizeof(NODEPTR)) );
		 p->info = NULL;
		 return (p);
	}


NODEPTR insert(NODEPTR p, char x);
void setright(NODEPTR p, char x);
void setleft(NODEPTR p, char x);
int driver (NODEPTR tree);
void printmenu (void);
NODEPTR maketree(char x);
void preorder(NODEPTR tree);

void main( void )
{
	int value;
	clrscr();

	do {
		  value = driver (tree);
	}  while (value != 0);
}

/* This is the driver function which calls the functions */

int driver (NODEPTR tree)
{
	NODEPTR p;
	int choice;
	char x;
	do {
	  printmenu ();
	  fflush(stdin);
	  scanf("%d", &choice);

	  switch (choice) {
		 case 0: break;

		 case 1:
					insert(p , x);
					getch();
			 break;

		 case 2: printf("Postorder Tree");
					preorder(tree);
					getch();
			 break;

		 case 3: printf("Option 3 is selected - Function Call - Press any key");
					getch();
			 break;

		 case 4: printf("Option 4 is selected - Function Call - Press any key");
					getch();
			 break;

		 default:printf("\n\n\t  Incorrect entry - try again - Press any key\n");
			 getch();     /* holds the output screen */
	  }
	}  while (choice < 0 || choice > 4);
	return (choice);
}


/* This function prints the menu  */

void printmenu (void)
{
	clrscr();
	printf("\n\n\n\n\n\n");
	printf("\t**********************************\n");
	printf("\t*         List of Choices        *\n");
	printf("\t**********************************\n");
	printf("\n\n");
	printf("\t   0 -- quit\n");
	printf("\t   1 -- Option 1\n");
	printf("\t   2 -- Option 2\n");
	printf("\t   3 -- Option 3\n");
	printf("\t   4 -- Option 4\n");
	printf("\n\n\tEnter your selection, 0 through 4 > ");
	return;
}



NODEPTR insert(NODEPTR tree, char x)
{
	char response;
	NODEPTR p, q;
	 clrscr();
	printf("Enter Root for new tree");
	fflush(stdin);
	scanf("%c", &x);
	tree = maketree(x);


	fflush(stdin);
	printf("Do you have more data to enter?");
	scanf("%c", &response);


	while (response =='y' || response == 'Y')
	{
		printf("Enter Next Character");
		fflush(stdin);
		scanf("%c", &x);
		p = q = tree;
		while( x != (p->info) && q != NULL)
		{
			p=q;
			if (x < (p->info))
				q = (p->right);
			else
				q = (p->right);
		}
		if(x == (p->info))
			printf("%c is a duplicate", x);
		else if(x < (p->info))
			setleft(p,x);
		else
			setright(p,x);

		printf("\nDo you have more Data?");
		fflush(stdin);
		scanf("%c", &response);

	}
	printf("press any key to return to main menu");
	return (p,tree);   <-- so shouldnt this return the tree?*********
}


void setleft(NODEPTR p, char x)
{
	if(p == NULL)
		printf("Void insertion\n");
	else if(p->left !=NULL)
		printf("Invalid insertion\n");
	else
		p->left = maketree(x);
}

void setright(NODEPTR p, char x)
{
	if(p == NULL)
		printf("Void insertion\n");
	else if((p->right) !=NULL)
		printf("Invalid insertion\n");
	else
		(p->right) = maketree(x);
}


NODEPTR maketree(char x)
{
	NODEPTR p;

	p=getnode();
	p->info = x;
	p->left = NULL;
	p->right=NULL;
	return(p);

}


void preorder(NODEPTR tree)

{
	if(tree!=NULL)

	{

		printf("%c", (tree->info));
		preorder(tree->left);
		preorder(tree->right);
		getch();

		}

}

This post has been edited by Teph: 12 December 2010 - 10:16 AM

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 4006
  • View blog
  • Posts: 12,361
  • Joined: 25-December 09

Re: C++ Binary Tree Insertion

Posted 12 December 2010 - 10:43 AM

One thing I noticed was:

     fflush(stdin);



You should NEVER, Never, never do this, it leads to undefined behavior.


Jim
Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg  Icon User is offline

  • member icon


Reputation: 4006
  • View blog
  • Posts: 12,361
  • Joined: 25-December 09

Re: C++ Binary Tree Insertion

Posted 12 December 2010 - 10:59 AM

When I compile your code these are the error/warning messages I received.

Quote

main.c|28|warning: return type of ‘main’ is not ‘int’|
main.c||In function ‘insert’:|
main.c|105|warning: comparison between pointer and integer|
main.c|104|warning: unused variable ‘r’|
main.c|104|warning: unused variable ‘q’|
main.c||In function ‘maketree’:|
main.c|142|warning: implicit declaration of function ‘getnode’|
main.c|142|warning: assignment makes pointer from integer without a cast|
main.c|150|warning: no previous declaration for ‘getnode’|
main.c|150|error: conflicting types for ‘getnode’|
main.c|142|note: previous implicit declaration of ‘getnode’ was here|
main.c||In function ‘getnode’:|
main.c|154|warning: assignment makes integer from pointer without a cast|
||=== Build finished: 1 errors, 10 warnings ===|


So I would have to say that my problems start with:

void main( void )


The problem you are having probably are the warnings that have "assignment makes pointer from integer without a cast" contained in them.

And another big problem is since you do not have a prototype for getnode() the compiler thinks you are returning an int.

And for line 105:

 if(p->info == NULL){ //    <---ERROR OCCURS HERE ;(


What type of variable is p->info? Is it a pointer?

Jim
Was This Post Helpful? 0
  • +
  • -

#6 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6052
  • View blog
  • Posts: 23,487
  • Joined: 23-August 08

Re: C++ Binary Tree Insertion

Posted 12 December 2010 - 11:38 AM

Quote

i suppose it was {NULL, \x0, NULL}(which should have just exited the function, not crashed the whole program)

Your assumption is incorrect, and it will certainly crash your program. Your p variable is a pointer typedef'd to not LOOK like a pointer, which -- although a common idiom -- is a BAD IDEA for just this reason.

You create it in main here:
NODEPTR p;

That pointer points WHERE exactly? Answer: you don't know. Time to go read about pointers.
Was This Post Helpful? 0
  • +
  • -

#7 Teph  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 16-October 10

Re: C++ Binary Tree Insertion

Posted 13 December 2010 - 06:54 PM

lol at binky pointer fun, good stuff.

anyway, for anyone who comes to this thread later seeking enlightenment, this is how i handled the insert function(along with a few other functions)

its not pretty but it does the job

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


#define FALSE 0
#define TRUE 1

/* Preprocessor Constants  */

typedef struct tree
{
	char data;
	struct tree *left,*right;
}node;
node *makenode(char);
void setleft(node *,char);
void setright(node *,char);
void preorder(node *);
void insert();
void getleaf(node *);
int driver ();
void printmenu (void);
void search(node *,char);
void findsib(node *,char);

node *q,*k;
int l=0,d=1;
int driver ();
int inserted;
node *root,*p,*q;
int count=0;

int main( void )
{

	int value;
	clrscr();

	do {
		  value = driver ();
	}  while (value != 0);



   return(0);
}

/* This is the driver function which calls the functions */

int driver ()
{
	 char x;
	int choice;


	do {
	  printmenu ();
	  fflush(stdin);
	  scanf("%d", &choice);

	  switch (choice) {


		 case 1:
					insert();
					getch();
			 break;

		 case 2: printf("\nPreorder traversal is \n");
					preorder(root);

					getch();
			 break;

		 case 3:	printf("What item are you searching for: ");
					fflush(stdin);
					scanf("%c", &x);
					search(root, x);


					getch();
			 break;

		 case 4: getleaf(root);
					printf("there are %d leaves",count);
					count = 0;
					p = q;
					getch();
			 break;

		 case 5: printf("THIS FUNCTION DONT WORKEnter Item whos siblings you want to find");
					fflush(stdin);
					scanf("%c", &x);
					findsib(root,x);
					getch();

			 break;

		 case 6: printf("exiting program");
					exit(0);
					break;





		 default:printf("\n\n\t  Incorrect entry - try again - Press any key\n");
			 getch();     /* holds the output screen */
	  }
	}  while (choice < 1 || choice > 6);
	return (choice);
}


/* This function prints the menu  */

void printmenu (void)
{
	clrscr();
	printf("\n\n\n\n\n\n");
	printf("\t**********************************\n");
	printf("\t*         List of Choices        *\n");
	printf("\t**********************************\n");
	printf("\n\n");
	printf("\t  1: Insert items into Binary Tree \n");
	printf("\t  2: Print Pretrav \n");
	printf("\t  3: Search for an Item \n");
	printf("\t  4: Count leaves \n");
	printf("\t  5: Find Sibling \n");
	printf("\t  6: Quit \n");
	printf("\n\n\tEnter your selection, 1 through 6 : ");
	return;
}



void insert()
{
	
	char x,f;
	clrscr();
	 while (inserted == FALSE)
	 {
	printf("\nEnter the root :");
	fflush(stdin);
	scanf("%c",&x);
	root=makenode(x);
	inserted = TRUE;
	}

	printf("\nEnter the data(type any # to end) :");
	fflush(stdin);
	scanf("%c",&x);
	while(!(isdigit(x)) )
	{
		p=root;
		while(p!=NULL)
		{
			q=p;
			if(x<p->data)
			{
				p=p->left;
			}
			else
			{
				p=p->right;
			}
		}
		if(x<q->data)
		{
			setleft(q,x);
		}
		else
		{
			setright(q,x);
		}
		printf("\nEnter the data(type any # to end) :");
		fflush(stdin);
		scanf("%c",&x);


	}


	printf("press any key to return to main menu");


}


node *makenode(char x)
{
	node * temp;
	temp=(node *)malloc(sizeof(node));
	temp->data=x;
	temp->left=NULL;
	temp->right=NULL;
	return(temp);
}
void setleft(node *p,char x)
{
	node *temp;
	if(p==NULL)
	{
		printf("Error");
	}
	temp=makenode(x);
	p->left=temp;
}
void setright(node *p,char x)
{
	node *temp;
	if(p==NULL)
	{
		printf("Error");
	}
	temp=makenode(x);
	p->right=temp;
}


void preorder(node *p)
{
	if(p!=NULL)
	{
		printf("%c\t",p->data);
		preorder(p->left);
		preorder(p->right);
	}
}




void search(node *p,char x)
{

node *q, *r;
	q = r = p;
	if(q!=NULL)
	{

			while(p->data != x && p->right != NULL)
		{
			p = p->right;
		}

			if(p->data != x)
			{
          p = q;
			}

		while(p->data != x && p->left != NULL)
		{
		  p= p->left;
		}

		if(p->data == x)
		{


			printf("%c found\n", p->data);

			if(p->left != NULL)
			{
				printf("%c 's left child = %c\n",(p->data), (p->left)->data);
			}
			else
			{
				printf("%c has no left child\n", p->data);
			}

			if(p->right != NULL)
			{
				printf("%c 's right child = %c\n", (p->data),(p->right)->data);
			}
			else
			{
				printf("%c has no right child\n", p->data);
			}
		}
		else
      printf("Item not found - Press any key to continue");
	 }
}



void getleaf(node *p)
{
	if (p!=NULL)
	{
		if(p->right == NULL && p->left == NULL)
		{
		 count++;
		}
		getleaf(p->left);
		getleaf(p->right);


	}

}




now if someone could just tell me how to find a sibling of a given node, using only left and right pointers. that would be perfect
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1