Binary tree print on a console application

//basic.h

#ifndef BASIC_H
#define BASIC_H
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <math.h>
#include <string.h>

typedef int element;

typedef struct item {
    element value;
    struct item *left, *right;
} node;

typedef node* tree;

extern bool empty(tree t);
extern tree emptyTree();
extern element root(tree t);
extern tree left(tree t);
extern tree right(tree t);
extern void showElement(element e);
extern tree consTree(element e, tree l, tree r);
extern bool isLess(element lhs, element rhs);
extern bool isEqual(element lhs, element rhs);
extern bool isGreater(element lhs, element rhs);
extern void destroyTree(tree t);
extern void preOrder(tree t);
extern void postOrder(tree t);
extern void inOrder(tree t);
extern bool booleanSearch(element e, tree t);
extern uint32_t height(tree t);
extern void getElementsAtLevel(uint32_t level, tree t, uint32_t k, tree *v, uint32_t *pos);
extern void printTree(tree t, int level, const tree start, FILE *f);
extern uint32_t getLeftSpaces(uint32_t h);
extern uint32_t getDigitsNumber(int n);

#endif // !BASIC_H

//basic.c

bool isEqual(element lhs, element rhs)
{
    return lhs == rhs;
}

bool isLess(element lhs, element rhs)
{
    return lhs < rhs;
}

bool isGreater(element lhs, element rhs)
{
    return !isLess(lhs, rhs) && !isEqual(lhs, rhs);
}

bool empty(tree t)
{
    return (t == NULL);
}

tree emptyTree()
{
    return NULL;
}

element root(tree t)
{
    if (empty(t)) abort();
    return t->value;
}

tree left(tree t)
{
    if (empty(t)) abort();
    return t->left;
}

tree right(tree t)
{
    if (empty(t)) abort();
    return t->right;
}

tree consTree(element e, tree l, tree r)
{
    tree t = malloc(sizeof(node));
    t->value = e;
    t->left = l;
    t->right = r;

    return t;
}

void showElement(element e)
{
    printf("%d", e);
}

void preOrder(tree t)
{
    if (!empty(t))
    {
        printf("\t");
        showElement(root(t));
        preOrder(left(t));
        preOrder(right(t));
    }
}

void postOrder(tree t)
{
    if (!empty(t))
    {
        postOrder(left(t));
        postOrder(right(t));
        printf("\t");
        showElement(root(t));
    }
}

void inOrder(tree t)
{
    if (!empty(t))
    {
        inOrder(left(t));
        printf("\t");
        showElement(root(t));
        inOrder(right(t));
    }
}

bool booleanSearch(element e, tree t)
{
    if (!empty(t)) return false;

    if (isEqual(root(t), e)) return true;
    else
        return (booleanSearch(e, left(t)) || booleanSearch(e, right(t)));
}

void destroyTree(tree t)
{
    if (!empty(t))
    {
        tree l = left(t), r = right(t);
        free(t);
        destroyTree(l); destroyTree(r);
    }
}

uint32_t getDigitsNumber(int n)
{
    uint32_t digits = 1;
    while ((n /= 10) != 0) digits++;

    return digits;
}

uint32_t height(tree t)
{
    if (empty(t)) return 0;
    else
    {
        uint32_t hl = height(left(t)),
            hr = height(right(t));
        return 1 + (hl>hr ? hl : hr);
    }
}

/*
Esiste una relazione matematica tra il numero di spazi stampati a sinistra del primo in ampiezza ad ogni livello dell'albero. Essa è descritta come

a(h) = 2 * a(h - 1) + 3, h € N U {0}
con a(0) = 0 e h altezza del sottoalbero considerato.
*/

uint32_t getLeftSpaces(uint32_t h) //Implementazione della successione matematica sopra citata.
{
    uint32_t ris = 0;

    for (size_t i = 0; i < h; i++)
        ris = 2 * ris + 3;

    return ris;
}

uint32_t getMidlleSpaces(uint32_t left_spaces) //Gli spazi da stampare tra un sottoalbero e l'altro sono gli stessi stampati a sinistra del primo nodo, tenendo però conto delle stampe delle radici.
{
    return left_spaces + 2;
}

