Can anyone help me with my binary search tree

Question

I'm a computer engineering student and I have to write BST as an assignment but the code is not like what everyone written(so far as I search for some example,so I'm desperate now) Here is my code so far(My classroom use C as a main language not C++)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct bst_node
{
        int data;
        struct bst_node *right;
        struct bst_node *left;
}BST_NODE;
typedef struct bst
{
        int size;
        BST_NODE *root;
}BST;
void print(BST_NODE *pos)
{
     printf("%d(0)",pos->data);
    if(pos->left != NULL)
     {
                  printf("%d(L)\n",pos->left->data);
                  pos=pos->left;
                  }
     if(pos->right != NULL)
     {
                  printf("%d(R)\n",pos->right->data);
                  pos=pos->right;
                  }
     if(pos->left != NULL)
                  print(pos->left);
     if(pos->right != NULL)
                  print(pos->right);
}         
int main()
{
    int number;
    BST b;
    BST_NODE *pos;
    b.root=NULL;
    while(1)
    {
            scanf("%d",&number);
            printf("value=%d",number);
            if(number<=0)

                         break;

            if(b.root==NULL)
            {
                            b.root=(BST_NODE*)malloc(sizeof(BST_NODE));
                            pos=b.root;
                            pos->data=number;
                            pos->left=NULL;
                            pos->right=NULL;
            }
            else
            {
                pos=b.root;
                while(pos)
                {
                          if(number>pos->data)
                          {
                              if(pos->right==NULL)
                              {                             
                                      pos->right=(BST_NODE*)malloc(sizeof(BST_NODE));
                                      pos->right->left=NULL;
                                      pos->right->right=NULL;
                                      pos->right->data= number;
                                      pos=pos->right;

                              }
                              else
                              {
                                   pos->right->data= number;
                                   pos=pos->right;

                              }        
                          } 

                          if(number<pos->data)
                          {
                                 if(pos->left==NULL)
                                 {             
                                      pos->left=(BST_NODE*)malloc(sizeof(BST_NODE));
                                      pos->left->left=NULL;  
                                      pos->left->right=NULL; 
                                      pos->left->data=number;
                                      pos=pos->left;

                                 }
                                  else
                                  {
                                      pos->left->data=number;
                                      pos=pos->left;

                                  }
                         }

                }
            }
    }
    print(b.root); 

    return 0;
}

I don't know what wrong with this code because it can only receives 2 value then it stops working. The only thing I found out so far to be a problem is while(pos)loop and I try to fix this for week.I would be grateful,if anyone help me solve this problem. Print it out to would be great. P.S -stop working mean the windows I run program in just freeze or hang.

Please be more specific. What does "stop working" mean, and what inputs are you entering? — OldProgrammer
– OldProgrammer, Commented Dec 27, 2013 at 4:17
I don't see where you initialize the tree and you may want to look up recursion, as it is a more elegant solution for this problem — James Black
– James Black, Commented Dec 27, 2013 at 4:20
To Jame Black:My teacher give me a while(1) loop for the "else" after while(1) she have us filled that and print it out for assignment. and for the first question; stop working mean it the window where I run just freeze or APPcrash sometime. but Thank for both anyway — RHLS
– RHLS, Commented Dec 27, 2013 at 4:27

Jonas Bötel · Accepted Answer · 2013-12-27 04:32:33Z

1

You want to break out of your while(pos) loop as soon as you malloc a new node. You are done inserting so stop working.

Also you don't want to overwrite all ->data values while traversing the tree in your else branches.

answered Dec 27, 2013 at 4:32

Jonas Bötel

4,5021 gold badge23 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

atk Over a year ago

I think you found it! in addition, rsih will need to reset pos to the root node outside the nested while loop, but inside the outer while loop

atk · Accepted Answer · 2013-12-27 14:36:07Z

0

When you add a value to the tree, it looks like you always replace the existing value with the input number instead of just traversing to the next level. Remove

pos->right->data = number;

And

pos->left->data =  numbér;

From main()

You also should add an 'else' before the left node check. As it stands, you're checking the right branch and then the left branch every time through the loop. If you check the right branch and make a hit, you'll always check the left branch, too. Probably not a problem, but unnecessary.

Not sure that's the reason 'it stops working' as 'it stops working' is awful darn vague, but that looks suspicious to me.

Additionally...

Be consistent on your indentation. Sometimes the indentation is more spaces than other times
add spaces between struct definitions and Breen function declarations. Think of these things as chapters in a book. Use the whitespace to make separate things clearly separate.
add a prompt within the loop to indicate that it's expecting input. If you think your app has frozen, it may simply be waiting for input
add a check at the start of print() and sensibly handle null roots. This could occur if you type a negative number as your input the first time around. Missing such a check and typing a negative as your first input may crash.
Oh! And use calloc() instead of malloc(). Calloc initializes new memory to nulls, while malloc does not. Malloc just gives you whatever memory it happens to give you, containing whatever random garbage it may contain. If you use calloc, you will have less liklihood of issues with bad memory.

edited Dec 27, 2013 at 14:36

answered Dec 27, 2013 at 4:30

atk

9,3723 gold badges34 silver badges32 bronze badges

6 Comments

Jonas Bötel Over a year ago

There is recursion in the print method near the end.

RHLS Over a year ago

That's help me a lots thanks and sorry for indentation

atk Over a year ago

@Rslh i think LumpN found the core issue, though I'll leave my answer up as it has several review comments :)

atk Over a year ago

@Rslh oh, and don't be sorry about the indentation, just fix your code and be consistent in the future.

RHLS Over a year ago

To atk: This is personal thing but can you help me. When I learn I understand how each technique work like quick sort, link listed etc. but I'm stink when it come to code writing.How can I do better a code writing or just take time to learn.

|

Collectives™ on Stack Overflow

Can anyone help me with my binary search tree

2 Answers 2

1 Comment

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related