SortingAlgorithms/treeSort.c at master · ALor79/SortingAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


#include <stdlib.h>
typedef struct node{
    struct node *leftTree;
    struct node *rightTree;
    int val;
}node;

void addNode ( node **sr, int num )
{
    if ( *sr == NULL )
    {
        *sr = malloc ( sizeof ( node ) ) ;

        ( *sr ) -> leftTree = NULL ;
        ( *sr ) -> val = num ;
        ( *sr ) -> rightTree = NULL ;
    }
    else
    {
        if ( num < ( *sr ) -> val )
            addNode ( &( ( *sr ) -> leftTree ), num ) ;
        else
            addNode ( &( ( *sr ) -> rightTree ), num ) ;
    }
}
void inOrder ( node *subTree, int **array)
{
    if ( subTree != NULL )
    {
        inOrder ( subTree -> leftTree, array) ;
        **array = subTree -> val ;
        ++*array;
        inOrder ( subTree -> rightTree, array) ;
    } else
        return;
}
void deallocTree ( node *subTree)
{
    if ( subTree != NULL )
    {
        deallocTree ( subTree -> leftTree) ;
        free(subTree);
        deallocTree ( subTree -> rightTree) ;
    } else
        return;
}
void treeSort(int *array, int length)
{
    node *root = NULL;
    int i, *p = array;

    for ( i = 0 ; i < length ; i++ )
        addNode ( &root, array[i] ) ;

    inOrder ( root, &p) ;
    deallocTree(root);
}