Problem while making a binary tree

**fancy217** · 07-16-2008

I was trying to make a simple binary tree
When i ran it, turbo C terminated
while it wrkd fine when i compiled using gcc
I used a count variable to keep a check in the loop....and the value of count had gone upto 25 when it should have been just 3

(this happened when i entered numbers 7 6 5 8)

Code:

#include<stdio.h>

#include<conio.h>



struct nodetype

{

int info;

struct nodetype *rt;

struct nodetype *lt;

};



typedef struct nodetype *node;



node getnode()

{

node tmp=(node)malloc(sizeof(node));

return tmp;

}



node maketree(int x)

{

node p= getnode();

if(p==NULL)printf("No space");

p->info=x;

p->lt=NULL;

p->rt=NULL;

return(p);

}



void setleft(node q, int x)

{

node tmp;

if(q==NULL)

 {

 printf("Father null");

 return;

 }





 if(q->lt!=NULL)

  {

   printf("Invalid insertion");

   return;

  }



 q->lt= maketree(x);





}





void setright(node q, int x)

{

node tmp;

if(q==NULL)

 {

 printf("Father null");

 return;

 }





 if(q->rt!=NULL)

  {

   printf("Invalid insertion");

   return;

  }



 q->rt= maketree(x);



}



void insert(node *tree, int x)

{

int count=0;

node p,q;

p=q= *tree;



if(p== NULL)

{

 printf("tree");

 *tree=maketree(x);

 return;

}



while((p->info!=x)&&(q!=NULL))

 {

  p=q;

  //count++;



  if(q->info>x)

  q=q->lt;



  else

  q=q->rt;

  //printf("count: %d" , count);

 }



 if(x==p->info)

 printf("Number already exixts");



 else

 {

  if(x>p->info)

  setright(p,x);



  else

  setleft(p,x);

 }

}


//For inorder traversal of the tree
void intrav(node p)

{



 if(p!=NULL)

  {

  intrav(p->lt);

  printf(" %d ", p->info);

  intrav(p->rt);

  }

}



void main()

{

int num;

node mytree= NULL;

clrscr();

do

{

printf("NUMBER: ");

scanf("%d", &num);

insert(&mytree, num);

printf("\nEnter more: ");

scanf("%d", &num);

}while(num==1);



intrav(mytree);

getch();

}

I would highly appreciate if someone would go through the code and point out my problem
Thanks

**MacGyver** · 07-16-2008

Originally Posted by fancy217

I would highly appreciate if someone would go through the code and point out my problem

That's partly what a compiler is for. And Turbo C is garbage these days.

**fancy217** · 07-16-2008

I hv gone through a code a couple of times now but cannot come up with the flaw.
I have faced this before which means I am going wrong somewhere.....
Please give a look at the code.....

**swoopy** · 07-16-2008

I'm not spotting any problem with your code. Try traversing the tree after every insert(), and let us know what it prints for the tree:

Code:

insert(&mytree, num);
intrav(mytree);

printf("\nEnter more: ");
scanf("&#37;d", &num);

}while(num==1);

**swoopy** · 07-16-2008

>node tmp=(node)malloc(sizeof(node));
Make this:
node tmp = malloc(sizeof(*node));

You should also #include <stdlib.h> for malloc().

**swoopy** · 07-16-2008

You might need to use the actual object:
node tmp = malloc(sizeof(*tmp));

**fancy217** · 07-16-2008

It is working fine with the solution you suggested.
Thanks a bunch
Can you please explain me why it wasn't k earlier...coz the pointer also would give the same size of the node. It was working perfectly fine with gcc though.

**swoopy** · 07-16-2008

>Can you please explain me why it wasn't k earlier...coz the pointer also would give the same size of the node.
node is defined as a pointer to struct nodetype:

Code:

typedef struct nodetype *node;

So sizeof(node) or sizeof(struct nodetype *) is the size of a pointer on your system. You can printf() this value to see what it is. It could be 4, or it could be more. However sizeof(struct nodetype) is bigger. This struct contains one int, plus two pointers. And it may even contain some padding. So sizeof(struct nodetype) is at least 10, possibly more:

Code:

printf("sizeof(node): &#37;lu\n", (unsigned long) sizeof(node));
printf("sizeof(struct nodetype): %lu\n", (unsigned long) sizeof(struct nodetype));

See what that prints. You were probably allocating 4 bytes of memory for the struct, when it actually needed 10 to 12 bytes. The reason it worked perfectly under gcc is you got lucky, and didn't corrupt the memory area.

>It was working perfectly fine with gcc though.
This is the consequence of code containing undefined behavior. Undefined behavior means anything may happen. The program may run perfectly, or it may crash at the line causing undefined behavior, or it may keep running farther and crash.

**swoopy** · 07-16-2008

>void main()
And it's a good habit to return an int from main, since void main() is wrong.

Code:

int main(void)
{
.
.
	return 0;
}

See this FAQ entry: What's the difference between... > main() / void main() / int main() / int main(void) / int main(int argc, char *argv[])

Thread: Problem while making a binary tree

Thread Tools

Search Thread

Display

Problem while making a binary tree

Similar Threads

Interpreter.c

binary search tree help

problem in binary expression tree

binary tree node structure

binary tree problem??