[c++]Dubbio su costruzione dinamica di Alberi in>> da file di testo

[apatriarca]

Non necessariamente. Dipende da come hai definito il formato. Ma se vuoi semplificarti la vita allora sono probabilmente utili altre parentesi. Un albero binario di ricerca ha una struttura particolare, per cui qualsiasi metodo di lettura dovrebbe verificare tali condizioni. Ma certamente una struttura di file come quella che ho scritto può essere usato per qualsiasi tipo di albero.

[Giova411]

Il problema sarà poi generare file di testo con alberi formati da migliaia di nodi.... Le parentesi, messe in modo sensato, sarà una bella sfida che mi porterà a.....seguire il tuo consiglio sugli array semplici

[apatriarca]

Ma perché generare un file di testo? Puoi direttamente creare un albero casuale..

[Giova411]

E ma il programma che userò per fare gli esercizi accetta solo dei .txt semplice di in e out..
Gli uploudo e poi caricando un eseguibile lo compile e prende ingresso e confronta il risultato.

[apatriarca]

Ma il problema è in pratica lo stesso. Generare un albero o quel file di testo non cambia molto.

[apatriarca]

Come suggerimento potrei farti notare che se hai un albero casuale con N nodi (N maggiore di 0), allora puoi scegliere casualmente la tua radice e assegnare due alberi casuali come figli della radice. Il numero di nodi a destra e sinistra vanno generati a caso (ma la loro somma deve essere uguale a N-1). Generi insomma un numero casuale L da 0 a N-1 e generi un albero casuale di L nodi e lo metti come albero sinistro. Generi quindi un albero da mettere come sottoalbero destro con N-1-L nodi.

[Giova411]

Apa ciò che mi dici mi rende FELICEEEEEE!!!
Un passo per volta però, devo ancora fare l'alberello del link come esempio...

Testo nascosto, fai click qui per vederlo

Come farò, un giorno, a sdebitarmi me lo chiedo ogni santo giorno!

[Giova411]

Apa sono sempre incastrato
Ciò di cui sono sicuro è questo:

Codice:

    struct nodo
    {
     string dato; // direi meglio int ma devo beccare le parentesi...... DUBBIO!!!
     nodo* left;
     nodo* right;
    };


Poi mi dovrò "muovere" così?

Codice:

   
    *n = new nodo;
    (*n)->dato = dato;
    (*n)->left = NULL;
    (*n)->right = NULL;


Mettiamo l'input del file così:
---------------------------
7
1 (2 (4 5)) (3 (6 7))
---------------------------

Le parentesi, che mi indicano la strada "corretta" per costruire l'albero, come le becco??

Ad esempio se la funzione che costruisce è

Codice:

void costruisci(string &input, int i, nodo **n){
..



La costruzione dev'essere ricorsiva?

Codice:

 
..
//faccio verifiche sull'input da file e ricorro:
costruisci(input, i, &((*n)->left));
costruisci(input, i, &((*n)->right));
  else
    cout << "INPUT NON VALIDO!" << endl;


E' davvero difficile da fare!!

[apatriarca]

Perché non inizi a definire con più precisione la struttura della stringa che dovrai leggere? Dopotutto, il primo passo verso la soluzione di qualsiasi problema è sempre quella di analizzare il problema e comprenderlo a fondo. L'implementazione viene sempre dopo. La scelta di usare o meno la ricorsione viene anch'essa dopo. La ricorsione è spesso più naturale quando si ha a che fare con alberi, ma questo non significa sia impossibile scrivere il programma in modo da non usarla.

[Giova411]

ApA Maestro mio!!!
Non ho fatto molto ma ci sono quasi.
Ammetto che ho trovato qualcosa in giro (anche se non si trova molto....) per prendere spunto
Seguendo il tuo consiglio, per questo tipo di alberi, penso sia conveniente seguire questo tipo di struttura:
(2,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (1,) ()
E' sempre il primo esempio del primo post
Questi saranno i file di ingresso e le parentesi finali (aperta e subito chiusa) indica che finisce il tree.
Prossimamente "ti butto" il codice e dico "butto" perché il mio codice è sempre "brutto"
(Ho dato tutti gli esami di programmazione negli anni in cui "studiavo e basta" ossia nella stagione '03/'04)