CODEWITHSUNDEEP
cmallocbinary-search-tree
warwcat
warwcat

Reputation: 339

malloc in pointer received as argument

I'm implementing an binary search tree but for some reasons I 'm not able to add a node

my: input was :

a.value = 5;
add_bst_node(&t,a);

mystructures:

typedef struct BST_node{
 entity value;
 struct BST_node* left;
 struct BST_node* right;
}BST_node;

typedef struct BST_tree{
 BST_node* root;
}BST_tree;

my code for add a node:

void add_bst_node2(BST_node* root,entity* e){
 if(!root){
  root = (BST_node*)malloc(sizeof(BST_node));
  root->value = *e;
  root->left = NULL;
  root->right = NULL;
  return;
 }
 else if(great_than(&root->value,e))
  add_bst_node2(root->left,e);
 else
  add_bst_node2(root->right,e);
 }

 void add_bst_node(BST_tree* t,entity e){
  add_bst_node2(t->root,&e);
  printf("%d\n",t->root==NULL);
 }

Someone can explayn why I'can't add a node?

Upvotes: 3

Views: 156

Answers (3)

Anton Angelov
Anton Angelov

Reputation: 1244

Apart from not passing double pointer to BST_node (i.e. BST_node**) in add_bst_node2() as noted in the comments, you also didn't implement the function properly.

Your implementation never really adds a node, but instead in enters into infinite recursion.

Here you can find some clean theory about BST - http://www.zentut.com/c-tutorial/c-binary-search-tree/

Here is an untested correction of your code. Note that here we pass pointer to BST_tree instead of BST_node

void add_bst_node2(BST_tree* tree,entity* e){
    if(!tree->root){
        /* If the binary search tree is empty, we just create a root node */
        tree->root = bst_create_node(e);
        return;
    }

    int is_left  = 0;
    BST_node* current_node = tree->root;
    BST_node* prev   = NULL;

    /* Traverse the tree until we find the proper position for the new node.
     * The position is denoted by 'current_node'
     */
    while(current_node != NULL) {
        prev = current_node;

        if(greater_than(&current_node->value, e)) {
            is_left = 1;
            current_node = current_node->left;
        } else {
            is_left = 0;
            current_node = current_node->right;
        }
    }

    /* We finally know the position where we should add the new node */
    if(is_left)
        prev->left = bst_create_node(e);
    else
        prev->right = bst_create_node(e);
}

We introduce another function for creating and initializing a node...

BST_node *bst_create_node(entity *e)
{
    BST_node *n = malloc(sizeof(BST_node));

    n->value = *e;
    n->left = NULL;
    n->right = NULL;

    return n;
}

And finally we change add_bst_node()

void add_bst_node(BST_tree* t,entity e){
    add_bst_node2(t, &e);
    printf("%d\n", t->root==NULL);
}

Upvotes: 1

Sunil Nale
Sunil Nale

Reputation: 46

first thing is that you put an unnecessary structure BST_tree.You do it in simple way like

                 struct node
                {
                    int value;
                    node* left;
                    node* right;
                };
                struct node* root;

I suggest you try with this code 

        struct node* insert(struct node* r, int data)
        {
          if(r==NULL) // BST is not created created
          {
               r = (struct node*) malloc(sizeof(struct node)); // create a new node
               r->value = data;  // insert data to new node
              // make left and right childs empty
               r->left = NULL;   
               r->right = NULL;
          }
         // if the data is less than node value then we must put this in left sub-tree
          else if(data < r->value){ 
               r->left = insert(r->left, data);
          }
         // else this will be in the right subtree
         else {
               r->right = insert(r->right, data);
          }
         return r;
   }`

`

Upvotes: 0

DGounaris
DGounaris

Reputation: 182

From what it seems, a is a struct BST_node and value is a variable in it. You have to either pass the value to the function and handle the node creation there, or pass the whole constructed node and just point to it from the existing tree.

Upvotes: 0

Related Questions