How to insert elements in binary tree from array in C?-CodePudding

I think the index variable, used to traverse the array containing the node values, should be a global one but C doesn't let me. The left node is working fine but the right node also shows the same value as the left one. In the array containing the values, -1 represent a null node and I used pre-order (root->left->right) to build the tree:

#include<stdio.h>
#include<stdlib.h>
typedef struct no{
    int data;
    struct no * left;
    struct no * right;
}node;
node* building_node(int);
node* building_binary_tree(int*,int,node*);
int main()
{
    system("clear||cls");
    int a[]={4,2,9,-1,-1,8,-1,-1,7,-1,-1};
    node*root=NULL;
    root=building_binary_tree(a, -1,root);
    printf("The Binary Tree Has:\n\n");
    printf("root = %d \n",root->data);
    printf("root->left = %d \n",root->left->data);
    printf("root->right = %d \n",root->right->data);
    // printf("%d ",root->left->left->data);
    // printf("%d ",root->left->right->data);
}
 
node * building_node(int data)
{
    //for building an empty node with data
    node* newnode=(node*)calloc(1,sizeof(node));
    newnode->data=data;
    newnode->right=NULL;
    newnode->left=NULL;
    return newnode;
}

node* building_binary_tree(int* a,int index,node* root)
{  
    //for building the tree recursively
    index  ;
    if(a[index]==-1) return NULL;
    root=building_node(a[index]);
    root->left=building_binary_tree(a,index,root->left);
    root->right=building_binary_tree(a,index,root->right);
    return root;
}

CodePudding user response：

It's pretty normal to have a different signature for the root node build_tree() than the remaining nodes build_subtree(). In this case we want to hide the implementation detail on how we advance through the array.

You can use index like you did, but you need to caller how far you get. This means a pointer to your index (*index). I elected to instead pass the address of the pointer to the array itself (**a). Then we just build the current node and recursive build the left and right subtrees.

As a bonus (and to ease debugging) I added a print_tree() so we can inspect the whole tree not just the root and it's 2 children.

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

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} node;

node * build_node(int data) {
    node* n = malloc(sizeof *n);
    n->data = data;
    n->right = NULL;
    n->left = NULL;
    return n;
}

node *build_subtree(int **a) {
    if(**a == -1) return NULL;
    node *n = build_node(**a);
    (*a)  ;
    n->left = build_subtree(a);
    (*a)  ;
    n->right = build_subtree(a);
    return n;
}

node *build_tree(int *a) {
    return build_subtree(&a);
}

void print_subtree(node *n, size_t level) {
    if(!n) return;
    level  ;
    print_subtree(n->right, level);
    for(int i = 0; i < 3 * (level - 1); i  )
        printf("%c", ' ');
    printf("%d <\n", n->data);
    print_subtree(n->left, level);
}

void print_tree(node *n) {
    print_subtree(n, 0);
}

int main() {
    node *root = build_tree(
       (int []) {4, 2, 9, -1, -1, 8, -1, -1, 7, -1, -1}
    );
    print_tree(root);
}

and the output is (your picture rotated 90 degrees counter clock wise):