SO I just need to add a tree sort, but I have some error when run it, please help me to debug and add free binary function in free_btree(struct BTreeNode **node);
The description is in a picture, to run test tree sort using : ./sorting_program tree
https://imgur.com/c2NAyTC
This is my current output, the error https://imgur.com/a/VcC9XA9
////////////////////// your_functions.h
#ifndef YOUR_FUNCTIONS_H
#define YOUR_FUNCTIONS_H
//Students: Binary Tree structure that your functions will use to create a binary tree
struct BTreeNode
{
struct BTreeNode *leftchild;
struct BTreeNode *rightchild;
int data;
};
// Students: Add the required functions for tree sort here...
void inorder(struct BTreeNode *node, int *array);
void insert_element(struct BTreeNode **node, int element);
void tree_sort(int *array, int size);
void free_btree(struct BTreeNode **node);
void mergeSort(int *array_start, int *temp_array_start, int array_size);
void mergeSort_sort(int *array_start, int *temp_array_start, int left, int right);
void mergeSort_merge(int *array_start, int *temp_array_start, int left, int mid, int right);
#endif // YOUR_FUNCTIONS_H
///////////////////// your_functions.c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "function.h"
void inorder(struct BTreeNode *node,int *array)
{
//Recursive In-order traversal: leftchild, element, rightchild
if ( node != NULL )
{
inorder ( node -> leftchild, array) ;
**array = node -> data ;
++*array;
inorder ( node -> rightchild, array) ;
}
}
void insert_element(struct BTreeNode **node, int element)
{
if ( *node == NULL )
{
*node = malloc ( sizeof ( struct BTreeNode) ) ;
( *node ) -> leftchild = NULL ;
( *node ) -> data = element ;
( *node ) -> rightchild = NULL ;
}
else
{
if ( element < ( *node ) -> data )
insert_element ( &( ( *node ) -> leftchild ), element ) ;
else
insert_element ( &( ( *node ) -> rightchild ), element ) ;
}
}
void free_btree(struct BTreeNode **node)
{
// help me to add this
}
void tree_sort(int *array, int size)
{
//1. Construct the binary tree using elements in array
//2. Traverse the binary tree in-order and update the array
//3. Free the binary tree
struct BTreeNode *bt = NULL;
int i, *p = array;
for ( i = 0 ; i < size ; i++ )
insert_element ( &bt, array[i] ) ;
inorder ( bt, &p) ;
//deallocate tree
return array;
}
///////////////////helper_functions.c (h)
#ifndef HELPER_FUNCTIONS_H
#define HELPER_FUNCTIONS_H
void initArray(int *array_start, int array_size);
void bubbleSort(int *array_start, int array_size);
bool verifySort(int *array_start, int array_size);
#endif // HELPER_FUNCTIONS_H
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "helper_functions.h"
// Initialize array with random numbers in range from 0 to RAND_MAX
// Arguments:
// (1) Pointer to start of array
// (2) Number of elements in array
// Return value: None
void initArray(int *array_start, int array_size)
{
printf("Initializing %i elements in array...\n", array_size);
for(int i=0; i<array_size; i++)
{
array_start[i] = rand();
}
return;
}
// Bubble sort algorithm
// Arguments:
// (1) Pointer to start of array
// (2) Number of elements in array
// Return value: None
void bubbleSort(int *array_start, int array_size)
{
printf("Using bubble sort algorithm...\n");
int temp;
for (int i = (array_size - 1); i > 0; i--)
{
for (int j = 1; j <= i; j++)
{
if (array_start[j-1] > array_start[j])
{
temp = array_start[j-1];
array_start[j-1] = array_start[j];
array_start[j] = temp;
}
}
}
return;
}
// Test if array is sorted in ascending order
// Arguments:
// (1) Pointer to start of array
// (2) Number of elements in array
// Return value: True (if sorted), false otherwise
bool verifySort(int *array_start, int array_size)
{
printf("Verifying array sorting...\n");
if(array_size == 1)
return true; // Array with 1 element is always sorted
else if(array_size <= 0)
return false; // Invalid array
else
{
for(int i=1; i<array_size; i++)
{
// Starting from element 1 (not 0), compare with preceeding
if(array_start[i-1] > array_start[i])
return false; // Found 1 example out of order - stop searching
}
return true;
}
}
///////////////////////////////// sorting.c
// Compile this program:
// unix> make
// Run this program:
// unix> ./sorting_program bubble
// unix> ./sorting_program quick
// unix> ./sorting_program merge
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h> // Use bool as a datatype - requires newer C99 standard!
#include <string.h> // For string comparison
#include "helper_functions.h"
#include "your_functions.h"
#define ARRAY_SIZE 100000
int main(int argc, char *argv[])
{
int my_array[ARRAY_SIZE];
int *temp_array = NULL;
bool sorted = false;
if( argc != 2)
{
printf("Program usage: %s sortname\n", argv[0]);
return 1;
}
// Fill array with random numbers
initArray(my_array, ARRAY_SIZE);
// Sort array by chosen algorithm
if(strcmp(argv[1], "bubble") == 0)
bubbleSort(my_array, ARRAY_SIZE);
else if(strcmp(argv[1], "tree") == 0)
tree_sort(my_array,ARRAY_SIZE);
else if(strcmp(argv[1], "merge") == 0)
{
// Merge sort needs a second (temporary) array
// Dynamically allocate this
temp_array = calloc(ARRAY_SIZE, sizeof(int));
mergeSort(my_array, temp_array, ARRAY_SIZE);
free(temp_array); // Release dynamic memory after use
}
else
{
printf("Invalid sort algorithm. Must specifiy 'bubble', 'tree', or 'merge'\n");
return 1;
}
// Test if array is sorted correctly
sorted = verifySort(my_array, ARRAY_SIZE);
if(sorted)
printf("Congrats! Array is sorted correctly\n");
else
printf("*** Error: Array sort algorithm fails verification test ***\n");
return 0;
}
//////////////////// Makefile
# The variable CC specifies which compiler will be used.
# (because different unix systems may use different compilers)
CC=gcc
# The variable CFLAGS specifies compiler options
# -c : Only compile (don't link)
# -Wall: Enable all warnings about lazy / dangerous C programming
# -std=c99: Using newer C99 version of C programming language
CFLAGS=-c -Wall -std=c99
# All of the .h header files to use as dependencies
HEADERS=helper_functions.h your_functions.h
# All of the object files to produce as intermediary work
OBJECTS=sorting.o helper_functions.o your_functions.o
# The final program to build
EXECUTABLE=sorting_program
# --------------------------------------------
all: $(EXECUTABLE)
$(EXECUTABLE): $(OBJECTS)
$(CC) $(OBJECTS) -o $(EXECUTABLE)
%.o: %.c $(HEADERS)
$(CC) $(CFLAGS) -o $@ $<
clean:
rm -rf *.o $(EXECUTABLE)
