CODEWITHSUNDEEP
carraystreebinary-treepreorder
Isak
Isak

Reputation: 115

Convert binary tree to array in c

I want to convert a binary tree to an array using C. I tried but was unsuccessful.

My binary tree contains the following elements (preorder)

4 3 5 10 8 7

but my array contains (after sorting)

4 4 5 7 8 10

Any help would be greatly appreciated. My current code look like this:

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

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

int AddToArray(tree *node, int arr[], int i);
tree *CreateNode(int data);
tree *Insert(tree *node, int data);
void PrintPreorder(tree *node);
int count(tree *node);
int compare(const void * a, const void * b);

//---------------------------------------------------------------------------
int main()
{
    int i;
    int size;
    int *arr=NULL;
    tree *root=NULL;

    printf("***TEST PROGRAM***\n");
    root = Insert(root, 4);
    root = Insert(root, 3);
    root = Insert(root, 5);
    root = Insert(root, 10);
    root = Insert (root, 8);
    root = Insert (root, 7);
    size = count(root);

    printf("\n***BINARY TREE (PREORDER)***\n");
    PrintPreorder(root);
    printf("\nThe binary tree countain %d nodes", size);

    printf("\n\n***ARRAY***\n");
    arr = calloc(size, sizeof(int));
    AddToArray(root, arr, 0);
    qsort(arr,size,sizeof(int),compare);

    for (i=0; i<size; i++)
    {
        printf("arr[%d]: %d\n", i, arr[i]);
    }
}
//---------------------------------------------------------------------------

int compare(const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int AddToArray(tree *node, int arr[], int i)
{
    if(node == NULL)
        return i;
     arr[i] = node->data;
     i++;
     if(node->left != NULL)
          AddToArray(node->left, arr, i);
     if(node->right != NULL)
          AddToArray(node->right, arr, i);

     arr[i] = node->data;
     i++;
}

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

tree *Insert(tree *node, int data)
{
    if(node==NULL)
    {
        tree *temp;
        temp = CreateNode(data);
        return temp;
    }

    if(data >(node->data))
    {
        node->right = Insert(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = Insert(node->left,data);
    }

    /* Else there is nothing to do as the data is already in the tree. */
    return node;
}

void PrintPreorder(tree *node)
{
    if(node==NULL)
    {
        return;
    }
    printf("%d ",node->data);
    PrintPreorder(node->left);
    PrintPreorder(node->right);
}

int count(tree *node)
{
    int c = 1;

    if (node == NULL)
        return 0;
    else
    {
        c += count(node->left);
        c += count(node->right);
        return c;
     }
}

Upvotes: 2

Views: 37662

Answers (4)

josef
josef

Reputation: 1

int TreeToArray (struct node *tree, int *arr, int i)

{
    if (tree == NULL) return i;

    if (tree->left != NULL) i = TreeToArray(tree->left, arr, i);
    arr[i] = tree->Value;
    i++;
    if (tree->right != NULL) i = TreeToArray(tree->right, arr, i);

    return i;
}

Upvotes: -2

BLUEPIXY
BLUEPIXY

Reputation: 40145

Cause that i is not treated in a unified manner.

AddToArray replace with 

void AddToArray(tree *node, int arr[], int *i){
    if(node == NULL)
        return ;

    arr[*i] = node->data;
    ++*i;
    AddToArray(node->left, arr, i);
    AddToArray(node->right, arr, i);
}

and call i=0; AddToArray(root, arr, &i); at main.

Upvotes: 4

Stewart Grant
Stewart Grant

Reputation: 79

The two lines of code int AddToArray

 arr[i] = node->data;
 i++;

Are appearing twice at each level of recursion. My guess is that every value in the tree is being written to the array twice and they over lap each other. but the root is the final value to be written twice so it is the only noticeable one.

Just remove the duplicate call at the bottom of the function.

Upvotes: -1

Daniel Kleinstein
Daniel Kleinstein

Reputation: 5502

Change your AddToArray method to this:

int AddToArray(tree *node, int arr[], int i)
{
     if(node == NULL)
          return i;


     arr[i] = node->data;
     i++;
     if(node->left != NULL)
          i = AddToArray(node->left, arr, i);
     if(node->right != NULL)
          i = AddToArray(node->right, arr, i);

     return i;
}

What was happening was that your recursive calls were changing the value of i (the index where you were supposed to insert the following element), but your recursion wasn't changing the value of i in the iteration that actually invoked the recursion. Updating i with the value returned by AddToArray fixes this.

Upvotes: 10

Related Questions