PROBLEMA Lettura di un albero binario da file

[Giacomo Furlan]

Secondo me non è così difficile da implementare...

Per ogni riga
- se è un nodo
- - se entrambi sxTree e dxTree dell'ultimo elemento dell'array sono già impostati (o è il primo elemento) aggiungi un nuovo nodo
- - altrimenti imposti sxTree o dxTree, il primo non impostato
- - aggiungi il nodo all'array
- se è null
- - se entrambi sxTree e dxTree dell'ultimo elemento dell'array sono già impostati esegui un array pop
- - imposti a null sxTreeo dxTree, il pimo non impostato

Come fai a sapere se sxTree o dxTree sono stati impostati? Potresti usare un secondo array, per esempio.

EDIT: se non capisci come sono arrivato a questa logica, fai un passo indietro e pensa a come riesci a tradurre tu il file nell'alberatura. Prova a leggere il file e scarabocchiare l'albero su un pezzo di carta. Ora fermati e rifletti su come lo stai facendo.

 

[Sysken]

@Giacomo Furlan, ho capito il tuo ragionamento, è un ottimo compromesso alla pila, dal momento che il modo in cui viene utilizzato l'array in qualche modo la simula. Nel secondo array inserisco i nodi esauriti, una ricerca potrà quindi indicarmi se aggiungere un nuovo nodo, o impostare uno dei figli.

 

[BAT]

La prossima volta inserisci una figura decente (vedi la mia) che dia l'idea standard di albero, perché anche sapendo che l'hai messa con la radice a sinistra è alquanto difficoltoso decifrarla. A questo punto chiarisci pure a cosa serve quella che chiami "funzione randomica di inserimento dei nodi": devi usare quella?
Perché se hai una struttura stabilita, se chiami quella funzione randomica i nodi li inserisce a caso e, ogni volta che inserisci un nodo devi pure verificare/correggere che la creazione del nodo corrisponda alla struttura.

 

[Sysken]

@BAT00cent Penso che sia chiaro e al quanto comprensibile: l'utente inserisce il valore dei nodi, la funzione insRand, non trattandosi di un ALBERO BINARIO DI RICERCA o di qualunque altro albero con una struttura predefinita, continua a scendere fino a quando non incontra un figlio nullo. Il percorso è randomico e stabilito, come puoi ben vedere, da una variabile way, la quale indica per way=1 sinistra, viceversa destra.

NODE_PTR insRand(NODE_PTR rootPtr, int key){
    if(rootPtr == NULL){
        NODE_PTR node = newNode(key);
        rootPtr = node;
    } else{
        int way;
        way = rand()%2;
        if(way){
            rootPtr->sxTree = insRand(rootPtr->sxTree, key);
        } else{
            rootPtr->dxTree = insRand(rootPtr->dxTree, key);
        }
    }
    return rootPtr;
}

EDIT: Aggiungo anche che l'unica cosa fondamentale per risolvere il problema è la funzione di salvataggio del file. La funzione di inserimento l'ho aggiunta per completezza. Se l'albero avesse avuto una struttura predefinita il problema sarebbe stato mille volte più semplice, basti pensare nuovamente agli ABR. Inoltre so benissimo che se l'albero avesse avuto una struttura stabilita, una funzione randomica avrebbe infranto le regole della stessa.
Basta porsi ad un livello di astrazione maggiore.

 

[Andretti60]

Questo mi pare un classico esercizio scolastico, dove si chiede allo studente di risolvere un problema con le dovute limitazoni, anche se esistono metodi alternativi o anche migliori, per vedere se lo studente e' in grado di ragionare.

Da tenere presente che questo e' un problema molto comune anche in ambiente lavorativo. Per esempio dove lavoro io abbiamo clienti in tutto il mondo che usano i nostri dati in file di diversi formati (incluso database), che ovviamente NON possiamo cambiare, ma solo migliorare e solo in futuro. Per clienti con dati in formato vecchio, dobbiamo aggirare ostacoli perche' non tutti vogliono fare un grosso upgrade (alcuni non possono nemmeno, per motivi vari). In alcuni casi non abbiamo neanche ben chiaro noi COME migliorare il formato, che magari comporta un grosso cambiamento nel codice, e magari non abbiamo le risorse per farlo in quel momento.

 

[Sysken]

