Converting an array into binary tree using C?

Question

I am trying to convert an integer array into a binary tree using C.

For example for an array a[10]={5,2,1,6,7,3,4} , the Binary tree should look like

I tried to convert using the following code

typedef struct btree    
{        
    int value;    
    struct btree *left;    
    struct btree *right;    
}Btree;    
void insert(Btree *t,int *a,int index,int n)    
{    
    t=(Btree *)malloc(sizeof(Btree));    
    if(index<n)    
    {    
        t->value=a[index];    
        insert(t->left,a,2*index,n);    
        insert(t->right,a,2*index+1,n);    
    }    
}    
int main(void) {    
    int a[100],i;    
    Btree *t;    
    for(i=0;i<10;i++)    
        scanf("%d",&a[i]);    
    insert(t,a,0,i+1);    
    return 0;    
}

Can someone help me out with this problem?

ggorlen · Accepted Answer · 2021-07-01 16:35:26Z

There are several issues here:

Your node allocation should go inside the conditional block in insert, otherwise you allocate memory for null nodes.
You should initialise the left and right pointers to NULL in case the node is a leaf node and has no children.
Most important. Your changes to the tree are lost. The pointer variables are local to the current instance of insert (which you call recursively) and don't transfer to earlier instances or to main. Pass a pointer to the node pointer.
Consider using zero-base indices throughout; they are standard in C.

So, here's how it should work:

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

typedef struct btree {
    int value;
    struct btree *left;
    struct btree *right;
} Btree;

void insert(Btree **t, int *a, int index, int n)
{
    if (index < n) {
        *t = malloc(sizeof(**t));
        
        (*t)->value = a[index];
        (*t)->left = NULL;
        (*t)->right = NULL;
        
        insert(&(*t)->left, a, 2 * index + 1, n);
        insert(&(*t)->right, a, 2 * index + 2, n);
    }
}

void print(Btree *t, int level)
{
    if (t) {
        print(t->left, level + 1);
        printf("%*s->%d\n", 4*level, "", t->value);
        print(t->right, level + 1);
    }
}

int main(void)
{
    int a[] = {5, 2, 1, 6, 7, 3, 4};
    Btree *t;

    insert(&t, a, 0, 7);
    print(t, 0);

    // TODO: Clean up memory used by nodes

    return 0;
}

(I've replaced the scanf stuff with a hard-coded array. The code does not clean up the allocated memory, which it really should.)

Kavindu Dodanduwa · Accepted Answer · 2015-03-06 06:15:09Z

0

May be you simply need to output the array to match with a tree like view. And in that case you would not need to make a binary tree with nodes but simply use the array with proper indexing.

If your current index is X childs become 2X+1 and 2X+2 . May be this is what you actually wants.

See the example :

#include <stdio.h>

int main()
{

    int a[7]={5,2,1,6,7,3,4}; // <= A hard coded array

    int n=0;

    // Getting the unsorted Tree output. 
    //  sizeof(a)/sizeof(int) - used to get the array length

    while(n < (sizeof(a)/sizeof(int))/2){
        printf("Parent: %d\n",a[n]);  // <= parent node
        printf("Left Child: %d\n",a[2*n +1]); // <= left Child
        printf("Right Child: %d\n",a[2*n +2]); // <= right Child

        printf("\n");
        n++;
    }

    return 0;
}

Output :

Parent: 5                                                                                                                                                            
Left Child: 2                                                                                                                                                        
Right Child: 1                                                                                                                                                       

Parent: 2                                                                                                                                                            
Left Child: 6                                                                                                                                                        
Right Child: 7                                                                                                                                                       

Parent: 1                                                                                                                                                            
Left Child: 3                                                                                                                                                        
Right Child: 4

answered Mar 6, 2015 at 6:15

Kavindu Dodanduwa

13.2k4 gold badges38 silver badges49 bronze badges

3 Comments

vineeth suhas Over a year ago

what if i wanted to print the inorder traversal of the tree formed by the array.Is it possible to print it without using the binary tree?

Kavindu Dodanduwa Over a year ago

Yes,, nothing need to be done,, if the tree is sorted simply print the array :) simple as that.. But I provided the solution just to say it's possible to represent a binary tree with array,, but learning with nodes is good for the knowledge :) (see here, methods of storing binary tree section : en.wikipedia.org/wiki/Binary_tree)

vineeth suhas Over a year ago

Actually the tree is not sorted,the tree is formed from the array which is given as is explained in the question.I need to print the array in inorder manner i.e.,inorder of given array is {6,2,7,5,3,1,4}.I have tried printing it without forming the tree.But i am not able to get the idea of how to do it.Can you please provide me the code of it?

Collectives™ on Stack Overflow

Converting an array into binary tree using C?

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related