Problem while making a binary tree

This is a discussion on Problem while making a binary tree within the C Programming forums, part of the General Programming Boards category; I was trying to make a simple binary tree When i ran it, turbo C terminated while it wrkd fine ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    3

    Unhappy Problem while making a binary tree

    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

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Quote Originally Posted by fancy217 View Post
    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.

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    3
    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.....

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    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);

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >node tmp=(node)malloc(sizeof(node));
    Make this:
    node tmp = malloc(sizeof(*node));

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

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    You might need to use the actual object:
    node tmp = malloc(sizeof(*tmp));

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    3
    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.

  8. #8
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >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.

  9. #9
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >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[])

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 01:51 PM
  3. problem in binary expression tree
    By hanij in forum C Programming
    Replies: 6
    Last Post: 04-28-2002, 08:31 AM
  4. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM
  5. binary tree problem??
    By fergie in forum C++ Programming
    Replies: 1
    Last Post: 04-23-2002, 12:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21