È un esercizio che ho trovato navigando, mi ha incuriosito non poco. A mio parere il vincolo di avere una sola funzione rende le cose molto meno chiare.

 

[Andretti60]

Secondo me non è così difficile da implementare...
...
Come fai a sapere se sxTree o dxTree sono stati impostati? Potresti usare un secondo array, per esempio.

Concordo, e' abastanza semplice.
Una maniera facile per sapere se i nodi destro e sinistro sono stati settati e' quello di ininzializzarli con un valore "impossibile", tipicamente -1 (con un cast, ovvio). Non elegante, ma efficace.
Basta solo un vettore per salvare gli indirizzi dei vari nodi, e una variabile per sapere quale elemento di tale vettore sia quello "corrente", ossia l'ultimo. L'unica scocciatura e' ridimensionale il vettore quando si raggiunge il valore massimo (cosa che non avviene in una "vera" lista). Macchinoso ma possibile.

 

[BAT]

È un esercizio che ho trovato navigando, mi ha incuriosito non poco. A mio parere il vincolo di avere una sola funzione rende le cose molto meno chiare.

Cortesemente, posta il link;
mi sembrava strano che un professore avesse dato come compito una esercizio che viola i principi di buona programmazione (fare tutto in una sola funzione... si commenta da solo!). Cerca di fare esercizi presi sui siti di scuole superiori o università altrimenti rischi di imbatterti in immondizia.

 

[Sysken]

@Andretti60 Inizializzare i nodi al valore -1 è rischioso, ogni nodo può assumere un qualunque valore.
Sono abbastanza sicuro che per essere certi che un nodo sia stata settato il secondo array sia sufficiente, dal momento che la lettura procederà fin quando non incontriamo un nodo foglia per poi risalire.
@BAT00cent il link purtroppo non lo ho, magari vedo se riewco a ritrovarlo. Posso però assicurarti che era un sito universitario.

Post unito automaticamente: 31 Agosto 2018

Posto una soluzione che fa uso di due pile, senza considerare quindi il vincolo di utilizzare una sola funzione:

Spoiler: freadAB

// Strutture
struct node{
    int key;
    struct node* sxTree;
    struct node* dxTree;
};
typedef struct node NODE;
typedef NODE* NODE_PTR;

struct stack{
    NODE_PTR keyPtr;
    struct stack* nextNode;
};
typedef struct stack STACK;
typedef STACK* STACK_PTR;
// fine strutture

NODE_PTR newNode(int key){
    NODE_PTR newNode = (NODE_PTR)malloc(sizeof(NODE));
    if(newNode != NULL){
        newNode->key = key;
        newNode->sxTree = NULL;
        newNode->dxTree = NULL;
    }
    return newNode;
}

STACK_PTR new_stackNode(NODE_PTR keyPtr){
    STACK_PTR newNode = (STACK_PTR)malloc(sizeof(STACK));
    if(newNode != NULL){
        newNode->keyPtr = keyPtr;
        newNode->nextNode = NULL;
    }
    return newNode;
}

STACK_PTR push(STACK_PTR headPtr, NODE_PTR keyPtr){
    STACK_PTR node = new_stackNode(key);
    if(node != NULL){
        node->nextNode = headPtr;
        headPtr = node;
    }
    return headPtr;
}

NODE_PTR pop(STACK_PTR *headPtr){
    if(!isEmpty(*headPtr)){
        STACK_PTR tmpPtr = *headPtr;
        *headPtr = (*headPtr)->nextNode;
        NODE_PTR keyPtr = tmpPtr->keyPtr;
        free(tmpPtr);
        return keyPtr;
    }
    return NULL;
}

int isEmpty(STACK_PTR headPtr){
    return headPtr == NULL;
}

NODE_PTR top(STACK_PTR headPtr){
    if(!isEmpty(headPtr)){
        return headPtr->keyPtr;
    }
    return NULL;
}

