The following is my assignment on a programming course I'm working on:
Below is the code I've written so far. I've adjusted it to contain the integers in an array, without the need to read them in from another file, to be easily usable by you. Below it I will explain why it does not create the binary tree successfully, followed by my question. Here's the code:
/* A program that should use integers in an array to make binary trees
using the integers, then prints the integers from the tree inorder.
By John
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
} NODE;
typedef NODE *BTREE;
//allocate memory for the node
BTREE create_node(BTREE t)
{
t = (BTREE)malloc(sizeof(NODE));
return t;
}
//initialize the node
BTREE init_node(int number, BTREE p1, BTREE p2)
{
BTREE t = NULL;
t = create_node(t);
t->data = number;
if (p1->data <= t->data)
{
t->left = p1;
}
else if (p1->data > t->data)
{
t->right = p1;
}
if (p2->data <= t->data)
{
t->left = p2;
}
else if (p2->data > t->data)
{
t->right = p2;
}
return t;
}
//create the tree from the integers stored in the array
BTREE create_tree(int num_array[], int i, int size)
{
if (i >= size)
{
return NULL;
}
else
{
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
}
}
//printing the integers stored in the trees inorder
void print_inorder(BTREE t)
{
if (t != NULL)
{
print_inorder(t->left);
printf("%d :", t->data);
print_inorder(t->right);
}
}
int main(void)
{
BTREE t = NULL;
int data[] = { 9, 11, 4, 5 }; //pointer to integers array
int i = 0; //represents indexes of the integers array
int number = 0; //number of integers to be read into array
t = create_tree(data, i, number);
print_inorder(t);
free(t);
return 0;
}
I get a segmentation fault, because I have a bad (dangling?) pointer, to my understanding (and please correct me if I'm wrong). When init_node which is being returned by the create_tree function is finally called, the i value being passed to the init_node function is == 3 , which refers to the last integer in my num_array. Hence, in the init_node function, if(p1 -> data <= t -> data) is an invalid statement because p1 itself cannot exist, since it would've needed an int that's taken from the num_array, but I had already reached the end of the num_array before attempting to create p1, hence p1 is a bad / dangling pointer.
My problem is in the return value of the create_tree function:
BTREE create_tree(int num_array[], int i, int size)
{
if (i >= size)
{
return NULL;
}
else
{
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
}
}
The point of this:
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
is to create NODE p1 and NODE p2 to be used by the init_node function to create a tree, that assigns p1 to the left pointer and p2 to the right pointer. p1 should contain one integer, then p2 should contain the integer contained at the very next index in the num_array. What ended up happening was that when we get to the execution of create_tree(num_array, 2*i 1, size), it recurses, and with the recursions i takes the values 0, 1, 3, then i becomes == 7, hence NULL is returned to the create_tree function, and the i value passed to create_tree(num_array, 2*i 2, size) is already == 3, so the create_tree function in this case returns NULL, and then the init_node function starts executing.
What I wanted by the create_tree recursions in the returned init_node function, was to use the integer at index i == 0 of the num_array in create_tree(num_array, 2*i 1, size), then use the integer at index i == 1 in create_tree(num_array, 2*i 2, size), and for the init_node function to be called to create the trees, and then for the alternation between the first and second create_tree function calls to continue using i == 2 and i == 3 consecutively. How can I fix my code to make it do that?
(The professor teaching the course actually implemented the code the way I did it, meaning he wrote the create_tree function the way I did, except that he used a char array containing chars a, b, c, d, e instead of an int array containing ints, and somehow his program executed properly, and mines does not, which is also very confusing.)
Below is a snippet from my course, showing generally the same logic that I used, used by the professor for his init_node and create_tree functions. He then runs the compiled program and it works just fine, and I cannot understand how that worked for him.
Thank you for all your help!
CodePudding user response：
I see two key flaws in your sample code. The first is likely only in the sample and not your original:
int data[] = { 9, 11, 4, 5 }; //pointer to integers array
int i = 0; //represents indexes of the integers array
int number = 0; //number of integers to be read into array
t = create_tree(data, i, number);
The number variable needs to be set to the size of the array, so it's zero value will keep the code from doing much. But the real problem is the init_node() function.
In your professor's example, t->left and t-right are set unconditionally to the arguments p1 and p2, which might be NULL. but your code does some condtional tests like if (p1->data ... when p1 might be NULL. And similarly for p2. And, it might leave t->left and /or t->right unintialized. Let's redo the code, testing the validity of our pointers:
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
} NODE;
typedef NODE *BTREE;
BTREE create_node(void)
{
BTREE t = malloc(sizeof(NODE));
if (t == NULL)
{
perror("NODE can't be allocated!");
exit(EXIT_FAILURE);
}
return t;
}
BTREE init_node(int number, BTREE p1, BTREE p2)
{
BTREE t = create_node();
t->data = number;
t->left = NULL;
t->right = NULL;
if (p1 != NULL)
{
if (p1->data <= t->data)
{
t->left = p1;
}
else
{
t->right = p1;
}
}
if (p2 != NULL)
{
if (p2->data <= t->data)
{
t->left = p2;
}
else
{
t->right = p2;
}
}
return t;
}
BTREE create_tree(int num_array[], unsigned i, size_t size)
{
if (i >= size)
{
return NULL;
}
return init_node(num_array[i], create_tree(num_array, 2*i 1, size), create_tree(num_array, 2*i 2, size));
}
void print_inorder(BTREE t)
{
if (t != NULL)
{
printf("(");
print_inorder(t->left);
printf(" %d ", t->data);
print_inorder(t->right);
printf(")");
}
}
int main(void)
{
BTREE t = NULL;
int data[] = { 9, 11, 4, 5 }; // pointer to integers array
size_t number = sizeof(data)/sizeof(*data); // number of integers to be read into array
t = create_tree(data, 0, number);
print_inorder(t);
printf("\n");
return EXIT_SUCCESS;
}