Store tree structured data to an array in C

user_9868042 0
Viewed 65

I am trying to write a code to transverse a tree data structure using inorder transversal and store all the nodes onto an array.

I came up with this code below but it doesn't work, as the index of any previous recursion has already been passed on in the function.

int *inorderTransversal(AVLTreeNode *node, AVLTreeNode *array[], int index)
{
    if (node == NULL)
        return index;

    inorderTransversal(node->left, array, index);
    nodesArray[index] = node;
    index++;
    inorderTransversal(node->right, array, index);
    return index; 
}

I know I could possibly declare a static 'index' value inside the function, and it might work? But the downside is it makes 'index' stays in the memory for the entire duration of the program e.g.

void *inorderTransversal(AVLTreeNode *node, AVLTreeNode *array[])
{
    static int index = 0;
    if (node == NULL)
        return;

    inorderTransversal(node->left, array);
    nodesArray[index] = node;
    index++;
    inorderTransversal(node->right, array);
    return; 
}

Or I could declare the index outside the function prior? e.g.

AVLTreeNode *array[tree->size]; 
int index = 0; 

void *inorderTransversal(AVLTreeNode *node) { 
    if (node == null) 
        return; 

    inorderTransversal(node->left); 
    array[index] = node; 
    index++;
    inorderTransversal(node->right); 
}

Could someone help me to amend the code to include the 'index' increments inside the function without using static? Much appreciated!

tree pointers data-structures c
1 Answers

Your first attempt was close. You want to pass in index as an int *. Then you can dereference it and update it.

void inorderTransversal(AVLTreeNode *node, AVLTreeNode *array[], int *index)
{
    if (node == NULL)
        return;

    inorderTransversal(node->left, treeSize, index);
    nodesArray[*index] = node;
    (*index)++;
    inorderTransversal(node->right, treeSize, index);
}

When you call this function, you pass the address of an int which has been initialized to 0. When the recursion ends it will hold the number of elements in the list.

user_16871190
Related