Creating and printing binary tree from array

Question

I am trying to create a binary tree with the array as defined in my function.

I then then want to print its elements in inorder fashion (root, left, right)

The following code compiles but gives no input (NULL)

Please tell me where am I going wrong

struct BST{
    int data;
    struct BST *left;
    struct BST *right;
};

struct BST *in(int data, struct BST *p1, struct BST *p2);
struct BST *create_BST(int a[], int i, int size);
void inorder(struct BST *tree);
int  main(void){
    struct BST *root;
    int a[]={7, 10, 14, 5, 9, 11, 4, 13, 6};


    root=create_BST(a,0,9);

    printf("\nPrinting Tree:\t");
    inorder(root);
    return 0;

}
void inorder(struct BST *root){
    if(root!=NULL){
        inorder(root->left);
        printf("%d",root->data);
        inorder(root->right);
    }
}

struct BST *in(int data, struct BST *p1, struct BST *p2){
    struct BST *t;
    t=(struct BST*)malloc(sizeof(struct BST));
    t->data=data;
    t->left=p1;
    t->left=p2;
    return t;
}

struct BST *create_BST(int a[], int i, int size){

    if(i>=size){
        return NULL;
    }else{
        return(in(a[i],create_BST(a,2*i + 1,size),
            create_BST(a,2*i + 2,size)));
    }

}

You print elements with printf("%c", root->data); but this prints characters; small integers print as funky characters. You probably mean %d to print the numbers. Recommend adding a space before as well: printf(" %d", root->data); — Steve Friedl
– Steve Friedl, Commented Nov 25, 2019 at 0:24
@SteveFriedl thank you, but after having changed that, I am getting Printing Tree: 4147 in output, which is wrong — chesslad
– chesslad, Commented Nov 25, 2019 at 0:33
What are 2*i + 1 and 2*i + 2 doing? {1,2}, {3,4}, {7,8}?? Possible Duplicate Inserting elements in a BST — David C. Rankin
– David C. Rankin, Commented Nov 25, 2019 at 0:37
@DavidRankin-ReinstateMonica a[2*i+1] and a[2*i +2] become left and right child of a[i] — chesslad
– chesslad, Commented Nov 25, 2019 at 0:46

Kingsley · Accepted Answer · 2019-11-25 00:54:24Z

The create_BST() function is not correct. For starters, it's only inserting a single value into the tree. But there's a couple of other bugs too.

struct BST *in(int data, struct BST *p1, struct BST *p2){
    struct BST *t;
    t=(struct BST*)malloc(sizeof(struct BST));
    t->data=data;
    t->left=p1;
    t->left=p2;    // <-- HERE, should be t->right=p2;
    return t;
}

Ah, you already corrected the %c bug @SteveFriedl pointed out.

I modified the creation process to walk the tree, looking for the correct insertion point on a leaf-node.

struct BST *insert( struct BST *root, int value )
{
    if ( root == NULL )
    {
        // Tree is empty, make it
        root = in( value, NULL, NULL );
        printf( "Inserted %d at the root (%p)\n", value, root );
    }
    else
    {
        // Find the location to insert the node
        int  inserted = 0;
        struct BST *ptr = root;

        // Keep walking the tree until we're inserted
        while ( !inserted )
        {
            // Does it hang off the left?
            if ( value <= ptr->data )
            {
                if ( ptr->left == NULL )
                {
                    ptr->left = in( value, NULL, NULL );
                    printf( "Inserted %d as a left-branch of %d(%p)\n", value, ptr->data, ptr );
                    inserted = 1;
                }
                else
                {
                    // branch left, cannot make a leaf here
                    ptr = ptr->left;
                }
            }
            else  // Hangs off the right  ( value > ptr->data )
            {
                if ( ptr->right == NULL )
                {
                    ptr->right = in( value, NULL, NULL );
                    printf( "Inserted %d as a right-branch of %d(%p)\n", value, ptr->data, ptr );
                    inserted = 1;
                }
                else
                {
                    // branch right, cannot make a leaf here
                    ptr = ptr->right;
                }
            }
        }
    }

    return root;
}

And then simply iterate over your array of values, inserting each in-turn into the tree.

struct BST *create_BST(int *values, int count)
{
    struct BST *tree = NULL;

    if ( values != NULL && count > 0 )
    {
        for( int i=0; i<count; i++ )
            tree = insert( tree, values[ i ] );
    }

    return tree;
}

Obviously your main() needs to call:

root=create_BST(a,9);

This gives me:

$ ./bst
Inserted 7 at the root (0x5568b65f32a0)
Inserted 10 as a right-branch of 7(0x5568b65f32a0)
Inserted 14 as a right-branch of 10(0x5568b65f36d0)
Inserted 5 as a left-branch of 7(0x5568b65f32a0)
Inserted 9 as a left-branch of 10(0x5568b65f36d0)
Inserted 11 as a left-branch of 14(0x5568b65f36f0)
Inserted 4 as a left-branch of 5(0x5568b65f3710)
Inserted 13 as a right-branch of 11(0x5568b65f3750)
Inserted 6 as a right-branch of 5(0x5568b65f3710)

Printing Tree:  4 5 6 7 9 10 11 13 14

The inorder() function is obviously fine.

Collectives™ on Stack Overflow

Creating and printing binary tree from array

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related