PROBLEMA Lettura di un albero binario da file

Sysken

Nuovo Utente
51
20
Buongiorno a tutti,
ho un problema nella lettura di un albero binario da file. In pratica, un programma A riceve in input da tastiera un albero binario (non di ricerca), e lo salva in un file in modalità pre-order (Operazione su nodo, visita sotto-albero sx in pre-order, visita sotto-albero dx in pre-order), di seguito il codice in C:

Codice:
void saveTree(FILE *fPtr, NODE_PTR rootPtr){
    if(rootPtr == NULL){
        fprintf(fPtr, "%s\n", "NULL");
    } else{
        fprintf(fPtr, "%s%d\n", "NODO: ", rootPtr->key);
        saveTree(fPtr, rootPtr->sxTree);
        saveTree(fPtr, rootPtr->dxTree);
    }
}

A questo punto, un programma B deve leggere il contenuto del file e ricreare dunque il medesimo albero binario. Il problema principale sta nei vincoli richiesti:
1) Utilizzare una sola funzione con la seguente intestazione:

Codice:
...
struct node{
    int key;
    struct node* sxTree;
    struct node* dxTree;
};
typedef struct node NODE;
typedef NODE NODE_PTR;

//Intestazione
NODE_PTR freadAB(FILE* fPtr);
...

La funzione dovrà dunque restituirmi un puntatore alla struttura.
2) Il vincolo 1 e i parametri forniti alla funzione non mi consentono di utilizzare la ricorsione, dal momento che non ho modo di muovermi nell'albero.

La natura randomica della funzione di inserimento dei nodi, va a complicare ulteriormente le cose, in quanto i nodi non seguono un percorso prestabilito:

Codice:
struct node{
    int key;
    struct node* sxTree;
    struct node* dxTree;
};
typedef struct node NODE;
typedef NODE NODE_PTR;

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;
    }
}

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;
}

1.PNG
Cattura.PNG

Vorrei discuterne un pò con voi per tirare fuori qualche idea. Ovviamente non voglio il codice, solo uno scambio di idee. :)
 

Andretti60

Utente Èlite
4,184
2,824
Secondo me è la scrittura dell'albero nel file che rende la lettura difficile. Uno deve tenere conto dei nodi che sta leggendo, e chiederli quando legge un NULL, capendo a quale nodo coincide.
Io proverei a scriverlo così
Codice:
fprintf(fPtr, "%s%d %d %d\n", "NODO: ", rootPtr->key, rootPtr->sxTree, rootPtr->dxTree);
PS puoi scrivere "Nodo" direttamente nella string di formattazione.
 

Sysken

Nuovo Utente
51
20
Ciao Andretti60, innanzitutto grazie per la risposta, concordo pienamente, la formattazione del file rende la lettura complicata, purtroppo quest'ultima (errore mio per non averlo scritto) è essa stessa un vincolo.
 

BAT

Moderatore
Staff Forum
Utente Èlite
6,296
2,706
CPU
Neurone solitario
Dissipatore
Ventaglio azionato a mano
Scheda Madre
Casalinga
RAM
Molto molto volatile
GPU
Binoculare integrata nel cranio
PSU
Pastasciutta, pollo e patatine al forno
Net
Segnali di fumo e/o tamburi
OS
Windows 10000 BUG
Secondo me quel file in lettura è sbagliato perché non contiene informazioni sulla struttura dell'albero, ovvero non specifica i singoli sottoalberi di ciascun nodo. Essendo una visita in preordine, l'unica cosa che si capisce è che la radice dell'albero è 8, ma poi non si capisce quali siano i sottoalberi sinistro e destro della radice (lo stesso dicasi -ricorsivamente- :sisi: per ciascun nodo).
Quale sarebbe la figura dell'albero che corrsiponde al file in output? posta un'immagine chiara (disegnala) dell'albero che dovrebbe rappresentare con nodi (cerchietti) e relativo valore, la prima figura è incomprensibile
 

Andretti60

Utente Èlite
4,184
2,824
Quale sarebbe la figura dell'albero che corrsiponde al file in output? posta un'immagine chiara (disegnala) dell'albero che dovrebbe rappresentare con nodi (cerchietti) e relativo valore, la prima figura è incomprensibile
È una delle figure racchiuse in Spoiler nel primo messaggio.
Post automatically merged:

Sei sicuro che l’esempio che hai postato sia corretto? Ci sono nodi con la stessa chiave (4,5,8). Non dovrebbe essere univoca?
 

Giacomo Furlan

Utente Attivo
328
85
CPU
AMD Ryzen 2700x @ 4.1 Ghz
Dissipatore
BeQuiet! SilentLoop 360mm
Scheda Madre
Gigabyte X470 AORUS Gaming 7 WIFI AMD X470
HDD
Corsair MP500 480GB
RAM
G.Skill Trident F4-3600C16D-16GTZ 16GB DDR 4 @ 3466 Mhz (1.42V 14-15-15-15-36)
GPU
MSI GeForce RTX 2080 Gaming X Trio
Audio
Focusrite Saffrire 6 USB
Monitor
AOC Professional U3477PQU 34" 21:9
PSU
EVGA SuperNOVA 650 G3, 80 Plus GOLD 650W
Case
Sharkoon TG5
OS
Windows 10, Fedora 31
@BAT00cent credo sia l'altro spoiler :P
@Andretti60 credo sia il valore del nodo, non il suo identificativo

Da quanto ho capito ogni riga rappresenta il valore del nodo e, se non è null, seguito dai due valori ricorsivamente.

Quindi una cosa del genere (ordinata secondo file di input)

Codice:
Nodo (8)
- Nodo (4)
- - NULL
- - Nodo (6)
- - - Nodo (5)
- - - - NULL
- - - - NULL
- - - Nodo (8)
- - - - NULL
- - - - Nodo (4)
- - - - - NULL
- - - - - NULL
- Nodo (5)
- - Nodo (3)
- - - NULL
- - - Nodo (11)
- - - - NULL
- - - - NULL
- - Nodo (2)
- - - NULL
- - - NULL
 

Sysken

Nuovo Utente
51
20
@BAT00cent, in realtà è possibile capire qual'è il sotto-albero sinistro e quale quello destro:
Cattura.PNG
Prendiamo in esame l'immagine:
Ricordiamo che una visita in pre-order elabora dapprima il nodo per poi visitare in pre-order il sotto-albero sx e quello dx.
Quindi, chiaramente 8 è la radice. Ora, possiamo sicuramente affermare che la funzione si sposterà verso sinistra, fino a quando non incontrerà un puntatore NULL, quel NULL corrisponderà ad un figlio sinistro vuoto. Bene, l'ultima chiamata al sotto-albero più a sinistra, quindi in questo caso 4, deve valutare se è presente un figlio destro. Nel caso in esame 6 è figlio destro di 4, ma 6 oltre a rappresentare un nodo, rappresenta un'altra chiamata ricorsiva. Tale chiamata valuta nuovamente un'eventuale figlio sinistro (5), il figlio corrisponde ad una medesima chiamata ricorsiva, in cui notiamo che il figlio sinistro è NULL, quindi torniamo alla chiamata ricorsiva del nodo 5, si elabora ora la chiamata ricorsiva al nodo destro che restituisce NULL, torniamo al padre 4, la chiamata ricorsiva valuta ora il nodo destro, troviamo il figlio destro (8). Non mi dilungo ulteriormente, le chiamate sono numerose,
Post automatically merged:

@Giacomo Furlan Esattamente, il file ordinato rende chiare le idee, il primo figlio corrisponde sempre alla radice del sotto-albero sx, il secondo a quella del dx.
 

Andretti60

Utente Èlite
4,184
2,824
Capito.
Problema interessante, risolvibile con una list LIFO (last in first out). Almeno, io lo affronterei così.
 

Giacomo Furlan

Utente Attivo
328
85
CPU
AMD Ryzen 2700x @ 4.1 Ghz
Dissipatore
BeQuiet! SilentLoop 360mm
Scheda Madre
Gigabyte X470 AORUS Gaming 7 WIFI AMD X470
HDD
Corsair MP500 480GB
RAM
G.Skill Trident F4-3600C16D-16GTZ 16GB DDR 4 @ 3466 Mhz (1.42V 14-15-15-15-36)
GPU
MSI GeForce RTX 2080 Gaming X Trio
Audio
Focusrite Saffrire 6 USB
Monitor
AOC Professional U3477PQU 34" 21:9
PSU
EVGA SuperNOVA 650 G3, 80 Plus GOLD 650W
Case
Sharkoon TG5
OS
Windows 10, Fedora 31
@Sysken non ho capito se freadAB debba restituirti l'intera sotto-alberatura, oppure un singolo elemento. Nel secondo caso puoi lasciare la logica di associazione all'albero alla funzione main, mentre freadAB potrebbe essere delegato il compito di leggere la singola riga e restituire il puntatore al singolo elemento (senza figli), o null.
 

Giacomo Furlan

Utente Attivo
328
85
CPU
AMD Ryzen 2700x @ 4.1 Ghz
Dissipatore
BeQuiet! SilentLoop 360mm
Scheda Madre
Gigabyte X470 AORUS Gaming 7 WIFI AMD X470
HDD
Corsair MP500 480GB
RAM
G.Skill Trident F4-3600C16D-16GTZ 16GB DDR 4 @ 3466 Mhz (1.42V 14-15-15-15-36)
GPU
MSI GeForce RTX 2080 Gaming X Trio
Audio
Focusrite Saffrire 6 USB
Monitor
AOC Professional U3477PQU 34" 21:9
PSU
EVGA SuperNOVA 650 G3, 80 Plus GOLD 650W
Case
Sharkoon TG5
OS
Windows 10, Fedora 31
Allora potresti avere un array contenente i puntatori ai singoli nodi ed ogni volta che leggi un valore (che sia un nodo oppure NULL) lo metti nell'ultimo nodo dell'array... quando il nodo si "esaurisce" (entrambi i valori settati) lo togli dall'array. Capito dove voglio arrivare?
 

Andretti60

Utente Èlite
4,184
2,824
Allora potresti avere un array contenente i puntatori ai singoli nodi ed ogni volta che leggi un valore (che sia un nodo oppure NULL) lo metti nell'ultimo nodo dell'array... quando il nodo si "esaurisce" (entrambi i valori settati) lo togli dall'array. Capito dove voglio arrivare?
È in pratica una implementazione di una lista LIFO, come ho consigliato io :ok:
 

Sysken

Nuovo Utente
51
20
@Andretti60 L'utilizzo di una pila è ideale, ci ho pensato anche io, ma in questo modo viene infranto il primo vincolo, dal momento che saranno necessarie funzioni ausiliari per la gestione della pila.
È davvero un bel rompicapo :look:
 

Andretti60

Utente Èlite
4,184
2,824
Sei sicuro di avere bisogno di funzioni ausiliarie?
Post automatically merged:

Il problema è che l’albero si può attraversare solo top down, cosa un po’ stupida, se fosse possibile anche il contrario sarebbe facile
 

Sysken

Nuovo Utente
51
20
Inserimento da testa, cancellazione da testa, visita top, status. Non nego che è possibile implementarle tutte nella stessa funzione ma questo potrebbe rendere il codice parecchio "dispendioso".
Ora programmo dapprima la funzione in modo che faccia utilizzo delle funzioni ausiliarie, in un secondo momento, con tanta pazienza, accorpo il tutto in una sola funzione.
Post automatically merged:

Intendi utilizzando dei puntatori ai nodi padri? Purtroppo il problema è quello, la struttura interna dell'albero non è stata definita da me, ne tanto meno quell'odioso inserimento nel file :muro:
 

Entra

oppure Accedi utilizzando

Hot: E3 2021, chi ti è piaciuto di più?

  • Ubisoft

    Voti: 5 17.9%
  • Gearbox

    Voti: 0 0.0%
  • Xbox & Bethesda

    Voti: 21 75.0%
  • Square Enix

    Voti: 0 0.0%
  • Capcom

    Voti: 0 0.0%
  • Nintendo

    Voti: 4 14.3%
  • Altro (Specificare)

    Voti: 1 3.6%

Discussioni Simili