void getElementsAtLevel(uint32_t level, tree t, uint32_t k, tree *v, uint32_t *pos) //level: livello di cui si desiderano i nodi (0 è considerato il livello della radice) | t : puntatore alla radice dell'intero albero | k : contatore per tenere traccia del numero di livelli attraversati | *v : successione contenente i nodi trovati (si suppone sia già stata allocata nella funzione chiamante) | *pos : posizione corrente in cui inserire un elemento.
{
    if (!empty(t) && k <= level)                                                    //Se il valore corrente di t è analizzabile e si su un livello precedente o uguale a quello desiderato, si distingue in due casi:
    {
        if (k == level)                                                             //Primo caso: il nodo preso in analisi è sul livello che si desidera.
        {
            v[*pos] = t;                                                            //Il nodo viene messo nella posizione di inserimento corrente, assieme a tutta la struttura sottostante ("l'oggetto" tree t). Non viene effettuato alcun controllo su *pos in quanto, data la struttura dell'albero binario, è matematicamente certo che sarà sempre minore di 2^level.
            (*pos)++;                                                               //La corretta posizione in cui inserire adesso è la prossima.
            return;
        }
        getElementsAtLevel(level, left(t), k + 1, v, pos);                          //Secondo caso: il nodo è a un livello minore (visivamente risulta più alto, più vicino alla radice) di quello desiderato (non potrà mai essere maggiore per quanto detto sopra sulle proprietà matematiche degli alberi binari).
        getElementsAtLevel(level, right(t), k + 1, v, pos);                         //Vengono quindi cercati i nodi al livello k+1, andando nel sottoalbero sinistro e destro di ognuno.
    }
    else
    {
        (*pos) += (uint32_t)pow(2, level - k);                                      //Se il controllo soprastante è fallito, allora bisogna spostare *pos di tante posizioni quante sono quelle "perse", ovvero quelle in cui non sono presenti nodi dello stesso livello.
                                                                                    //Attenzione: le posizioni da saltare nel vettore v non sono sempre 1. Se si incontra un nodo NULL che però è ad un livello maggiore di quello desiderato (caso k < level, con "maggiore" si intende da un punto di vista visivo), le posizioni perse sono tante quante i sottonodi di livello k che quel nodo avrebbe potuto avere, ovvero 2^(level - k). Viene quindi incrementato *pos di tale valore.
    }
}

