Homework 3 - manipolazione di un albero binario

ATTENZIONE: HO AGGIUNTO IL COMANDO "V" CHE STAMPA IL VETTORE

In un vettore è possibile rappresentare implicitamente un albero binario, definito ricorsivamente come segue:

• si pone la radice all'indice 1
• i figli del nodo all'indice X si trovano agli indici 2X e 2X+1

NOTA: Assumiamo che tutti gli elementi vuoti dell'albero contengano il valore 0 (zero).

Esempio: il vettore 0 1 2 3 4 5 6 0 8 9 10 0 0 13 0 0 16 rappresenta l'albero

                      1
                  /         \
            2                  3
         /     \              /
      4        5         6
     /  \       /             \
   8    9  10             13
  /
16

Per individuare un qualsiasi nodo nell'albero, oltre all'indice dell'elemento nel vettore, è possibile usare una successione di bit che indicano per ogni nodo se scendere verso il figlio sinistro (1) o il destro (0).

Leggiamo la successione di bit da destra verso sinistra, ovvero dal bit meno significativo verso il più significativo. Per evitare che gli zeri a sinistra valgano come una successione di mosse verso destra aggiungiamo un bit 1 che indica che siamo arrivati. Per cui, data un qualsiasi percorso indicato da una sequenza di bit P:

• se P==1 siamo arrivati al nodo cercato
• se P>1 dobbiamo ancora scendere
  • il bit meno significativo di P indica se dobbiamo muoverci sul sottoalbero sinistro (1) o destro (0) del nodo in cui siamo
  • tolto il meno significativo, gli altri bit di P indicano come muoversi nel sottoalbero scelto

Quindi ad esempio:

• 1=1 indica la radice (che contiene il valore 1)
• 3=11 indica il suo figlio sinistro (che contiene il valore 2)
• 2=10 indica il suo figlio destro (che contiene il valore 3)
• 7=111 indica il figlio sinistro di 11 (che contiene il valore 4)
• 5=101 indica il figlio destro di 11 (che contiene il valore 5)
• 6=110 indica il figlio sinistro di 10 (che contiene il valore 6)
• 4=100 indica il figlio destro di 10 (che è vuoto)
• 12=1010 indica i 3 movimenti: destra, sinistra, destra, ovvero il nodo 13 nell'esempio precedente
• 13=1011 indica i 3 movimenti: sinistra, sinistra, destra, ovvero il nodo 9 nell'esempio precedente

Realizzate il programma che:

• alloca staticamente un vettore di almeno 1000 word che rappresenta un albero binario vuoto (contiene tutti 0)
• legge una successione di comandi (formati da una lettera su una riga separata), seguiti se necessario da parametri sulle righe successive:
  • Q: (quit) esce dal programma
  • P: (print) stampa l'albero in postordine seguito da accapo, ovvero:
    • se la radice è zero non stampa nulla
    • altrimenti:
      • ricorsivamente, stampa il sottoalbero del figlio sinistro
      • ricorsivamente, stampa il sottoalbero del figlio destro
      • stampa la radice seguita da spazio
  • A: (add) aggiunge un nodo nella posizione indicata, argomenti:
    • percorso: numero intero che contiene la sequenza di bit come descritto sopra. INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)
    • valore: numero intero diverso da zero da inserire nel nodo individuato (assumete che nei test sia sempre diverso da 0)
  • D: (delete) elimina (azzera) un nodo nell'albero. Argomenti:
    • percorso: numero intero che contiene la sequenza di bit come descritto sopra. INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)
  • C: (copy) copia un sottoalbero da una posizione ad un'altra. Argomenti:
    • percorso di partenza: numero intero che contiene la sequenza di bit come descritto sopra. INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)
    • percorso di arrivo: numero intero che contiene la sequenza di bit come descritto sopra. INDIPENDENTEMENTE DAL FATTO CHE I NODI INTERMEDI SIANO PRESENTI (diversi da 0)
    • NOTA: POTETE ASSUMERE CHE NEI TEST I DUE PERCORSI INDICHERANNO SEMPRE SOTTOALBERI DISGIUNTI (ovvero una sequenza di mosse non è il prefisso dell'altra)
    • NOTA: la copia non deve mai copiare eventuali nodi vuoti (con valore 0)
  • V: (vettore) stampa su una riga seguita da accapo tutti i 1000 elementi del vettore, separati da spazio

Esempio

La sequenza di comandi che ricrea l'albero precedente (commentata)

A   # add
1   # alla radice
1   # il valore 1
A   # add
3   # 11=al suo figlio sinistro
2   # il valore 2
A   # add
2   # 10=al suo figlio destro
3   # il valore 3
A   # add
7   # 111=al figlio sinistro di 11
4   # il valore 4
A   # add
5   # 101=al figlio destro di 11
5   # il valore 5
A   # add
6   # 110=al figlio sinistro di 10
6   # il valore 6
A   # add
15  # 1111=al figlio sinistro di 111
8   # il valore 8
A   # add
11  # 1011=al figlio destro di 111
9   # il valore 9
A   # add
13  # 1101=al figlio sinistro di 110
10  # il valore 10
A   # add
10  # 1010=al figlio destro di 101
13  # il valore 13
A   # add
31  # 11111=al figlio sinistro di 1111
16  # il valore 16
P   # stampa l'albero in postordine su una riga
V   # stampa il vettore su una riga
Q   # esce dal programma

Stamperà i valori

16 8 9 4 10 5 2 13 6 3 1
0 1 2 3 4 5 6 0 8 9 10 0 0 13 0 0 16 0 0 0 0 0 ..... (TANTI ALTRI 0 FINO A 1000 ELEMENTI)

Consegna entro lunedì 8 maggio ore 24

Per consegnare usate la pagina di consegna.

Trovate alcuni esempi di test nella pagina apposita.

Per provare gli esempi potete, da riga di comando, usare la redirezione dei file per fornire il file di input che trovate nella pagina dei test:

• java -jar Mars4_5.jar me nc sm ic vostrofile.asm < test.in > test.out

e poi confrontare il file prodotto (test.out) con quello atteso, che trovate nella pagina dei test