[c++]Dubbio su costruzione dinamica di Alberi in>> da file di testo
Ora volevo iniziare a discutere su un dubbio che mi sta venendo e che sarà un mio problema prossimo....
Quando si parla di alberi che vanno costruiti in tempo "reale" ossia che la struttura viene immessa da tastiere o viene letta da file. Ho sempre visto alberi già formati dove "staticamente" si costruiva root figlio destro poi sinistro e compagnia bella (lavorando di puntatori)
Per costruirlo di volta in volta e sottoporre quindi alberi diversi ad un algoritmo come si fa? Forse è una domanda stupida, ma che consigli potete darmi?
Mi spiego con un esempio.. Una "interview" di google chiedeva il Lowest Common Ancestor (LCA Problem).
Problema classico, ad esempio:
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/
Io vorrei sottoporre alberi diversi, magari scritti in file di testo, che il programma legge e forma di volta in volta.
Non voglio una cosa scritta così:
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
Vorrei una cosa flessibile che "capisca" come formare l'albero usando un ciclo al massimo.
Ossia se nel file.txt abbiamo
-------------------------------------------------------------
7
1 2
1 3
2 4
2 5
3 6
3 7
-------------------------------------------------------------
Possiamo pensare che la prima riga contiene n, ossia il numero di nodi totale.
Le successive n-1 contengono, ciascuna, una coppia padre / figlio.
Ecco, avere una 20 di file del genere, tutti diversi tra loro, generano 20 alberi diversi. Giusto?
Vorrei capire come scrivere del codice flessibile che legga e formi, in modo intelligente, queste strutture.
Risposte
Esistono diversi modi di implementare un albero. Un albero può essere rappresentato usando classi per i nodi e puntatori ai figli, ma anche essere semplicemente un array in cui la struttura ad albero sia implicita. Si possono avere alberi con implementazioni semplicissime e alberi la cui implementazione è incredibilmente complicata.
Nel tuo caso hai un numero di nodi fissato, per cui ha senso allocare tutti i nodi insieme in un array. Ogni nodo è identificato univocamente dalla sua posizione nell'array. In generale: se puoi usare un array per qualcosa di questo tipo allora fallo. Ci sono infatti diverse ragioni per cui farlo è conveniente. E' ad esempio probabilmente più efficiente ed è più facile fare il debug perché puoi visualizzare l'intero albero molto più facilmente. A questo punto puoi decidere se allocare un nodo in più oppure sottrarre uno agli identificativi del nodo. Credo sia in generale più semplice allocare un nodo in più (anche perché è molto piccolo).
A questo punto non rimane che pensare a come descrivere la relazione padre/figlio. Se gli alberi possono essere solo binari, allora potresti pensare di avere un nodo tipo il seguente:
Il valore zero è usato per indicare un valore vuoto, un numero diverso da zero rappresenta un nodo all'interno dell'albero. Un'altra regola abbastanza utile è quella di avere come valore di default quello corrispondente a tutti i byte uguali a zero. E' infatti in generale più semplice e veloce inizializzare a zero rispetto ad altri valori. E' un consiglio particolarmente valido in C, ma usando spesso tipi POD è valido anche in C++.
A questo punto direi che hai tutti gli ingredienti per fare quello che ti sei prefissato:
1. Leggi il primo valore e allochi l'array di nodi.
2. Leggi ogni riga successivi e setti il valore di left o right (a seconda di quale sia ancora non inizializzato) del nodo corrispondente.
Una volta riuscito a fare questo ti propongo un paio di possibili passaggi ulteriori:
1. Sapresti modificare la struttura in modo da avere un albero con nodi aventi un numero di figli arbitrario?
2. Sapresti scrivere un algoritmo che, dato in ingresso un numero di nodi, generi un albero casuale?
Nel tuo caso hai un numero di nodi fissato, per cui ha senso allocare tutti i nodi insieme in un array. Ogni nodo è identificato univocamente dalla sua posizione nell'array. In generale: se puoi usare un array per qualcosa di questo tipo allora fallo. Ci sono infatti diverse ragioni per cui farlo è conveniente. E' ad esempio probabilmente più efficiente ed è più facile fare il debug perché puoi visualizzare l'intero albero molto più facilmente. A questo punto puoi decidere se allocare un nodo in più oppure sottrarre uno agli identificativi del nodo. Credo sia in generale più semplice allocare un nodo in più (anche perché è molto piccolo).
A questo punto non rimane che pensare a come descrivere la relazione padre/figlio. Se gli alberi possono essere solo binari, allora potresti pensare di avere un nodo tipo il seguente:
struct Node {
unsigned parent; // opzionale..
unsigned left, right;
};
Il valore zero è usato per indicare un valore vuoto, un numero diverso da zero rappresenta un nodo all'interno dell'albero. Un'altra regola abbastanza utile è quella di avere come valore di default quello corrispondente a tutti i byte uguali a zero. E' infatti in generale più semplice e veloce inizializzare a zero rispetto ad altri valori. E' un consiglio particolarmente valido in C, ma usando spesso tipi POD è valido anche in C++.
A questo punto direi che hai tutti gli ingredienti per fare quello che ti sei prefissato:
1. Leggi il primo valore e allochi l'array di nodi.
2. Leggi ogni riga successivi e setti il valore di left o right (a seconda di quale sia ancora non inizializzato) del nodo corrispondente.
Una volta riuscito a fare questo ti propongo un paio di possibili passaggi ulteriori:
1. Sapresti modificare la struttura in modo da avere un albero con nodi aventi un numero di figli arbitrario?
2. Sapresti scrivere un algoritmo che, dato in ingresso un numero di nodi, generi un albero casuale?
"apatriarca":
Una volta riuscito a fare questo ti propongo un paio di possibili passaggi ulteriori:
1. Sapresti modificare la struttura in modo da avere un albero con nodi aventi un numero di figli arbitrario?
2. Sapresti scrivere un algoritmo che, dato in ingresso un numero di nodi, generi un albero casuale?
Apa fermooo che poi ti si ritorce contro 
VEDO CHE HAI CAPITO AL VOLO!!!
Avevo pensato a qualcosa del genere ma ho il problema di definire i figli!!!
struct nodo{
vector<int> figli;
int peso;
};
int N;
vector<nodo> albero;
vector<int> S;
int get(int node){
if(S[node]==-1){
S[node]=albero[node].peso;
for(int f:albero[node].figli)
// fai qualcosa
}
return // qualcosa;
}
int main(void) {
ifstream in("in.txt");
ofstream out("out.txt");
in>>N;
albero.resize(N);
S.resize(N,-1);
for(int i=0;i<N;i++)
in>>albero[i].peso; // come fo SX e DX?!
for(int i=0;i<N-1;i++){
int p,f;
in>>p>>f;
albero[p].figli.push_back(f); // e qui devo capire come fare
}
// fai qualcosa
return 0;
}
AIUTOOOOO
non ridere!!!!Ma devo riuscire a leggere da file e lavorare con queste specifiche struct:
// Albero binario
struct nodo
{
int chiave;
struct nodo *left, *right;
};
nodo * newNodo(int k)
{
nodo *temp = new nodo;
temp->chiave = k;
temp->left = temp->right = NULL;
return temp;
}
Perché stai usando un vector se vuoi un albero binario? Il metodo più semplice per gestire i figli è quello di scegliere che il primo figlio che compare sia sempre quello di sinistra. Il secondo quello di destra. Se vuoi maggiore controllo potresti sempre decidere che se inserisci il valore 0 nel file corrisponde ad un figlio nullo..
Usare quella funzione significa complicarti la vita. Ci sono infatti due alternative: avere un array di appoggio che contiene puntatori ai nodi corrispondenti oppure cercare ogni volta la chiave all'interno dell'albero. La seconda alternativa è la più complicata perché durante la costruzione potresti avere più alberi che devi poi unire.. La soluzione più semplice è invece quella di allocare tutti i nodi all'inizio usando quella funzione e inserire i loro indirizzi in un array che poi userai per andarli a recuperare. Si tratta però di una complicazione rispetto alla più semplice soluzione di lavorare direttamente con chiavi e indici. Nota che puoi invece lavorare tranquillamente con quella struttura per il nodo. Non ha importanza se usi gli indici o i puntatori per accedere a i nodi figli. L'unico reale vantaggio dell'uso di indici è quello di essere più facilmente scrivibile e leggibile da file (puoi infatti leggere e scrivere la struttura direttamente da file senza alcun problema di correzione dei puntatori).
Usare quella funzione significa complicarti la vita. Ci sono infatti due alternative: avere un array di appoggio che contiene puntatori ai nodi corrispondenti oppure cercare ogni volta la chiave all'interno dell'albero. La seconda alternativa è la più complicata perché durante la costruzione potresti avere più alberi che devi poi unire.. La soluzione più semplice è invece quella di allocare tutti i nodi all'inizio usando quella funzione e inserire i loro indirizzi in un array che poi userai per andarli a recuperare. Si tratta però di una complicazione rispetto alla più semplice soluzione di lavorare direttamente con chiavi e indici. Nota che puoi invece lavorare tranquillamente con quella struttura per il nodo. Non ha importanza se usi gli indici o i puntatori per accedere a i nodi figli. L'unico reale vantaggio dell'uso di indici è quello di essere più facilmente scrivibile e leggibile da file (puoi infatti leggere e scrivere la struttura direttamente da file senza alcun problema di correzione dei puntatori).
Apa ho un caos in capoccia!!!
OK andrebbe bene mettere questo vincolo.
Però poi vorrei usare semplici puntatori:
Ed avere una struttura che si formi da sola da un semplice file come nell'esempio del primo mio post.
Se ho codice che si esprime così "root->right->right" è il massimo!
Solo che il problema è proprio caricarlo da file... E' fattibile per aberi con 300000 mila nodi da caricare da file? Come la formo/carico la struttura? Non è banale da capire
Sopra ho scritto quello che avevo pensato ieri... Ma sono fuori strada difatti....
"apatriarca":
Il metodo più semplice per gestire i figli è quello di scegliere che il primo figlio che compare sia sempre quello di sinistra. Il secondo quello di destra
OK andrebbe bene mettere questo vincolo.
Però poi vorrei usare semplici puntatori:
Node * root = newNode(1); root->left = newNode(2); //etc etc
Ed avere una struttura che si formi da sola da un semplice file come nell'esempio del primo mio post.
Se ho codice che si esprime così "root->right->right" è il massimo!
Solo che il problema è proprio caricarlo da file... E' fattibile per aberi con 300000 mila nodi da caricare da file? Come la formo/carico la struttura? Non è banale da capire
Sopra ho scritto quello che avevo pensato ieri... Ma sono fuori strada difatti....
Se avessi un Albero Binario di Ricerca forse avrei meno difficoltà
In questo caso si regola da solo dove mettere tra DX e SX. Mi allontano da quello che volevo nel primo post.
Ossia leggendo da file:
---------------------------------------
7
7 3 4 6 5 1 2
---------------------------------------
Non avrei lo stesso albero.. A parte che non so se è manco giusto scrivere così:
Apa mettiti una mano sul cuore
In questo caso si regola da solo dove mettere tra DX e SX. Mi allontano da quello che volevo nel primo post.
Ossia leggendo da file:
---------------------------------------
7
7 3 4 6 5 1 2
---------------------------------------
Non avrei lo stesso albero.. A parte che non so se è manco giusto scrivere così:
struct nodo {
int valore;
nodo *left_nodo;
nodo *right_nodo;
};
void insert_nodo(nodo *tree, nodo *new_nodo){
if (new_nodo->valore > tree->valore){
if (tree->right_nodo == NULL) tree->right_nodo = new_nodo;
else insert_nodo(tree->right_nodo, new_nodo);
}
else {
if (tree->left_nodo == NULL) tree->left_nodo = new_nodo;
else insert_nodo(tree->left_nodo, new_nodo);
}
}
int main(void){
ifstream in("in.txt");
ofstream out("out.txt");
int c, i, val;
cin >> c;
cin >> val;
nodo *tree = (nodo *)malloc(sizeof(nodo));;
tree->valore = val;
tree->left_nodo = NULL;
tree->right_nodo = NULL;
for (i = 0; i < c - 1; i++){
cin >> val;
nodo *new_nodo = (nodo *)malloc(sizeof(nodo));
new_nodo->valore = val;
new_nodo->left_nodo = NULL;
new_nodo->right_nodo = NULL;
insert_nodo(tree, new_nodo);
}
// altro da fare
return 0;
}
Apa mettiti una mano sul cuore
Nel mio codice ho usato gli indici semplicemente perché sono più facili da leggere e comprendere. In un certo senso c'è un maggiore parallelismo con quello che c'è scritto nel file. È tuttavia abbastanza ininfluente il loro utilizzo. Usando puntatori avrai un codice del tutto equivalente.
Il problema più grosso sta nella funzione newNode. Questa funziona alloca dinamicamente e in modo indipendente tutti i nodi, ma questo significa che non hai un modo automatico e veloce per trovare un particolare nodo come nel caso di un semplice array di nodi.
All'interno del file hai però una relazione tra nodi in base alle loro chiavi. Hai quindi bisogno di un metodo veloce per accedere al nodo con una particolare chiave, senza dover cercare la chiave in una struttura complessa come potrebbe essere la foresta (un insieme di alberi) che hai all'inizio. La soluzione più semplice è quindi quella di allocare subito tutti i nodi memorizzando il loro indirizzo in un array. Ogni volta che cerchi una chiave andrai quindi a cercarla in questo array, invece che nella foresta. Ha però l'aria di una inutile forzatura.
Ma non vedo comunque il motivo di allocare a questo punto tutto dinamicamente. Si poteva anche fare qualcosa come segue:
Questa seconda versione è potenzialmente più veloce. Rimane comunque ancora un problema da risolvere: qual'è la radice del tuo albero? Come fai a stabilire se quello che hai ottenuto è effettivamente un albero e non un grafo generico? Come fai a dire se l'albero è connesso invece di essere un insieme disgiunto di alberi?
Il problema più grosso sta nella funzione newNode. Questa funziona alloca dinamicamente e in modo indipendente tutti i nodi, ma questo significa che non hai un modo automatico e veloce per trovare un particolare nodo come nel caso di un semplice array di nodi.
All'interno del file hai però una relazione tra nodi in base alle loro chiavi. Hai quindi bisogno di un metodo veloce per accedere al nodo con una particolare chiave, senza dover cercare la chiave in una struttura complessa come potrebbe essere la foresta (un insieme di alberi) che hai all'inizio. La soluzione più semplice è quindi quella di allocare subito tutti i nodi memorizzando il loro indirizzo in un array. Ogni volta che cerchi una chiave andrai quindi a cercarla in questo array, invece che nella foresta. Ha però l'aria di una inutile forzatura.
std::vector<Node *> nodes;
// lettura dimensione N..
nodes.resize(N+1);
for (int i = 1; i <= N; ++i) {
nodes[i] = newNodo(i);
}
// per settare relazione padre P - figlio F
if (nodes[P]->left) {
if (nodes[P]->right) { /* .. errore .. */ }
else { nodes[P]->right = nodes[F]; }
} else {
nodes[P]->left = nodes[F];
}
Ma non vedo comunque il motivo di allocare a questo punto tutto dinamicamente. Si poteva anche fare qualcosa come segue:
std::vector<Node> nodes;
// lettura dimensione N..
nodes.resize(N+1);
for (int i = 1; i <= N; ++i) {
nodes[i].chiave = i;
}
// per settare relazione padre P - figlio F
if (nodes[P].left) {
if (nodes[P].right) { /* .. errore .. */ }
else { nodes[P].right = &nodes[F]; }
} else {
nodes[P].left = &nodes[F];
}
Questa seconda versione è potenzialmente più veloce. Rimane comunque ancora un problema da risolvere: qual'è la radice del tuo albero? Come fai a stabilire se quello che hai ottenuto è effettivamente un albero e non un grafo generico? Come fai a dire se l'albero è connesso invece di essere un insieme disgiunto di alberi?
Rimanendo sul tipo di esercizi che vorrei fare io
Come esempio perfetto (ma leggendo però da file i vari alberi):
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/
Per ora non mi preoccupo di esser veloce ma di avere una struttura di puntatori corretta.
Possiamo fare che il primo nodo indicato sia la radice e supporre che non siano ammesse foreste?
Quindi albero binario tutto connesso in input. Primo intero sarà il numero di nodi totali.
Poi il primo nodo è la root?
Il problema rimane nel costruirlo bene. Forse mi stai facendo avvicinare alla soluzione, devo pensarci bene.
L'esempio del link dici che è un po' forzato nell'utilizzare puntatori?
Come lo cambieresti poi? Per trovare il LCA con array semplici mi tiro la zappa nei cosidetti
Come esempio perfetto (ma leggendo però da file i vari alberi):
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/
Per ora non mi preoccupo di esser veloce ma di avere una struttura di puntatori corretta.
Possiamo fare che il primo nodo indicato sia la radice e supporre che non siano ammesse foreste?
Quindi albero binario tutto connesso in input. Primo intero sarà il numero di nodi totali.
Poi il primo nodo è la root?
Il problema rimane nel costruirlo bene. Forse mi stai facendo avvicinare alla soluzione, devo pensarci bene.
L'esempio del link dici che è un po' forzato nell'utilizzare puntatori?
Come lo cambieresti poi? Per trovare il LCA con array semplici mi tiro la zappa nei cosidetti
Nel suo caso può avere senso.. Nel tuo, considerando come è definito il file di testo, un po' meno. Il problema del formato da te scelto è che devi accedere in modo causale ai diversi nodi. Se avessi un formato diverso, come il seguente, non ci sarebbero problemi a fare esattamente come scrive il testo:
7 1 (2 4 5) (3 6 7)
Non servono altre parentesi interne a quelle messe? Capito il consiglio e spero di metterlo in pratica.
Il file che "immaginavo" potrebbe essere messo in pratica con
Alberi Binari di Ricerca o, ancor più semplice, con Alberi qualsiasi (senza limitazioni su figli). Giusto Maestro?
Il file che "immaginavo" potrebbe essere messo in pratica con
Alberi Binari di Ricerca o, ancor più semplice, con Alberi qualsiasi (senza limitazioni su figli). Giusto Maestro?
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.
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
Ma perché generare un file di testo? Puoi direttamente creare un albero casuale..
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.
Gli uploudo e poi caricando un eseguibile lo compile e prende ingresso e confronta il risultato.
Ma il problema è in pratica lo stesso. Generare un albero o quel file di testo non cambia molto.
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.
Apa ciò che mi dici mi rende FELICEEEEEE!!!
Un passo per volta però, devo ancora fare l'alberello del link come esempio...
Un passo per volta però, devo ancora fare l'alberello del link come esempio...
Apa sono sempre incastrato 
Ciò di cui sono sicuro è questo:
Poi mi dovrò "muovere" così?
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 è
La costruzione dev'essere ricorsiva?
E' davvero difficile da fare!!
Ciò di cui sono sicuro è questo:
struct nodo
{
string dato; // direi meglio int ma devo beccare le parentesi...... DUBBIO!!!
nodo* left;
nodo* right;
};
Poi mi dovrò "muovere" così?
*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 è
void costruisci(string &input, int i, nodo **n){
..
La costruzione dev'essere ricorsiva?
..
//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!!
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.
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"
[size=50](Ho dato tutti gli esami di programmazione negli anni in cui "studiavo e basta" ossia nella stagione '03/'04)[/size]
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"
[size=50](Ho dato tutti gli esami di programmazione negli anni in cui "studiavo e basta" ossia nella stagione '03/'04)[/size]
#include <fstream>
#include <sstream>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;
struct nodo
{
int value;
string percors;
nodo *left;
nodo *right;
};
bool verificatree (vector < nodo > &inp)
{
nodo *root = NULL, *cur = NULL, *prev = NULL;
for (vector < nodo >::iterator it = inp.begin (); it != inp.end (); it++)
{
nodo n = *it;
if (n.percors.size () == 0)
{
if (root != NULL)
{
return false;
}
else
{
root = &(*it);
}
}
else
{
cur = root;
for (string::iterator pit = n.percors.begin (); pit != n.percors.end (); pit++)
{
if (cur == NULL)
return false;
prev = cur;
if (*pit == 'S')
cur = cur->left;
else if (*pit == 'D')
cur = cur->right;
}
if (cur != NULL)
return false;
if (n.percors[n.percors.size () - 1] == 'S')
prev->left = &(*it);
else if (n.percors[n.percors.size () - 1] == 'D')
prev->right = &(*it);
}
}
return true;
}
bool findpercors(nodo *root, vector<int> &percors, int k)
{
if (root == NULL) return false;
percors.push_back(root->value);
if (root->value == k)
return true;
if ( (root->left && findpercors(root->left, percors, k)) ||
(root->right && findpercors(root->right, percors, k)) )
return true;
percors.pop_back();
return false;
}
int findLCA(nodo *root, int n1, int n2)
{
vector<int> percors1, percors2;
if ( !findpercors(root, percors1, n1) || !findpercors(root, percors2, n2))
return -1;
int i;
for (i = 0; i < percors1.size() && i < percors2.size() ; i++)
if (percors1[i] != percors2[i])
break;
return percors1[i-1];
}
int main (void)
{
ifstream in("in.txt");
ofstream out("out.txt");
int pr1, pr2;
in >> pr1>>pr2;
char nodo_data[1000];
char temp[100];
vector < nodo > inp;
while (in >> nodo_data)
{
if (nodo_data[0] == '(' && nodo_data[1] == ')')
{
if (verificatree (inp))
{
vector < nodo >::iterator it = inp.begin ();
out << findLCA( &(*(inp.begin ())) , pr1, pr2);
}
else
out << "Albero non valido";
out << endl;
inp.clear ();
continue;
}
nodo n;
sscanf (nodo_data, "(%d,%s)", &n.value, temp);
temp[strlen (temp) - 1] = '\0';
n.percors = temp;
n.left = n.right = NULL;
vector < nodo >::iterator it;
for (it = inp.begin (); inp.size () > 0 && it != inp.end (); it++)
{
if ((*it).percors.length () > n.percors.length () || ((*it).percors.length () == n.percors.length () && (*it).percors > n.percors))
{
inp.insert (it, n);
break;
}
}
if (inp.size () == 0 || it == inp.end ())
inp.push_back (n);
}
return 0;
}
3 4 (2,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (1,) () (1,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (2,) () (3,L) (4,R) () (2,S) (4,SS) (6,DS) (7,DD) (3,D) (5,SD) (1,) () (2,S) (4,SS) (6,DS) (3,D) (1,) ()
1 2 Albero non valido 1 1
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo