Stavo cercando di rifare un esercizio dell'appello d'esame di programmazione ma mi risulta un errore nella funzione void filtra. Quando faccio il debug ottengo una lista tenere e una lista buttare che non corrispondono al giusto output. Questa è la consegna :
Dato un albero binario R qualsiasi, si chiede di scrivere una funzione ricorsiva che lo percorra in ordine infisso costruendo 2 liste i cui nodi puntano ai nodi dell’albero stesso.
Le 2 liste si chiamano tenere e buttare. Nella lista tenere avremo i puntatori a tutti i nodi di R che contengono valori distinti dei campi info.
La lista buttare, ovviamente, avrà puntatori agli altri nodi di R. Esempio: se l’albero R contiene 2 nodi con info=5 allora uno dei 2 nodi dovrà essere puntato da un nodo di tenere e l’altro
sarà puntato da un nodo di buttare. Conviene inserire in tenere il primo nodo con info=5 che si incontra percorrendo l’albero secondo l’ordine infisso e,successivamente,mettere in buttare
l’altro nodo con info=5. Se ci fossero molti nodi con info=5 allora il primo di essi,secondo l’ordine infisso,andrà in tenere e tutti gli altri andranno in buttare.
Se R= 1(2(1(_,_),_),3(2(_,_),2(_,_))) allora tenere avrà 3 nodi che puntano ai 3 nodi di R in grassetto, mentre buttare punterà agli altri nodi di R.
L’ordine dei nodi in tenere e buttare è irrilevante. La funzione ricorsiva che deve assolvere il compito appena descritto deve avere il seguente prototipo :
void filtra(nodo*R, nodoE*& tenere, nodoE*& buttare) dove la struttura nodo è la solita che usiamo per i nodi degli alberi binari, mentre nodoE (E sta per Esteso) è la seguente:
struct nodoE{nodo* info; nodoE*next; nodoE(nodo*a=0; nodoE*b=0){info=a; next=b;}}; La funzione filtra avrà probabilmente bisogno di una funzione ausiliaria che determinise un nodo di
R ha un campo info uguale a quello di un nodo già visto durante il percorso dell’albero.Anche questa funzione dovrà essere ricorsiva come filtra.
Questo è il codice che ho scritto:
/*Dato un albero binario R qualsiasi, si chiede di scrivere una funzione ricorsiva che lo percorra in ordine infisso costruendo 2 liste i cui nodi puntano ai nodi dell’albero stesso.
Le 2 liste si chiamano tenere e buttare. Nella lista tenere avremo i puntatori a tutti i nodi di R che contengono valori distinti dei campi info.
La lista buttare, ovviamente, avrà puntatori agli altri nodi di R. Esempio: se l’albero R contiene 2 nodi con info=5 allora uno dei 2 nodi dovrà essere puntato da un nodo di tenere e l’altro
sarà puntato da un nodo di buttare. Conviene inserire in tenere il primo nodo con info=5 che si incontra percorrendo l’albero secondo l’ordine infisso e,successivamente,mettere in buttare
l’altro nodo con info=5. Se ci fossero molti nodi con info=5 allora il primo di essi,secondo l’ordine infisso,andrà in tenere e tutti gli altri andranno in buttare.
Se R= 1(2(1(_,_),_),3(2(_,_),2(_,_))) allora tenere avrà 3 nodi che puntano ai 3 nodi di R in grassetto, mentre buttare punterà agli altri nodi di R.
L’ordine dei nodi in tenere e buttare è irrilevante. La funzione ricorsiva che deve assolvere il compito appena descritto deve avere il seguente prototipo :
void filtra(nodo*R, nodoE*& tenere, nodoE*& buttare) dove la struttura nodo è la solita che usiamo per i nodi degli alberi binari, mentre nodoE (E sta per Esteso) è la seguente:
struct nodoE{nodo* info; nodoE*next; nodoE(nodo*a=0; nodoE*b=0){info=a; next=b;}}; La funzione filtra avrà probabilmente bisogno di una funzione ausiliaria che determinise un nodo di
R ha un campo info uguale a quello di un nodo già visto durante il percorso dell’albero.Anche questa funzione dovrà essere ricorsiva come filtra.
Oltre alla funzione filtra, si chiede di costruire 2 funzioni iterative:
i)una funzione iterativa buildBST che usa la lista tenere per costruire un albero BST aggiungendo, uno alla volta, i nodi di R puntati dalla lista tenere.
Inoltre, la funzione, man mano che la lista tenere viene consumata,deve deallocare i suoi nodi nodoE non più utili.
ii)la funzione butta che si occupa di deallocare i nodi della lista buttare. Attenzione che si tratta di buttare sia i nodi nodoE della lista buttare che i nodi di tipo
nodo che sono puntati da questi nodoE.*/
#include<iostream>
using namespace std;
struct nodo { int info; nodo* left; nodo* right; nodo(int a = 0, nodo* b = 0, nodo* c = 0) { info = a; left = b; right = c; } };
struct nodoE { nodo* info; nodoE* next; nodoE(nodo* a = 0, nodoE* b = 0) { info = a; next = b; } };
void stampa_l(nodo* r) {
if (r) {
cout << r->info << '(';
stampa_l(r->left);
cout << ',';
stampa_l(r->right);
cout << ')';
}
cout << '_';
}
bool check(nodoE* L, nodo* r) {
if (!L) return false;
if (L->info->info == r->info) return true;
else
return check(L->next, r);
}
void filtra(nodo* R,nodoE*& tenere, nodoE*& buttare) {
if (R) {
filtra(R->left, tenere, buttare);
if (!check(tenere, R) ) {
if (!tenere) {
tenere = new nodoE(R, 0);
}
else {
while (tenere->next)
tenere = tenere->next;
tenere->next = new nodoE(R, 0);
}
}
else {
if (buttare) {
while (buttare->next)
buttare = buttare->next;
buttare->next = new nodoE(R, 0);
}
else {
buttare = new nodoE(R, 0);
}
}
filtra(R->right, tenere, buttare);
}
}
void stampaLista(nodoE* LISTA) {
if (LISTA) {
cout << LISTA->info->info<<' ';
stampaLista(LISTA->next);
}
}
void buildBST(nodoE*& tenere, nodo*& r) {
r = new nodo(tenere->info->info);
nodoE* pop = tenere;
tenere = tenere->next;
delete pop;
nodo* a = r;
while (tenere) {
while (r) {
if (tenere->info->info < r->info) {
if (!r->left)
r->left = new nodo(tenere->info->info);
else
r = r->left;
}
else {
if (!r->right)
r->right = new nodo(tenere->info->info);
else
r->right;
}
nodoE* c = tenere;
tenere = tenere->next;
delete c;
}
r = a;
}
}
void butta(nodoE*& buttare){
while (buttare) {
delete buttare->info;
nodoE* a = buttare;
buttare = buttare->next;
delete a;
}
}
int main()
{
nodo* r = new nodo(3, new nodo(2), new nodo(1));
r->left->left = new nodo(2);
r->right->left = new nodo(2);
r->right->right = new nodo(3);
nodoE* TENERE = 0;
nodoE* BUTTARE = 0;
stampa_l(r);
filtra(r, TENERE, BUTTARE);
cout << endl;
stampaLista(TENERE);
cout << endl;
stampaLista(BUTTARE);
nodo* bst = 0;
buildBST(TENERE, bst);
butta(BUTTARE);
}
Qualcuno mi sa dire dove ho sbagliato?