I forgot about this post. I have got it to work. This is what I used:
For the header file:
///\file Header.h
///\brief The header containing all the prototypes for our functions.
struct node *Create_node( int value );
void delete_value(struct node **root, int val_del) ;
void inorder_traversal( struct node *node );
void insert_value( struct node **head, int new_value );
void pre_order_traversal( struct node* node );
struct node* search_by_value(struct node* node, int value);
int random_value_generator(int domain);
For the implementation of the functions:
///\file Functions.c
///\brief C library implementation for BST.
#include <stdio.h>
#include <stdlib.h>
#include "Header.h"
//In this structure we'll be storing our BST.
struct node{
///\struct struct node
///\brief It represents our structure to store our BST.
int data;
struct node *left;
struct node *right;
};
/*-----------------------------------------------------------------------------------------------------*/
/*
Helper function which creates a new node, containing the desired value and setting left and right
pointers to NULL.
*/
struct node *Create_node( int value )
{
///\fn struct node *Create_node(int value)
///\brief Returns a new node, initialised with "value" and 2 NULL pointers, left and right.
///\param value The value which we want to initiliase the newly created node with.
//Creating the new Node and allocating memory to it.
struct node *new_node = (struct node*)malloc(sizeof(struct node));
//Assigning the desired value to the newly created node.
new_node->data = value;
//Setting left and right pointers to NULL;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
};
/*-----------------------------------------------------------------------------------------------------*/
/*
The first traversal method.
*/
void pre_order_traversal( struct node* node )
{
///\fn pre_order_traversal(struct node* node)
///\brief A function used to 'traverse' the tree. It actually is a printing function.
///\param node It represents the starting point of printing.
//Checking if the tree is not empty.
if( node != NULL ) {
///It will print the root, then the left child, then the right child.
//Printing the node.
printf( "%d ",node->data );
//Printing the left child.
pre_order_traversal( node->left );
//Printing the right child.
pre_order_traversal( node->right );
}
}
/*-----------------------------------------------------------------------------------------------------*/
/*
A function which inserts a new node in the tree.
*/
void insert_value( struct node **head, int new_value )
{
///\fn insert_value(struct node **head, int new_value)
///\brief Inserts a new node into our BST.
///\param head This parameter is passed as a double pointer to avoid any conflicts with other fucntions.
/// and represents the starting point of insertion. The function will start searching for the appropriate
/// position to insert the value.
///\param new_value Is the new value which will be assigned to the new node;
//Initialising the pointer.
struct node *current = *head;
//Checking if the the current node is NULL, if it is, we create a new node.
if( current == NULL){
//If the root is NULL, then we create a new new node, containing the new value.
current = Create_node( new_value );
*head = current;
}else{
//Else, if the value is smaller, recur to the left.
if( new_value < current->data ){
insert_value( ¤t->left, new_value );
}else{
//Else recur to the right.
insert_value( ¤t->right, new_value );
}
}
}
/*-----------------------------------------------------------------------------------------------------*/
/*
The second traversal method.
*/
void inorder_traversal( struct node *node )
{
///\fn inorder_traversal(struct node* node)
///\brief A function used to 'traverse' the tree. It actually is the second printing function.
///\param node It represents the starting point of printing.
if( node != NULL ) {
///It will print the left child, then the root, then the right child.
//Printing the left child.
inorder_traversal( node->left );
//Printing the root.
printf( "%d ",node->data );
//Printing the right child.
inorder_traversal( node->right );
}
}
/*-----------------------------------------------------------------------------------------------------*/
/*
A function which deletes a node.
*/
void delete_value(struct node **root, int val_del)
{
///\fn void delete_value(struct node **root, int val_del)
///\brief It is the most complex function and it is used to delete a node.
/// There are multiple cases of deletion, such as: a leaf node (a node without any children),
/// a node with a child on the right, a node with a child on the left or a node with 2 children.
//We are starting from root, with two pointers: current and parent.
struct node *current = *root;
struct node *parent;
//We recur on the tree untill we find the node containing the value which we want to remove.
while (current->data != val_del) {
//Moving the parent to root. The root's parent is NULL. (root has no parent)
parent = current;
//If the value is greater the parent's value, recur right.
if (current->data > val_del) {
current = current->left;
}else{
//Else recur left.
current = current->right;
}
}
//Checking if the node is a leaf node. (no children on the left or right)
if ((current->left == NULL) && (current->right == NULL)) {
//Comparing the node's value with the value of its parent.
//If the value is smaller, we remove the left children.
if (current->data < parent->data) {
parent->left = NULL;
}else{
//Else we remove the right child.
parent->right = NULL;
}
free(current);
//Else, we check if it has a child on the left.
}else if (current->right == NULL) {
//Checking if our node is the root.
if(current == *root) {
//Using an aux to free the root, so the memory is not allocated to it anymore .
struct node *aux;
aux = (*root)->left;
free(*root);
(*root) = aux;
//If the node is not the root, we proceed.
}else{
//If the node's parent value is greater the the value of our node. If true, we replace
//the parent's left child with its left succesor and remove (free) the node.
if (current->data < parent->data) {
parent->left = current->left;
free(current);
}else{
//Else, we do the same thing, but for the parent's right child.
parent->right = current->left;
free(current);
}
}
//Else, we check if it has a child on the right.
}else if(current->left == NULL) {
//Checking if our node is the root.
if(current == *root) {
//Using an aux to free the root, so the memory is not allocated to it anymore.
struct node *aux;
aux = (*root)->right;
free(*root);
*root = aux;
//If the node is not the root, we proceed.
}else {
if (current->data < parent->data){
//If the node's parent value is smaller the the value of our node. If true, we replace
//the parent's left child with its right succesor and remove (free) the node.
//It is the mirrored code of the previous case.
parent->left = current->right;
free(current);
}else{
//Else, we do the same thing, but for the parent's right child.
parent->right = current->right;
free(current);
}
}
//Else, the node has 2 children. This is the last case.
}else if( (current->right != NULL) && (current->left != NULL)){
//In order to replace the root, we need to go one step to the right,
//and then all the way to the left, retrieve the smallest value,
//which will replace the root.
struct node *temp = current->right;
int aux;
while (temp->left != NULL) {
temp = temp->left;
}
//This si where we do the swap.
aux = temp->data;
current->data = aux;
temp = temp->right;
}
}
/*-----------------------------------------------------------------------------------------------------*/
/*
Helper function to determine if a value already exists in the tree.
*/
struct node* search_by_value(struct node* node, int value)
{
///\fn struct node* search_by_value(struct node* node, int value)
///\brief It is a function used to check if an element already exists in the tree.
/// If the fucntion returns NULL, it means that the element DOESN'T belong to the tree.
//Checking if the current node is empty or it has the value which we are looking for.
if (node == NULL || node->data == value){
return node;
free(node);
}
//If the value is greater, recur right.
if( value > node->data ){
return search_by_value(node->right, value);
}else{
//Else recur left.
return search_by_value(node->left, value);
}
//Returning NULL if the element wasn't found.
return NULL;
}
/*-----------------------------------------------------------------------------------------------------*/
/*
A simple function to generate random numbers,
between 0 and a domain.
*/
int random_value_generator(int domain)
{
///\fn int random_value_generator(int domain)
///\brief It generates random numbers between 0 and a set domain.
///\param domain It represents the dmain.(the upper boundry for our generation)
return rand()%domain;
}
And finally the the main file:
///\file main.c
///\brief The driver program for our BST library, containing a command line.
#include <stdio.h>
#include <stdlib.h>
#include "Header.h"
//Setting the root to NULL.(empty tree)
struct node *root=NULL;
int main()
{
//Preparing the command line. The choice is like a task selector.
int choice;
//Infinitely recuring until the user decides to exit or there is an error.
do{
//Printing the command line and acquiring the choice.
printf("\nWhat would you like to do ? Select:");
printf("\n1-Add value;\n2-Delete value;\n3-Print In-Order;\n4-Print Pre-Order;\n5-Random;\n6-Exit;");
printf("\n");
printf("\nYour choice:");
scanf("%d",&choice);
switch(choice){
//The first case is used for insertion of a new value.
case 1:{
//Initialising the local values.
int iterations=0,number=0,value=0,iterator=0;
//Setting up a pointer, for later use.
struct node *ptr;
//Acquiring the number of iterations.
printf("\nHow many values would you like to insert? Type a value:");
scanf("%d",&iterations);
//Inserting values as many times as we initiliased "iterations".
while( number < iterations ){
printf("\nValue[%d]=",iterator);
scanf("%d",&value);
//Using the pointer to check if the value already exists.
ptr = search_by_value( root, value );
if( ptr == NULL ){
//In case of ptr = NULL, we add it to the BST.
insert_value(&root,value);
value = 0;
}else{
//Else we ask for another value, without affectig the number of iterations.
printf("\nThe element %d already exists in the tree!",value);
//Resetting the pointer and the vaue to be reused.
value = 0;
ptr = NULL;
//A simple way to keep the loop consistent.
//If we want to insert 10 values and 1 would already exists,
//we would only have 9 values. This way, even if there a values
//already exists, we will still have to insert the appropriate
//nuber of values.
number--;
iterator--;
}
//Incrementing the iterators to prevent an ifinite loop.
number++;
iterator++;
}
//Reseting the iterator to be used later.
iterator=0;
break;
};//end case-1
//The second case is used for deletion.
case 2:{
//Initialising the value.
int d_value=0;
//Acquiering the value we want to delete.
printf("\nWhich value would you like to delete? \nType a value:");
scanf("%d",&d_value);
//Checking if the value exists in the tree.
struct node *ptr = search_by_value( root, d_value );
if( ptr != NULL ){
//If ptr != NULL, it means that the value exists in the tree
// and it can be deleted.
printf("\nDeleting %d !",d_value);
//Deleting the value.
delete_value(&root, d_value);
//Reseting the value for laer use
d_value = 0;
}else if( ptr == NULL ){
//Else the value does not belong to the tree, so it cannot be deleted.
printf("\nThe element %d doesn't belong to the tree!",d_value);
printf("\n");
//Resetting the pointer and the value for later use.
d_value = 0;
ptr = NULL;
}else{
//Else our tree is empty.
printf("\nEmpty Tree!");
}
break;
};//end case-2
//The third case is used for in-order traversal.
case 3:{
printf("\nIn-order traversal:");
inorder_traversal(root);
printf("\n");
break;
};//end case-3
//The fourth case is used for pre-order traversal.
case 4:{
printf("\nPre-order traversal:");
pre_order_traversal(root);
printf("\n");
break;
};//end case-4
//The fifth case is used for randomly inserting value into teh BST.
case 5:{
//Initialising the values.
int iterations=0,number=0,value=0,iterator=0,domain=0;
//Setting up a pointer for later use.
struct node *ptr;
//Acquiering the number of iterations.
printf("\nHow many values would you like to insert? Type a value:");
scanf("%d",&iterations);
//Acquiering the domain for the random generator.
printf("\nPlease type the domain for the randomly generated numbers.");
printf("\nPlease type a value:");
scanf("%d",&domain);
//Iterating until all the values have been successfully inserted.
while( number < iterations ){
//The new value to be inserted is generated using our fucntion.
value = random_value_generator(domain);
//Checking if the values already exists in the tree.
ptr = search_by_value( root, value );
if( ptr == NULL ){
printf("\nInserting %d!",value);
//If ptr = NULL, we can safely insert the value into our BST.
insert_value(&root,value);
//Resetting the value for later use.
value = 0;
}else{
//Else, we cannot insert the value, as it already exists.
printf("\nThe element %d already exists in the tree!",value);
//Resetting the pointer and the value.
value = 0;
ptr = NULL;
//Same trick to insert the exact number of values.
number--;
iterator--;
}
//Incrementing to prevent infinite looping.
number++;
iterator++;
}
//Resetting the iterator for later use.
iterator=0;
break;
};//end case-5
//The sixth case is used to exit the proram at will.
case 6:{
exit(0);
};//end case-6
//The default case occurs in case of error. (hope not)
default :{
printf("\nError!");
exit(-1);
};//end default
}//end switch
}while(1);//end while
return 0;
}
I used double pointers and that got rid of my problems. I hope this will help someone.