NODE_PTR freadAB(FILE* fPtr){
    NODE_PTR rootPtr = NULL;
    NODE_PTR tmpPtr = NULL;
    STACK_PTR sxStack = NULL;
    STACK_PTR dxStack = NULL;
    while(!feof(fPtr)){
        char s[MAX_LEN];
        fscanf(fPtr, "%s", s);
        if(strcmp(s, "NULL") != 0){
            int key;
            fscanf(fPtr, "%d", &key);
            NODE_PTR node = newNode(key);
            if(node != NULL){
                if(rootPtr == NULL){
                    rootPtr = node;
                } else{
                    if((tmpPtr = pop(&sxStack)) != NULL){
                        tmpPtr->sxTree = node;
                    } else if((tmpPtr = pop(&dxStack)) != NULL){
                        tmpPtr->dxTree = node;
                    }
                }
                sxStack = push(sxStack, node);
                dxStack = push(dxStack, node);
            }
        } else{
            NODE_PTR tmp1 = top(sxStack);
            NODE_PTR tmp2 = top(dxStack);
            if((tmp1 != NULL) || (tmp2 != NULL)){
                if(tmp1 != NULL && tmp1 == tmp2){
                    pop(&sxStack);
                } else if(tmp2 != NULL){
                    pop(&dxStack);
                }
            }
        }
    }
    return rootPtr;
}

In pratica, ogni volta che viene letto un nodo questo viene inserito in entrambe le pile ad indicare che quel nodo attende di essere "servito", ovvero di ricevere un indirizzo per il sotto-albero sx e quello dx.
Dal momento che la visita in pre-order esaurisce dapprima i nodi del sotto-albero sx, la funzione continuerà a leggere, fin quando possibile, esclusivamente la pila che contiene gli indirizzi al sotto-albero sx. Non appena la pila sx viene svuotata, inizia la lettura della pila dx.
Quando viene letto un valore NULL possono accadere due cose (tralasciando i controlli sullo status della pila): entrambe le pile hanno in testa lo stesso valore, quindi deve essere servito prima il sotto-albero sx; le pile hanno indirizzi diversi in testa oppure la pila dei nodi di sx è vuota, quindi deve essere servito il sotto-albero destro.

 

[Andretti60]

@Andretti60 Inizializzare i nodi al valore -1 è rischioso, ogni nodo può assumere un qualunque valore....

No, la struttura memorizza l'indirizzo dei nodi figli, difficilmente un indirizzo ha valore -1.
Come ho detto non è elegante, ma efficiente. Non si può usare il valore NULL perché viene usato come terminatore del ramo. Una versione più sicura è inizializzare quei valori con l'indirizzo di un ben noto nodo allocato (o dichiarato) all'inizio.

Post unito automaticamente: 31 Agosto 2018

Ho dato una scorsa al tuo codice, ci sono parecchi errori, funzioni che non ritornano valori e funzioni che ritornano valori errati, tipo il valore 'key' del nodo invece del suo indirizzo.

Quindi avevo ragione, è un esercizio scolastico, dello stesso genere che viene poi dato nelle prove dei colloqui orali di assunzione. Si pone in candidato in fronte a problemi con forti limitazioni e si guarda come ragiona più che al risultato finale. Se il candidato risolve l'esercizio in poco tempo, lo si modifica aggiungendo altre limitazioni. Colloqui del genere o durano ore (ne ho fatti) e fanno divertire sia il bravo candidato e il interrogatore, o durano pochi minuti se il candidato è una scarpa (lo si congeda subito)

 

[Sysken]

@Andretti60, il valore key per la struttura pila equivale al nodo (vedi bene), nella funzione newNode ho per sbaglio cancellato il return, ma nel programma che ho è presente. Entrambe le strutture dato hanno una variabile con identificatore key. La prima è però di tipo int, la seconda NODE_PTR ovvero struct node*.
EDIT: Aggiungo subito il return, inoltre avevo per sbaglio scritto newNode al posto di node nella funzione push.

No, la struttura memorizza l'indirizzo dei nodi figli, difficilmente un indirizzo ha valore -1.

Credevo che il valore -1 era associato al valore del nodo (non a quello dell'indirizzo), dal momento che non è possibile assegnare un intero a una variabile indirizzo.

 

[Andretti60]

Vedo. Sarebbe meglio che cambi nome a quel campo, è un puntatore a un nodo, non una chiave ;)

 

[Sysken]

@Andretti60, lo so bene, ma ho il brutto vizio di non cambiare mai i nomi, lo puoi ben vedere dai parametri delle funzioni, per assurdo mi ci trovo bene. Ora lo cambio per facilitare la comprensione di un futuro lettore.

 

[Andretti60]

Brutto vizio indeed.

 

[Sysken]

@Andretti60, sono comunque sulla strada della "conversione". :hihi: