Tags:
create new tag
view all tags

Homework 5 (di recupero) - stampa in postordine di un albero binario

L'esercizio č riservato a chi NON ha consegnato tutti i primi 4 homework.

L'esercizio DEVE essere svolto in modo ricorsivo

L'obiettivo dell'esercizio č stampare in postordine un albero binario (quasi) completo. In particolare, per ogni nodo, invece di stampare il valore del nodo dovete stampare la somma di tutti i valori di quel sottoalbero.

L'albero č in forma di vettore, ovvero come una successione di valori in cui i figli del nodo che si trova all'indice x si trovano agli indici 2x+1 e 2x+2. Quindi un nodo in posizione x č foglia se non ha figli, ovvero se 2x > N-2.

Input: (su righe diverse) il numero N di elementi del vettore seguito dagli N elementi

  • N: dimensione del vettore che contiene i valori dei nodi dell'albero (intero compreso tra 1 e 1024)
  • X_0
  • X_1
  • ...
  • X_N-1

Output: (su righe diverse)

  • visita in postordine e stampa della somma dei nodi di ciascun sottoalbero visitato

Esempio

Input:
10
1
2
3
4
5
6
7
8
9
10

Che corrisponde all'albero

          1
       /     \
     2         3
   /   \     /   \
  4     5   6     7
 / \   /
8   9 10

Output:

8
9
21
10
15
38
6
7
16
55

Consegna entro le ore 24 del 5 giugno

La pagina di consegna č pronta

Tests e risultati

Ho pubblicato una decina di file di test generati a caso (con 100-1024 elementi)

Vi ricordo che per eseguire i test potete usare la riga di comando e la redirezione dell'input, ovvero:

  • java -jar Mars4_5.jar mioprogramma.asm < filedait.in

-- AndreaSterbini - 25 May 2015

Edit | Attach | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r4 - 2015-06-04 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback