CODEWITHSUNDEEP
carrayssorting
Meleadeles
Meleadeles

Reputation: 75

Tree Sort not sorting my array

I have to realize a Tree Sort in C, but I was not able to make it work despite following the classic algorithm as much as possible. Here is my code:

searchTreeSort.h:

#ifndef UTILS_H
#define UTILS_H

#include "utils.h"

#endif


//Déclaration d'une structure représentant un noeud d'arbre
struct _node;
typedef struct _node NODE;

typedef NODE *TREE;

TREE newNode(int item);
TREE insert(TREE node, int key);
void storeInOrder(TREE root, ARRAY t, int i);
void freeAllNodes(TREE root);
void displayNodes(TREE root);
void searchTreeSort(ARRAY t, int max);

searchTreeSort.c:

#include "searchTreeSort.h"

struct _node{
    int value;
    TREE left;
    TREE right;
};

TREE newNode(int item){
    TREE t = malloc(sizeof(NODE));
    t->value = item;
    t->left = NULL; 
    t->right = NULL;
    return t;
}

TREE insert(TREE root, int item){
    if(root == NULL)
        return newNode(item);

    if(item < root->value){
        root->left = insert(root->left, item);
    }
    else if(item > root->value){
        root->right = insert(root->right, item);
    }

    return root;
}

void storeInOrder(TREE root, ARRAY t, int i){
    if(root != NULL){
        storeInOrder(root->left, t, i);
        t[i++] = root->value;
        storeInOrder(root->right, t, i);
    }
}

void freeAllNodes(TREE root){
    if(root != NULL){
        freeAllNodes(root->left);
        freeAllNodes(root->right);
        free(root);
    }
}

void displayNodes(TREE root){
    if(root != NULL){
        displayNodes(root->left);
        displayNodes(root->right);
        printf("%d\n", root->value);
    }
}

void searchTreeSort(ARRAY t, int max){
    TREE root = NULL;
    root = insert(root, t[0]);
    for(int i = 1; i < max; i++){
        insert(root, t[i]);
    }

    int i = 0;
    storeInOrder(root, t, i);
    //displayNodes(root);
    freeAllNodes(root);
}

In utils.h, I have the following typedef: typedef int ARRAY[MAX]; and a definition of said MAX value.

In main, I fill my ARRAY t with random values, and then call my function like this: searchTreeSort(t, max);

Except that when I display my ARRAY before and after the sort, absolutely nothing changed: The elements stayed in the same order.

The function displayAllNodes showed me that the Tree was created correctly, it's the last step of storing the element back in the array in the right order that seems to be going awry.

I already saw some solution on thread like this one: C binary tree sort - extending it But I have to use the typedef int ARRAY[MAX]; and don't know how to implement those kind of more pointers intensive solution while using it.

Could you help me identify where the problem is coming from? Thanks in advance.

Upvotes: 1

Views: 195

Answers (1)

user2736738
user2736738

Reputation: 30906

Well it is supposed to go awry. The value i that you passed is pass by value. You increment it in one function. But that is not anyway going to reflect on other calls to the same function. You are overwriting already written values. So what is the solution?. Simple enough. Pass the address of the variable. 

void storeInOrder(TREE root, ARRAY t, int* i){
    if(root != NULL){
        storeInOrder(root->left, t, i);
        t[(*i)++] = root->value;
        storeInOrder(root->right, t,i);
    }
}

And you call it like this

storeInOrder(root, t, &i);
                     ^^^ passing the address.

In the header file change the declaration

void storeInOrder(TREE root, ARRAY t, int* i);

Upvotes: 1

Related Questions