Sia dato un albero binario in cui ogni nodo contiene una coppia di caratteri: etichetta: carattere qualsiasi tranne '\0' o '.' e valore: una cifra tra '0' e '9', memorizzato in un vettore di coppie di byte in modo che:
- la radice dell'albero è a posizione 1 (ovvero al byte 2)
- un nodo a posizione X ha i figli a posizioni 2X e 2x+1
- un nodo vuoto ha coppia etichetta-valore '..' (punto punto)
Ogni nodo X dell'albero è individuato dal percorso che porta dalla radice al nodo, cioè la stringa composta dalle etichette dei nodi dalla radice al nodo X (inclusi)
Esempio se l'albero è
a9 / \ b0 c2 / / \ d1 e3 f7 \ / g1 h6
La stringa che lo definisce è
a9b0c2d1..e3f7..g1....h6......
e il percorso che porta a h6 è la stringa "aceh"
In caso di ambiguità, (i figli di un nodo hanno la stessa etichetta), il percorso sceglie il figlio DESTRO.
Funzioni da realizzare
Leggi_albero(buffer, dim_max) che:
- dato l'indirizzo di una zona di memoria (buffer) di dimensione dim_max
- legge la stringa che rappresenta un intero albero
- torna il numero di nodi presenti nella stringa (compresi i nodi vuoti)
Nota: la stringa va posizionata nel buffer a partire dall'elemento 1 (ovvero dal byte 2)
Inserisci_nodo(albero, percorso, etichetta_e_valore, sx_o_dx) che: (ricorsiva)
- dato l'albero, il percorso che individua il nodo X, una nuova coppia di caratteri etichetta_e_valore del nuovo nodo, ed un bit che indica se il nodo va inserito a sinistra (1) oppure a destra (0)
- sostituisce il figlio sinistro/destro di X con il nodo formato dalla coppia etichetta_e_valore
Elimina_sottoalbero(albero, percorso) che: (ricorsiva)
- dato l'albero ed il percorso che individua un nodo X
- elimina tutti i nodi del sottoalbero radicato in X, sostituendoli con '..' (punto punto)
Sposta_sottoalbero(albero, percorso1, percorso2) che: (ricorsiva)
- dato un albero e due percorsi che individuano due nodi X ed Y
- elimina tutti i nodi del sottoalbero radicato in Y
- copia il sottoalbero radicato in X nel sottoalbero radicato in Y
- azzera tutti i nodi del sottoalbero radicato in X
Stampa_vettore(albero) che:
- dato un albero
- stampa la stringa delle coppie di caratteri contenute nel vettore
Esempio: per l'albero precedente la stringa stampata è
a9b0c2d1..e3f7..g1....h6......
Trova_cammino_massimo(albero, buffer) che: (ricorsiva)
- dato un albero e l'indirizzo di una area di memoria (buffer) sufficientemente grande
- individua il più lungo cammino che da una foglia raggiunge un'altra foglia (non necessariamente passando per la radice dell'albero)
- copia nel buffer la sequenza di etichette che portano dal nodo più a sinistra del cammino individuato, al nodo più a destra, seguita dal carattere '\0'
- In caso di parità (più percorsi massimi) si deve scegliere il percorso che parte dal nodo più a sinistra, ed in caso di ulteriore parità quello che arriva al nodo più a destra
Esempio: se l'albero è quello sopra, il buffer conterrà la stringa
gdbaceh
Cerca_max_prof_nodo(albero, valore) che: (ricorsiva)
- dato un albero ed un valore (tra '0' e '9')
- trova il nodo a profondità massima che contiene il valore cercato
- torna la profondità e l'etichetta del nodo trovato
- In caso di ambiguità (se più nodi hanno quel valore alla stessa profondità massima) si deve tornare il nodo più a destra
Somma_alterna(albero, percorso) che: (ricorsiva)
- dato un albero ed un percorso che individua il nodo X
- nel sottoalbero radicato in X
- somma tutti i valori a profondità pari rispetto a X (compreso X, a profondità 0)
- sottrae tutti i valori a profondità dispari
Programma principale
Il programma main legge una successione di comandi e li esegue nell'ordine.
Un comando inizia con una lettera, seguita sulla stessa riga dal testo che contiene i parametri (separati da ' ' spazio) della chiamata da eseguire
Lo spazio di memoria necessario a contenere l'albero ed eventuali buffer va definito staticamente ed il suo indirizzo viene passato come argomento alle funzioni che ne hanno bisogno.
Comando | Funzione da usare | Output | Note |
L<albero> | Leggi_albero(buffer, dim_max) | stampa il numero di nodi letti,
seguito da '\n' |
al massimo 1000 nodi,
(2000 caratteri) |
I<perc> <e_v> <sx_o_dx> | Inserisci_nodo(albero, percorso, etichetta_e_valore, sx_o_dx) | ||
E<percorso> | Elimina_sottoalbero(albero, percorso) | ||
S<percorso1> <percorso2> | Sposta_sottoalbero(albero, percorso1, percorso2) | ||
V | Stampa_vettore(albero) | stampa il vettore di coppie
come unica stringa seguita da '\n' |
|
C | Trova_cammino_massimo(albero, buffer) | stampa il cammino individuato
seguito da '\n' |
Il massimo cammino possibile
dovrebbe essere < 20 nodi |
M<valore> | Cerca_max_prof_nodo(albero, valore) | stampa l'etichetta
e la profondità trovate, separate da uno spazio e seguite da un '\n' |
|
A<percorso> | Somma_alterna(albero, percorso) | stampa il risultato
seguito da '\n' |
|
Q | esce dal programma |
Consegna entro domenica 27/5 ore 24
Per i file di test vedete http://twiki.di.uniroma1.it/pub/Architetture2/MZ/AA17_18/HomeWork4/