My professor gave us an assignment to make a binary tree. We're given a file which we store in an array and then sort the numbers in the array least to greatest.
I have done all of that so far...
This requirement is confusing me however.
"After storing the integers, sort them. Then construct the binary tree using the following algorithm:
function balance(array, first_index, last_index):
if first_index <= last_index
{
middle_index = first_index + (last_index - first_index)/2
create node_pointer
store value at middle_index in node
left_child_of_node = balance(array, first_index, middle_index - 1)
right_child_of_node = balance(array, middle_index + 1, last_index)
return node_pointer
}
else
return NULL"
This function is adding the nodes to the binary tree and also balancing it at the same time if I'm not mistaken?
This is my implementation of the code but it is not working so far.
Code:
struct node* balance(int *array, int first_index, int last_index)
{
int middle_index;
if (first_index <= last_index)
{
middle_index = first_index + (last_index - first_index)/2;
struct node* temp;
temp = (node*) malloc( sizeof(struct node) );
temp->value = middle_index;
temp->left = balance(array, first_index, middle_index - 1);
temp->right = balance(array, middle_index + 1, last_index);
return temp;
}
else
return NULL;
}
here is all of my code so far (split into 2 c files and a header because of requirements).
Code:
#include <stdio.h>
#include <stdlib.h>
#include "bin-library.h"
int main(void)
{
struct node *root = NULL;
int *array_of_numbers;
int Max_lines = 0;
int i;
array_of_numbers = numbers(&Max_lines);
array_of_numbers = sort_array(array_of_numbers, Max_lines);
root = balance(array_of_numbers, array_of_numbers[0], array_of_numbers[Max_lines]);
getchar();
return 0;
}
next file is this...(skipping over the sorting and such)
Code:
#include "bin-library.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node* balance(int *array, int first_index, int last_index)
{
int middle_index;
if (first_index <= last_index)
{
middle_index = first_index + (last_index - first_index)/2;
struct node* temp;
temp = (node*) malloc( sizeof(struct node) );
temp->value = middle_index;
temp->left = balance(array, first_index, middle_index - 1);
temp->right = balance(array, middle_index + 1, last_index);
return temp;
}
else
return NULL;
}
And then the header simply has the function declartions and the structure of ...
Code:
struct node {
int value;
struct node *left;
struct node *right;
};
I'm not sure what I'm confused on exactly. Am I right on what I think his algorithm is? If so what am I doing wrong? If I'm not right on that, can someone explain to me where I'm not understanding it?
Thanks in advance