Program C accepts a branch, although it should not

Question

I wrote a C program that builds a binary search tree from an array. It performs the following steps:

1: Sorting an array c qsort().

2: Put the sorted array elements in a binary tree using a recursive function treeify():

2a: Take the middle element of the array (dividing its length by 2) and place it as a field in the contentstruct tree (the root of the node of this subtree).

2b: The function then copies the left and right halves of the remaining elements into smaller arrays and calls itself for each of these arrays, respectively.

2c: Return the tree through the root of the node.

3: recursively traverse the tree and print its contents indented.

Basically, I used the division and subjugation paradigm to build a tree from an already sorted array. Surprisingly (since this was my first D&C algorithm project), this part went pretty smoothly.

Where I really ran into difficulties was in the third step. Sometimes this works, and when this happens, all the elements are in the correct order, so the part obviously works. But 90% of the time I run the program, it segfaults when it gets to the first leaf node.

Here is the full text of the program. I changed the print function so that it prints the addresses of the nodes (for debugging purposes). It originally displayed numerical values ​​...

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

struct tree {
    int content;
    struct tree *left;
    struct tree *right;
};

struct tree *treeify( int *, size_t );
void printtree( struct tree *, int );
int comp( int *, int * );

int main( int argc, char **argv ){
    int array[] = { 5, 6, 7, 2, 3, 4, 9, 1, 8, 0 };
    /* Sort array */
    qsort( (void *) array, 10, sizeof( int ), (int (*)(const void *, const void *)) &comp );
    for( int i = 0; i < 10; i++ ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
    /* Treeify array */
    struct tree *rootnode = treeify( array, 10 );
    /* Print tree */
    printtree( rootnode, 0 );
    return 0;
}

// Place sorted array elements in a tree
// Function is called for each subtree
struct tree *treeify( int *array, size_t size ){
    struct tree *root = (struct tree *) malloc( sizeof( struct tree ) );
    size_t middle = size/2;
    int leftsize = middle, rightsize = size-middle-1;
    int left[leftsize], right[rightsize];
    for( int i = 0; i < leftsize; i++ ) left[i] = array[i];
    for( int i = 0; i < rightsize; i++ ) right[i] = array[i+middle+1];
    root->content = array[middle];
    if( leftsize > 0 ) root->left = treeify( left, leftsize );
    if( rightsize > 0 ) root->right = treeify( right, rightsize );
    return root;
}

// Print tree contents in indented format
void printtree( struct tree *node, int level ){
    for( int i = 0; i < level; i++ ) printf( "  " );
    printf( "%x\n", &(node->content) );
    if( node->left ) printtree( node->left, level+1 );
    if( node->right ) printtree( node->right, level+1 );
}

// Comparison function for qsort
int comp( int *xp, int *yp ){
    int x = *xp, y = *yp;
    if( x < y ) return -1;
    if( x > y ) return 1;
    return 0;
}

I managed to isolate the problem by typing the addresses of the nodes when traversing the tree. Here is the result of a successful launch:

0 1 2 3 4 5 6 7 8 9 
cbe00000
  cbe00020
    cbe00040
      cbe00060
    cbe00080
      cbe000a0
  cbe000c0
    cbe000e0
      cbe00100
    cbe00120

And an unsuccessful run:

f04032b0
  f04032d0
    f04032f0
      f0403310
        0   
Segmentation fault: 11

, . , .

, :

        if( node->left ) printtree( node->left, level+1 );

, , node->left ( ).

, . false ( ), - , ( , ).

. -, C, , .

, :

• -

Answer 1

, , , ,

if (node->left) 

printtree().

, - undefined, .

,

struct tree *create_node(int content)
{
    struct tree *node;
    node = malloc(sizeof(*node));
    if (node == NULL)
        return NULL;
    node->content = content;
    node->left = NULL;
    node->right = NULL;
    return node;
}

• malloc() , void * - .
• , malloc() NULL .

Answer 2

comp ​​

int comp( const void *, const void * );

-, treeify left right , leftsize rightsize 0.

.

struct tree * treeify( const int *array, size_t size )
{
    struct tree *node = NULL;

    if ( size )
    {
        node = malloc( sizeof( struct tree ) );
        size_t middle = size / 2;

        node->content = array[middle];

        node->left = treeify( array, middle );
        node->right = treeify( array + middle + 1, size - middle - 1 );
    }

    return node;
}

printtree( . , , NULL.

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

struct tree 
{
    int content;
    struct tree *left;
    struct tree *right;
};

int comp( const void *, const void * );
struct tree * treeify( const int *, size_t );
void printtree( const struct tree *, int level );

int main(void) 
{
    int array[] = { 5, 6, 7, 2, 3, 4, 9, 1, 8, 0 };
    const size_t N = sizeof( array ) / sizeof( *array );

    qsort( array, N, sizeof( *array ), comp );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", array[i] );
    putchar( '\n' );

    struct tree *rootnode = treeify( array, N );

    printtree( rootnode, 0 );

    return 0;
}

int comp( const void *left, const void *right )
{
    int x = *( const int * )left;
    int y = *( const int * )right;

    return ( y < x ) - ( x < y );
}

struct tree * treeify( const int *array, size_t size )
{
    struct tree *node = NULL;

    if ( size )
    {
        node = malloc( sizeof( struct tree ) );
        size_t middle = size / 2;

        node->content = array[middle];

        node->left = treeify( array, middle );
        node->right = treeify( array + middle + 1, size - middle - 1 );
    }

    return node;
}

void printtree( const struct tree *node, int level )
{
    if ( node )
    {
        printf( "%*s", level, "" );
        printf( "%d\n", node->content );
        if( node->left ) printtree( node->left, level + 1 );
        if( node->right ) printtree( node->right, level + 1 );
    }
}

0 1 2 3 4 5 6 7 8 9 
5
 2
  1
   0
  4
   3
 8
  7
   6
  9