Salve a tutti, da poco ho iniziato per conto mio a studiare assembly utilizzando MARS 4.5 come assemblatore. Mettendo in chiaro che ho capito come utilizzare lo Stack Pointer ($sp), non riesco a risolvere un esercizio che ho trovato su un libro. Praticamente avendo un albero binario, dove il primo argomento è il valore del nodo, il secondo l'indirizzo del sottoalbero sinistro e il terzo l'indirizzo del sottoalbero destro, dovrei calcolare la più grande somma di valori possibile fra tutti i percorsi radice-foglia utilizzando lo Stack Pointer attraverso una ricorsione.
Questo è un esempio di albero in questione:
.data
root: .word 7, n01, n02
n01: .word -4, n03, n04
n02: .word 5, n05, n06
n03: .word 5, n07, n08
n04: .word 2, 0, n09
n05: .word 13, 0, 0
n06: .word -15, n10, n11
n07: .word 1, 0, 0
n08: .word 0, n12, n13
n09: .word 27, 0, 0
n10: .word 23, n14, 0
n11: .word 31, 0, n15
n12: .word -8, 0, 0
n13: .word 12, 0, 0
n14: .word 2, 0, 0
n15: .word 2, 0, 0
Diciamo che un codice in linguaggio C che risolve il problema sarebbe questo, anche se da quello che ho imparato questa logica non è applicabile in MIPS:
int maxSumPath (struct node *root) {
if (!root ) return 0;
if(!root.left && !root.right) return root.value;
return max(root.value+maxSumPath(root.left) ,root.value+maxSumPath(root.right)); }
Ci sarebbe qualcuno disposto a mostrare un codice che risolve questo problema o per lo meno dare consigli o passare link/informazioni utili?
Allegati:
Esempio di risultato