[C++] aiuto su es.Albero binario

[Fede865]

Salve a tutti!
Non riesco a sfolgere questo esercizio:
Dati un albero binario e un elenco di numeri interi, scrivere un programma che,visitando l'albero secondo la modalità INFISSA verifichi se tutti i numeri dell'elenco sn presenti nell'albero e sn raggiunti dalla visita esattamente nello stesso ordine in cui sono presenti nell'elenco( l'albero può contenere altri elementi).Io avevo iniziato così ma non riesco ad andare avanti

#include<iostream>
using namespace std;
#include"AlberoB.cpp"
#include"Lista.cpp"
#include"Iteratore.cpp"
bool verifica (AlberoB<int> A, int V[]);
void visitaInFissa (const AlberoB<int> A);

void main()
{
AlberoB<int> A(2);...
//creato e riempito un albero
A.insFiglio(SIN,B);...
//lista di numeri, forse era meglio un vettore??
list<int> elenco;
elenco.push_back(6);
elenco.push_back(2);
elenco.push_back(8);
elenco.push_back(1);
elenco.push_back(9);
}

bool verifica (AlberoB<int> A ,list<int> elenco & E )
{
for(int i=0; i<E.size; i++)
{

if(E.pop_back(i)==

return true;

}

void visitaInFissa (const AlberoB<int> &A)
{

if (!A.nullo())
{
visitaInFissa(A.figlio(SIN));
valuta(A.radice());
visitaInFissa(A.figlio(DES));
}

}

Spero che qualcuno mi aiuti! Grazie:(

Non sono stata chiara? nessuno mi da un consiglio... :(

[Fede865]

Ma nessuno fa esercizi sugli alberi!! :(

[banryu79]

Ma nessuno fa esercizi sugli alberi!! :(
Beh, io ad esempio mi trovo più comodo a farli sulla scrivania... :D
(Scusa, non ho resistito).

Battute orribili a parte, proviamo a fare due passi indietro (dal codice) e a ragionare prima sul problema.
Proviamo a spezzettare il problema in passi da svolgere per ottenere il risultato.

La condizione di partenza è il fatto che abbiamo un albero binario i cui elementi sono i numeri interi. Gli lementi nell'albero non sono ordinati,e possono essere stati inseriti in qualunque ordine e con qualunque criterio.

Il problema: dato un elenco di numeri interi, dire se:
a) sono tutti presenti nell'albero
b) l'ordine in cui sono presenti nell'elenco è lo stesso con cui si presentano durante una visita infissa (inorder visit) dell'albero

Ragionandoci un attimo possiamo notare che ci viene richiesto di eseguire un confronto tra due strutture dati diverse: un array (l'elenco) e un albero binario.
Concentrandoci sull'albero binario, possiamo accorgerci che è possibile produrre l'array equivalente visitandolo inorder e prendendo ogni elemento presente. A quel punto ci ritroviamo per le mani due array: l'elenco e gli elementi dell'albero. Ora diventa facile sia verificare se tutti gli elementi in "elenco" sono presenti in "albero", sia se l'ordine con cui compaiono gli elementi in "elenco" è lo stesso di quello con cui compaiono in "albero".

Puoi verificare tutto con un banale esempio:
numeri in input nell'albero iniziale = {8,4,13,2,5,22,1}
(albero costruito con criterio arbitrario)
http://www.freeimagehosting.net/uploads/f3201a22e8.png
elenco = {2,13,5}

Passo 1 - produco l'array elementi albero binario da visita inorder = {2,4,5,8,13,22,1}
Passo 2 - da array al passo 1 ricavo sub-array degli elementi presenti anche in "elenco" = {2,x,5,x,13,x,x}
Passo 3 - verifico uguaglianza array... {2,13,5} != {2,5,13} (perchè anche se hanno lo stesso numero di elementi, il che significa, "per costruzione" del sub-array, che tutti gli elementi in "elenco" sono presenti anche nell'albero, i due array non li contengono nello stesso ordine).

[Fede865]

Grazie mille... provo a scrivere il codice!!
:)

[Fede865]

..Il problema: dato un elenco di numeri interi, dire se:
a) sono tutti presenti nell'albero
b) l'ordine in cui sono presenti nell'elenco è lo stesso con cui si presentano durante una visita infissa (inorder visit) dell'albero........


Mi controlli il codice fin qua se puoi??? non sn tanto convinta se sto facendo bene o meno!
#include<iostream>
using namespace std;

#include"AlberoB.cpp"
#include"Array.cpp"



void main()
{
//creo un albero di prova
AlberoB<int> A(2);
AlberoB<int> B(6);
..........

A.insFiglio(SIN,B);
...........
G.insFiglio(DES,L);

L.insFiglio(SIN,M);


int[] elenco= new int[] {6,2,8,1,9};// qst è il mio elenco di prova
int[] elencoAlbero= new int[20];//qst è il vettore dove tramite il for successivo
// vorrei inserire gli elementi dell'albero
// in base a come vengono visitati cn la visita infissa


for(int i=0; i<A.nullo; i++)

elencoAlbero[i]=visitaInFissa(const AlberoB<int> &A);



}

int visitaInFissa (const AlberoB<int> &A)
{


if (!A.nullo())
{
visitaInFissa(A.figlio(SIN));
return A.radice();
visitaInFissa(A.figlio(DES));
}

}

[banryu79]

Grazie mille... provo a scrivere il codice!!
:)
Mah... intanto prova a vedere se ti ho scritto frescacce: ovvio che cerco di aiutarti ma forse non ho capito bene il problema.
Solo tu puoi stabilire come deve essere l'algoritmo per risolvere il tuo problema.

Per quanto riguarda il codice: se procedi un passo alla volta provando a tradurre la descrizione dell'algoritmo in codice, forse è meglio che postare un copia-incolla del codice che avevi già incluso nel tuo primo post e che avevo già visto (dato che ti ho risposto provando ad aiutarti; mi rifiuto però di fare due cose: a)l'esercizio al posto tuo e b) scriverti il codice).

Poi, la quantità di codice da scrivere è moderata: implementato l'algoritmo fai presto sia a vedere gli esisti di una sua compilazione, che a crearti un esempio per testarlo... anzi, in puro termine di tempo fai sicuramente molto prima a fare tutto questo che postare e aspettare una risposta (hai postato il primo mex il 12/11 e oggi è il 18).

Ciao ;)

[Fede865]

Io non voglio assolutamente che qualcuno mi scriva il codice se no nn imparerò mai..
ti ho chiesto se mi controllavi l'ultimo codice che ho scritto per vedere se fino a lì andava bene...perchè mi sono bloccata già e vorrei una mano ad andare avanti..
lo so che sicuramente per tutti è un esercizio banale, ma per me nn lo è..mi mancano alcune basi e vorrei riucire a capire cosa devo studiare meglio..

[banryu79]

ti ho chiesto se mi controllavi l'ultimo codice che ho scritto per vedere se fino a lì andava bene...perchè mi sono bloccata già e vorrei una mano ad andare avanti..

Perdonami, non avevo visto il l'aggiunta (i due elenchi o array).
In teoria dovresti prima definire l'array che userai per popolare l'albero. Quindi popoli l'albero. Il come lo fai, è indifferente, dato che l'albero potrebbe, in teoria, esserti dato già popolato senza che sia tu a fornirgli i singoli elementi inziali.


mi mancano alcune basi e vorrei riucire a capire cosa devo studiare meglio...
Vediamo quali sono le difficoltà specifiche, perchè ancora io no lo ho capito.
Proviamo così se sei d'accordo.
Usando la descrizione fatta prima:

Passo 1 - produco l'array elementi albero binario da visita inorder = {2,4,5,8,13,22,1}
Passo 2 - da array al passo 1 ricavo sub-array degli elementi presenti anche in "elenco" = {2,x,5,x,13,x,x}
Passo 3 - verifico uguaglianza array... {2,13,5} != {2,5,13} (perchè anche se hanno lo stesso numero di elementi, il che significa, "per costruzione" del sub-array, che tutti gli elementi in "elenco" sono presenti anche nell'albero, i due array non li contengono nello stesso ordine).

spezziattiamo il lavoro da compiere, in singole parti.
"Passo 1"
input: l'albero binario
output: un array i cui elementi sono gli elementi dell'albero binario passato in input, visitato con modalità inorder.
Prova a scrivere la definizione di una funzione che faccia questo.

[Fede865]

.......
spezziattiamo il lavoro da compiere, in singole parti.
"Passo 1"
input: l'albero binario
output: un array i cui elementi sono gli elementi dell'albero binario passato in input, visitato con modalità inorder.
Prova a scrivere la definizione di una funzione che faccia questo.

Ciao!!! ieri purtroppo nn sn stata proprio a casa.. ora ho aperto il pc...e
ho provato a fare la funzione
int visita (const AlberoB<int> &A)
{
int[] elenco=new int[];

for(int i=0; i<A.nullo; i++)
if (!A.nullo())
{
visita(A.figlio(SIN));
elenco[i]= A.radice();
visita(A.figlio(DES));
}
return elenco;

}

[banryu79]

Bene.
Bene se la funzione fa quello che deve (testala, se il compilatore si lamenta per qualche errore di sintassi correggilo, se non sai come correggerlo, posta il codice e i messaggi del compilatore).

Allora passiamo al punto 2:

Passo 2 - da array al passo 1 ricavo sub-array degli elementi presenti anche in "elenco" = {2,x,5,x,13,x,x}

"Passo 2"
input: l'array prodotto come out put al "Passo1", e l'array che rappresenta l'"elenco".
output: il sub-array preso dall'array output del "Passo1" "depurato" degli elementi che non sono presenti anche nell'array "Elenco".

Prova a scrivere la definizione di una funzione che implementi questo secondo passo.
A questo punto dovresti aver ormai capito come funziona: prova a continuare da sola a stabilire cosa deve prendere in input e che output produce ciascun "Passo" restante e a completare l'esercizio.
Ciao ;)

[Fede865]

Mi sa che la funzione che ho scritto nn fa ciò che dovrebbe fare...
riprovo a scriverla:cry:

[Fede865]

Ciaooo! la funzione con i vettori nn mi convinceva..
e ho cambiato tutto utilizzando le liste.. ora manca solo la funzione che mi confronta le 2 liste... mi sono bloccata lì...
Banryu mi aiuti?:) qst è il codice
#include<iostream>
using namespace std;

#include"AlberoB.cpp"
#include"Lista.cpp"
#include"Iteratore.cpp"
#include"Nodo.cpp"

void VisitaInFissa(const AlberoB<int> &A,Lista<int>& lA );
bool confronta(Lista<int>&lA,Lista<int>&l);


void main()
{
AlberoB<int> A(2);
.............
A.insFiglio(SIN,B);
...............

Lista<int> l;

l.addInCoda(6);
l.addInCoda(2);
l.addInCoda(8);
l.addInCoda(1);
l.addInCoda(9);

cout<<l;

Lista<int> lA;

VisitaInFissa(A,lA);

if (confronta(lA,l))
cout<<"l'elenco inserito esiste nell'albero nel giusto ordine";
else
cout<<"l'elenco non esiste nell'albero nel giusto ordine";

}
void VisitaInFissa(const AlberoB<int> &A,Lista<int>& lA )
{
if (!A.nullo())
{
VisitaInFissa(A.figlio(SIN),lA);

lA.addInCoda(A.radice());

VisitaInFissa(A.figlio(DES),lA);
}
}

bool confronta(Lista<int>&lA,Lista<int>&l)
{
Iteratore<int>it_lA(lA);
Iteratore<int>it_l(l);
it_lA.VaiInTesta();
it_l.VaiInTesta();

while(!it_l.isNull())
{
// qui dovrei confrontare ma qst è l'inizio e nn so continuare
if(it_lA.getCurrentValue()==it_l.getCurrentValue())
{ it_lA.MoveNext();
it_l.MoveNext();

}
else
{
it_lA.MoveNext();

} }

return false;
}

[Fede865]

Problema finito!!!
Programmino terminato... grazie a chi mi ha aiutata...:)

[banryu79]

Problema finito!!!
Programmino terminato... grazie a chi mi ha aiutata...:)
Sono contento per te, brava :)