void printTree(tree t, int level, const tree start, FILE *f)                                                    //t : albero da stampare | level = 0 : livello corrente da stampare all'intero della procedura ricorsiva | start: albero di partenza, necessario alle funzioni asuliari.
{
    if (empty(t)) return;                                                                                       //Condizione di uscita dalla ricorsione.
    tree *nodes = malloc((uint32_t)pow(2, level) * sizeof(tree*));                                              //Essendo tree un puntatore a item, nodes è un puntatore a puntatore. Serve ad immagazzinare una successione di cardinalità 2^level (numero di nodi al level-esimo livello dell'albero), contenente dei tree aventi come radici i nodi di livello level.
    memset(nodes, NULL, (uint32_t)pow(2, level) * sizeof(tree*));                                               //Motivo principale per cui nodes è di tipo tree*. Rimarranno NULL tutte quelle posizioni in cui il nodo non c'è. Questa operazione è eseguita da getElementsAtLevel.

    uint32_t appoggio = 0;                                                                                      //Variabile che serve a getElementsAtLevel per riempire nodes solo nelle posizioni che, in ampiezza, non sono NULL.
    getElementsAtLevel(level, start, appoggio, nodes, &appoggio);                                               //Acquisizione dei nodi al livello level.

    int h = height(t) - 1;                                                                                      //height() restituisce il livello massimo dell'albero, considerando la radice di livello 1 (e non 0). Per usare il valore nelle funzioni ausiliari che seguono, basta scalarlo di 1.
    uint32_t left_spaces = getLeftSpaces(h);
    int left_spaces_next, middle_spaces;

    left_spaces_next = h > 0 ? getLeftSpaces(h - 1) : -1;                                                       //Vengono stabiliti gli spazi a sinistra del livello sottostante quello corrente. Non ha però senso calcolarli per h = 0 (significa che quello raggiunto è l'ultimo livello), quindi viene impostato -1 per garantire la fine immediata dei cicli sottostanti.
    middle_spaces = getMidlleSpaces(getLeftSpaces(h + 1));                                                      //Vengono stabiliti gli spazi da stampare tra un numero e l'altro.

    for (size_t i = 0; i < left_spaces; i++) fprintf(f, " ");                                                   //Vengono stamparti gli spazi a sinistra, ma solo se si sta stampando il primo nodo in ampiezza (i restanti spazi tra un nodo e l'altro sono sempre spazi.
    for (size_t repeat = 0; repeat < pow(2, level); repeat++)                                                   //Questo ciclo occorre quando è necessario ripetere le stesse operazioni per ogni nodo nel livello correntemente analizzato dell'albero binario.
    {
        uint32_t distance_for_digits = 0;                                                                       //Vengono quindi stampati tutti i nodi (esattamente 2^level) e ognuno viene messo nella giusta posizione.
        if (!empty(nodes[repeat]))
        {
            fprintf(f, "%i", root(nodes[repeat]));
            uint32_t digits = getDigitsNumber(root(nodes[repeat]));
            if (digits > 1) distance_for_digits = digits - 1;                                                   //Gestione molto rudimentale dei numeri a più cifre
        }
        else
            fprintf(f, " ");                                                                                    //Viene stampato il nodo solamente se c'è, altrimenti deve essere stampato uno spazio per mantenere intatta la restante struttura dell'albero.
        for (int i = 0; i < middle_spaces - distance_for_digits; i++) fprintf(f, " ");                          //Stampa degli spazi tra un sottoalbero e l'altro.
    }

    fprintf(f, "\n");                                                                                           //Fine della riga in cui sono presenti tutti i nodi del level-esimo livello.
    left_spaces--;                                                                                              //Viene fatta manualmente la modifica del numero di spazi a sinistra del primo nodo e tra i simboli / e \ alla prima iterazione.
    middle_spaces -= 2;                                                                                         //Gli spazi tra / e \ decrementano ad ogni iterazione a 2 a 2.

    for (int i = left_spaces, m = 1; i > left_spaces_next; i--, m += 2, middle_spaces -= 2)                     //finchè il numero di spazi a sinistra da stampare non è quello del livello sottostante (spaces_left_next), il ciclo esegue le operazioni contenute, rispettando quanto affermato sopra riguardo il numero di spazi a sinistra e in mezzo. Leggere sotto per capire l'utilità di ogni variabile indice.
    {
        for (int j = 0; j < i; j++) fprintf(f, " ");                                                            //Stampa degli spazi a sinistra attuali (i).
        for (size_t repeat = 0; repeat < pow(2, level); repeat++)
        {
            if (!empty(nodes[repeat]) && !empty(left(nodes[repeat]))) fprintf(f, "/"); else fprintf(f, " ");    //stampa l'arco sinistro solo se il nodo non è NULL e se l'arco sinistro esiste (ovvero se il figlio sinistro esiste). Altrimenti viene stampato uno spazio per non alterare il resto della struttura.
            for (int j = 0; j < m; j++) fprintf(f, " ");                                                        //L'indice m serve per stampare gli spazi tra i simboli / e \ ad ogni riga, che sono differenti da quelli tra un sottoalbero e l'altro (middle_spaces)
            if (!empty(nodes[repeat]) && !empty(right(nodes[repeat]))) fprintf(f, "\\"); else fprintf(f, " ");  //Operazione perfettamente speculare a quella descritta due righe sopra.
            for (int i = 0; i < middle_spaces; i++) fprintf(f, " ");                                            //Stampa degli spazi tra sottoalberi attuali.
        }                                                                                                       //Viene decrementato il numero di spazi tra / e \ (m), tra sottoalberi (middle_spaces) e a sinistra (i)
        fprintf(f, "\n");                                                                                       //Fine riga.
    }

    uint32_t lh = !empty(left(t)) ? height(left(t)) : 0;                                                        //L'albero viene attraversato in profondità per garantire alle funzioni ausiliarie di passare di ricavare tutti i nodi in ampiezza di livello in livello. Questo significa però che la chiamata ricorsiva in profondità deve considerare il sottoalbero di altezza maggiore, sui cui la funzione height() aveva basato i propri calcoli. Se così non fosse e venisse preso il sottoalbero di sinistra o destra in modo arbitrario, l'algoritmo non funzionerebbe in tutti i casi, in quanto potrebbe essere preso il sottoalbero più corto tra i due, quindi il calcolo dell'altezza nella chiamata ricorsiva successiva sarebbe errato.
    uint32_t rh = !empty(right(t)) ? height(left(t)) : 0;                                                       //Vengono dunque prese in considerazione le altezza dei due sottoalberi....

    lh > rh ? printTree(left(t), level + 1, start, f) : printTree(right(t), level + 1, start, f);               //... E la chiamata ricorsiva in profondità avviene solo sul sottolbero più alto.

    for (size_t i = 0; i < pow(2, level); i++) free(nodes[i]);                                                  //Per risparmiare (poca) memoria vengono liberati solo i puntatori allocati. Liberare anche ciò a cui puntano questi ultimi significherebbe deallocare tutto l'albero su cui si sta lavorando.
}

int main(void)
{
    tree t = consTree(1, consTree(2, consTree(4, consTree(4, NULL, NULL), consTree(5, NULL, NULL)), consTree(4, consTree(4, NULL, NULL), consTree(4, NULL, NULL))), consTree(4, consTree(5, consTree(6, NULL, NULL), consTree(4, NULL, NULL)), consTree(2, consTree(4, NULL, NULL), consTree(7, NULL, consTree(7, NULL, consTree(7, NULL, NULL))))));
    printf("\n");

    FILE *ft = fopen("tree.txt", "wt");

    printTree(t, 0, t, ft);

    fclose(ft);
    return EXIT_SUCCESS;
}