1

我有一个关于汇编 mips 代码中的最大叶根的问题。我使用 MARS 4,5 汇编程序。我有这个树值：

.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

第一个元素是节点的值，第二个是左子树，第三个是右子树。对于这个问题，我如何使用堆栈指针 ($SP) 编写 ricorsion？非常感谢。

C代码：

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)); }

图片问题 我解决了我的问题，这是我的解决方案：

.text
main:
    la $a0, root #root's address
    jal sum
    move $a0, $v0 #out of the sum
    li $v0, 1 #command to output
    syscall
    li $v0, 10 #exit();
    syscall
sum:
    bnez $a0, sumric #IF(nodo != null) start the recursion
    li $v0, 0 #else right's sum
    jr $ra
sumric:
    addiu $sp, $sp, -12 #allocate space in the stack pointer
    sw $ra, 0($sp) #save ra
    sw $a0, 4($sp) #save node's address
    lw $a0, 4($a0) #load left subtree node's address
    jal sum
    sw $v0, 8($sp) #save the max sum
    lw $a0, 4($sp) #save node's address
    lw $a0, 8($a0) #load right subtree node's address
    jal sum
    lw $t0, 8($sp) #load left subtree's sum
    bge $v0, $t0, maxsumsx #IF(right subtree's sum > left subtree's sum) go to maxsumsx 
    move $v0, $t0 #else overwrite (change) the max sum
maxsumsx:
    lw $t8, 4($sp) #load node's address
    lw $t3, 0($t8) #load node's value
    bne $t8, 0, maxsumdx #IF(right node's address != null) go to calculate right subtree's sum
    addu $t0, $t0, $t3 #else update left sum
    j turnUP
maxsumdx:
    addu $v0, $v0, $t3 #update right sum
    j turnUP
turnUP:
    lw $ra, 0($sp) #update $ra's value in the stack
    addiu $sp, $sp, 12 #deallocate space in the stack pointer
    jr $ra #return back in recursion
4

0 回答 0