Im trying to create a recursive function that creates an array of post order integers from a given tree. This is the code:
//structure
typedef struct node
{
// Each node holds a single integer.
int data;
// Pointers to the node's left and right children.
struct node *left, *right;
} node;
// preorder_recursive is same as postorder_recursive(), except
// array[i] comes before the recursive calls
int *postorder_recursive(node *root)
{
int *array = malloc(sizeof(node) * node_count(root)); // node_count(root) counts nodes in binary tree
int i = 0;
if (root == NULL)
return 0;
while (root != NULL)
{
postorder_recursive(root->left);
postorder_recursive(root->right);
array[i] = root->data;
i++;
}
return array;
}
// returns 1 if pre order = post order, returns 0 otherwise
int compare(node *a, node *b)
{
int i = 0;
int *preArray, *postArray;
if (node_count(a) != node_count(b))
return 0;
preArray = preorder_recursive(a);
postArray = postorder_recursive(b);
for (i = 0; i < node_count(a); i++)
{
if (preArray[i] != postArray[i])
return 0;
}
free(preArray);
free(postArray);
return 1;
}
I am not entirely sure if the error is in this function, but if it is, it's probably due to the while loop. Any help would be great.
Edit: Ive included a lot more code. The purpose of this is to compare an array of post order to an array of pre-order.
Your function postorder_recursive()
is creating a new array every time it is called. Furthermore, while(root != NULL)
will loop forever for non-empty trees, if it weren't for the fact that it writes past the end of array
and cause a segmentation fault at some point.
The solution is to split the function into one that creates the array, and then another function that recursively fills in the array, like so:
static size_t postorder_recursive(const node *root, int *array, size_t index) {
if (root == NULL)
return index;
index = postorder_recursive(root->left, array, index);
index = postorder_recursive(root->right, array, index);
array[index++] = root->data;
return index;
}
int *postorder_to_array(const node *root)
{
int *array = malloc(sizeof(node) * node_count(root));
postorder_recursive(root, array, 0);
return array;
}