Albero di ricerca - Esercizio

Scrivere una funzione C++ di nome stampaStrada() che riceva come argomenti il puntatore ad un albero binario di ricerca ed una stringa str, e stampi la sequenza di mosse (L = left, R = right) da effettuare dalla radice dell’albero per raggiungere il nodo di valore str. Se il nodo coincide con la radice dell’albero viene stampato il messaggio “radice”, se invece il nodo non esiste, viene stampato il messaggio “nodo non trovato”.
In rifermento alla struttura dati albero binario:

void stampaStrada(.....,.....)
{ elem *
start=NULL; //puntatore alla lista dei passi
elem *temp; //puntatore di scansione
if(!(trovato(.....,.....,.....))) //Per la lista usa il passaggio by reference
{
cout } else if( ..... )
{
cout } else //stampa gli elementi della lista
.....
}
int trovato(.....,.....,.....)
{
.....
}
La funzione trovato() ha il compito di costruire la lista dei passi (‘L’ o ‘R’) da percorrere per trovare il nodo con valore str. Essa può essere formulata in modo ricorsivo notando che:
- se l’albero è vuoto, si deve restituire 0;
- se il nodo con valore str corrisponde alla radice si deve restituire 1, senza inserire elementi in lista;
- se il nodo viene trovato nel sottoalbero sinistro (mediante chiamata ricorsiva), si deve creare un elemento con valore ‘L’ ed inserirlo nella lista;
- se il nodo viene trovato nel sottoalbero destro (mediante chiamata ricorsiva), si deve creare un elemento con valore ‘R’ ed inserirlo nella lista;
- se il nodo non viene trovato nei sottoalberi sinistro e destro, si deve restituire 0.

STRUTTURA ALBERO BINARIO
struct elem{
elem*left;
elem*right;
char str[20];
}