Implementazione di una funzione C++ per la ricerca in un albero binario

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

{

coutNodo non trovato”

} else if( ..... )

{

coutRadice"

} else //stampa gli elementi della lista

.....

}

int trovato(.....,.....,.....)

{

.....

}

Descrizione della funzione

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];

}