Insert function in C Binary Tree?

Question

My Binary Tree code in C isn't running at all and I'm not sure exactly why. Is there anything blatantly wrong in the function? It runs with just one insert use, but any more and it stops working. It's just supposed to be a simple function that inserts ints at their right place along the tree.

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


typedef struct trees Tree;
struct trees {
    int data;
    Tree *left;
    Tree *right;
};

Tree *inicio=NULL; 


void insert(int n){
        Tree *novo = (Tree*)malloc(sizeof(Tree));
        Tree *aux;
        Tree *pai;

        novo->data=n;
        novo->left=NULL;
        novo->right=NULL;
    if(inicio==NULL){
            inicio = novo;
            return;
    } else {
        aux = inicio;
        pai = NULL;
        while(1){
            pai = aux;
            if(n>pai->data){
                aux=aux->right;
                if(aux==NULL){
                    pai->right=novo;
                    return;
            } else {
                aux=aux->left;
                if(aux==NULL){
                    pai->left=novo;
                    return;
                }

            }
            }
        }
    }   
}

int main() {
    insert(9);
    insert(8);

    printf("[%p] -> (%p, %d, %p)\n",inicio,inicio->left,inicio->data,inicio->right);    

    return 0;
}

Fix up your formatting and you may find the problem. In particular, use consistent indentation. Your if/else blocks are not grouped the way you intended. — kaylum
– kaylum, Commented Nov 28, 2019 at 1:42
There's little merit to keeping this post open — the problem is very specific rather than usefully generic. Please delete it. — Jonathan Leffler
– Jonathan Leffler, Commented Nov 28, 2019 at 1:59
I'll observe that it is more normal to pass and return pointers to the root of the tree to an insert function — if only so you are not constrained to a single list as you are with inicio as the global variable that holds the pointer to the start of the list. — Jonathan Leffler
– Jonathan Leffler, Commented Nov 28, 2019 at 2:00

WhozCraig · Accepted Answer · 2019-11-28 04:25:43Z

1

to illustrate @kaylum point, here is the relevant part reformatted

while(1){
    pai = aux;
    if(n>pai->data){
        aux=aux->right;
        if(aux==NULL){
            pai->right=novo;
            return;
        } // end if(aux==NULL)
        else
        {  // else => aux != NULL
           aux=aux->left;
           if(aux==NULL){
               pai->left=novo;
               return;
           } // end if(aux==NULL)
        } // end else
    } // end if(n>pai->data)
} // end while

Please Note that else after return are pointless noise

while(1){
    pai = aux;
    if(n > pai->data){
        aux = aux->right;
        if(aux == NULL){
            pai->right = novo;
            return;
        }
        continue; // skip to next loop
    }
    // implying (n <= pai->data)
    aux = aux->left;
    if(aux == NULL){
        pai->left = novo;
        return;
    }
}

"Better" implementation would probably use pointer to pointer and reduce redundant code.

void insert(int n)
{
    Tree **pp = &inicio;

    while (*pp)
    {
        if ((*pp)->data < n)
            pp = &(*pp)->right;
        else
            pp = &(*pp)->left;
    }

    *pp = malloc(sizeof **pp);
    if (*pp)
    {
        (*pp)->data = n;
        (*pp)->left = (*pp)->right = NULL;
    }
}

edited Nov 28, 2019 at 4:25

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

answered Nov 28, 2019 at 1:59

dvhh

4,73829 silver badges34 bronze badges

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

3 Comments

dvhh Over a year ago

thanks for adding the "better" implementation @WhozCraig, but I wanted to leave the exercise to DaviAtella

WhozCraig Over a year ago

I understand. It is my experience if someone struggles with pointers, they're going to have nightmares with pointers to pointers. You're correct it's a much better implementation, and having both in the same answer allows future readers to see how both methods achieve the same result.

dvhh Over a year ago

Good point, but I would hate gaining reputation from your addition

Collectives™ on Stack Overflow

Insert function in C Binary Tree?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related