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
5
/ \
2 1
/\ /\
6 7 3 4
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?
There are several issues here:
insert
, otherwise you allocate memory for null nodes.left
and right
pointers to NULL
in case the node is a leaf node and has no children.insert
(which you call recursively) and don't transcend to earlier instances or to main
. Pass a pointer to the node pointer.So, here's how it should work:
#include <stdlib.h>
#include <stdio.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.)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments