MIPS汇编二叉树DFS/BFS代码无输出及PC错误调试求助

我正在做一个项目，需要为两种不同格式的二叉树实现深度优先搜索（DFS）、广度优先搜索（BFS）算法，以及两种格式之间的转换程序。但代码运行时没有任何输出，MARS模拟器提示invalid program counter value: 0x00000000，执行因错误终止。请帮忙调试代码。

项目要求 #

• 深度优先搜索（DFS）：在二叉树中搜索指定值，返回元素所在层级，未找到则返回-1。
• 广度优先搜索（BFS）：在二叉树中搜索指定值，返回元素所在层级，未找到则返回-1。
• 转换程序：
  • 从表示格式1转换为表示格式2
  • 从表示格式2转换为表示格式1
• BFS实现：对两种格式的二叉树都能执行BFS

相关代码 #

.data
arraylist_data: .space 400
arraylist_size: .word 0
tree_rep1: .word 4, 9, 10, 10, 15, 2, 3
tree_rep2: .space 28
search_value: .word 10
queue_data: .space 100
queue_front: .word 0
queue_rear: .word -1
queue_size: .word 0
result_msg: .asciiz "Value found at level: "
not_found_msg: .asciiz "Value not found.\n"
dfs1_msg: .asciiz "DFS (Rep 1): "
dfs2_msg: .asciiz "DFS (Rep 2): "
bfs1_msg: .asciiz "BFS (Rep 1): "
bfs2_msg: .asciiz "BFS (Rep 2): "


.text
.globl main

# ArrayList Operations
create_arraylist:
    sw $zero, arraylist_size
    jr $ra

append_arraylist:
    lw $t0, arraylist_size
    sll $t1, $t0, 2
    la $t2, arraylist_data
    addu $t2, $t2, $t1
    sw $a0, 0($t2)
    addi $t0, $t0, 1
    sw $t0, arraylist_size
    jr $ra

get_arraylist_size:
    lw $v0, arraylist_size
    jr $ra

# Queue Operations
create_queue:
    li $t0, 0
    sw $t0, queue_front
    li $t0, -1
    sw $t0, queue_rear
    sw $zero, queue_size
    jr $ra

enqueue:
    lw $t0, queue_size
    li $t1, 100
    beq $t0, $t1, enqueue_full
    lw $t0, queue_rear
    addiu $t0, $t0, 1
    li $t1, 100
    rem $t0, $t0, $t1
    sw $t0, queue_rear
    la $t1, queue_data
    sll $t2, $t0, 2
    addu $t1, $t1, $t2
    sw $a0, 0($t1)
    lw $t0, queue_size
    addiu $t0, $t0, 1
    sw $t0, queue_size
    jr $ra

enqueue_full:
    jr $ra

dequeue:
    lw $t0, queue_size
    beqz $t0, dequeue_empty
    la $t0, queue_data
    lw $t1, queue_front
    sll $t2, $t1, 2
    addu $t0, $t0, $t2
    lw $v0, 0($t0)
    addiu $t1, $t1, 1
    li $t2, 100
    rem $t1, $t1, $t2
    sw $t1, queue_front
    lw $t0, queue_size
    addiu $t0, $t0, -1
    sw $t0, queue_size
    jr $ra

dequeue_empty:
    jr $ra

is_queue_empty:
    lw $t0, queue_size
    beqz $t0, is_empty
    li $v0, 0
    jr $ra

is_empty:
    li $v0, 1
    jr $ra

# Conversion Procedures
convert_rep1_to_rep2:
    addi $sp, $sp, -12
    sw $ra, 8($sp)
    sw $s0, 4($sp)
    sw $s1, 0($sp)
    jal create_arraylist
    move $s0, $a0
    li $a0, 0
    move $s1, $a1
    jal convert_helper_1_to_2
    la $t0, arraylist_data
    move $t1, $s1
    lw $t2, arraylist_size
    li $t3, 0
copy_loop:
    beq $t3, $t2, copy_done
    sll $t4, $t3, 2
    addu $t5, $t0, $t4
    lw $t6, 0($t5)
    sw $t6, 0($t1)
    addi $t1, $t1, 4
    addi $t3, $t3, 1
    j copy_loop
copy_done:
    lw $s1, 0($sp)
    lw $s0, 4($sp)
    lw $ra, 8($sp)
    addi $sp, $sp, 12
    move $v0, $s1
    jr $ra

convert_helper_1_to_2:
    blt $a0, 0, return_helper_1_to_2
    sll $t0, $a0, 2
    addu $t0, $s0, $t0
    lw $t1, 0($t0)
    move $a0, $t1
    jal append_arraylist
    sll $t3, $a0, 1
    addi $t3, $t3, 1
    addi $t4, $t3, 1
    lw $t6, arraylist_size
    blt $t3, $t6, process_left
    j check_right
process_left:
    move $a0, $t3
    jal convert_helper_1_to_2
check_right:
    lw $t6, arraylist_size
    blt $t4, $t6, process_right
    j return_helper_1_to_2
process_right:
    move $a0, $t4
    jal convert_helper_1_to_2
return_helper_1_to_2:
    jr $ra

convert_rep2_to_rep1:
    addi $sp, $sp, -16
    sw $ra, 12($sp)
    sw $s0, 8($sp)
    sw $s1, 4($sp)
    sw $s2, 0($sp)
    move $s0, $a2
    move $s1, $a0
    move $s2, $a1
    li $a0, 0
    li $a1, 0
    jal convert_helper_2_to_1
    lw $s2, 0($sp)
    lw $s1, 4($sp)
    lw $s0, 8($sp)
    lw $ra, 12($sp)
    addi $sp, $sp, 16
    move $v0, $s2
    jr $ra

convert_helper_2_to_1:
    blt $a0, $s0, valid_index
    j return_helper_2_to_1
valid_index:
    blt $a0, 0, return_helper_2_to_1
    sll $t0, $a0, 2
    addu $t0, $s1, $t0
    sll $t1, $a1, 2
    addu $t1, $s2, $t1
    lw $t2, 0($t0)
    sw $t2, 0($t1)
    addi $a0, $a0, 1
    addi $a1, $a1, 1
    jal convert_helper_2_to_1
    addi $a0, $a0, 1
    sll $t3, $a1, 1
    addi $a1, $t3, 1
    jal convert_helper_2_to_1
return_helper_2_to_1:
    jr $ra

# Depth-First Search
dfs_recursive:
    blt $a1, 0, dfs_not_found
    sll $t0, $a1, 2
    addu $t0, $a0, $t0
    lw $t1, 0($t0)
    bne $t1, $a2, check_left
    move $v0, $a3
    jr $ra
check_left:
    addi $t3, $a1, 1
    move $a1, $t3
    addi $a3, $a3, 1
    jal dfs_recursive
    move $t4, $v0
    bne $t4, -1, return_dfs
    addi $t5, $a1, 1
    sll $t5, $t5, 1
    addi $t5, $t5, 1
    move $a1, $t5
    jal dfs_recursive
    move $t6, $v0
    move $v0, $t6
    jr $ra
dfs_not_found:
    li $v0, -1
    jr $ra
return_dfs:
    move $v0, $t4
    jr $ra

# Breadth-First Search
bfs:
    addi $sp, $sp, -16
    sw $ra, 12($sp)
    sw $s0, 8($sp)
    sw $s1, 4($sp)
    sw $s2, 0($sp)
    la $s0, queue_data
    move $s1, $a0
    move $s2, $a2
    jal create_queue
    lw $t0, 0($s1)
    move $a0, $t0
    jal enqueue
bfs_loop:
    jal is_queue_empty
    bnez $v0, bfs_not_found
    jal dequeue
    move $t1, $v0
    lw $t2, 0($s1)
    beq $t1, $t2, bfs_found
    addi $a0, $a0, 1
    sll $t3, $a0, 2
    addu $t4, $s1, $t3
    lw $t5, 0($t4)
    move $a0, $t5
    jal enqueue
    j bfs_loop
bfs_found:
    lw $s2, 0($sp)
    lw $s1, 4($sp)
    lw $s0, 8($sp)
    lw $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
bfs_not_found:
    lw $s2, 0($sp)
    lw $s1, 4($sp)
    lw $s0, 8($sp)
    lw $ra, 12($sp)
    addi $sp, $sp, 16
    li $v0, -1
    jr $ra

# Main Program
main:
    la $a0, tree_rep1
    li $a1, 7
    lw $a2, search_value
    li $a3, 0
    jal dfs_recursive
    move $t0, $v0
    la $a0, dfs1_msg
    li $v0, 4
    syscall
    move $a0, $t0
    li $v0, 1
    syscall
    la $a0, not_found_msg
    li $v0, 4
    syscall
    la $a0, tree_rep2
    li $a1, 7
    lw $a2, search_value
    li $a3, 0
    jal dfs_recursive
    move $t0, $v0
    la $a0, dfs2_msg
    li $v0, 4
    syscall
    move $a0, $t0
    li $v0, 1
    syscall
    la $a0, not_found_msg
    li $v0, 4
    syscall
    la $a0, tree_rep1
    lw $a2, search_value
    jal bfs
    move $t1, $v0
    la $a0, bfs1_msg
    li $v0, 4
    syscall
    move $a0, $t1
    li $v0, 1
    syscall
    la $a0, not_found_msg
    li $v0, 4
    syscall
    la $a0, tree_rep2
    lw $a2, search_value
    jal bfs
    move $t1, $v0
    la $a0, bfs2_msg
    li $v0, 4
    syscall
    move $a0, $t1
    li $v0, 1
    syscall
    la $a0, not_found_msg
    li $v0, 4
    syscall
    li $v0, 10
    syscall

MARS模拟器错误信息 #

汇编：操作成功完成。
错误：无效的程序计数器值：0x00000000
步骤：执行因错误终止。

核心错误修复方案 #

1. 格式转换函数寄存器使用错误 #

convert_rep1_to_rep2中错误地将$a1赋值给s1，实际应该传入tree_rep2的地址，且递归逻辑中索引计算错误。修复后代码：

convert_rep1_to_rep2:
    addi $sp, $sp, -12
    sw $ra, 8($sp)
    sw $s0, 4($sp)
    sw $s1, 0($sp)
    jal create_arraylist
    move $s0, $a0        # tree_rep1的地址
    la $s1, tree_rep2    # 目标地址tree_rep2
    li $a0, 0
    jal convert_helper_1_to_2
    la $t0, arraylist_data
    move $t1, $s1
    lw $t2, arraylist_size
    li $t3, 0
copy_loop:
    beq $t3, $t2, copy_done
    sll $t4, $t3, 2
    addu $t5, $t0, $t4
    lw $t6, 0($t5)
    sw $t6, 0($t1)
    addi $t1, $t1, 4
    addi $t3, $t3, 1
    j copy_loop
copy_done:
    lw $s1, 0($sp)
    lw $s0, 4($sp)
    lw $ra, 8($sp)
    addi $sp, $sp, 12
    move $v0, $s1
    jr $ra

convert_helper_1_to_2:
    blt $a0, 0, return_helper_1_to_2
    # 计算当前节点在tree_rep1中的地址
    sll $t0, $a0, 2
    addu $t0, $s0, $t0
    lw $t1, 0($t0)
    # 将节点值加入arraylist
    move $a0, $t1
    jal append_arraylist
    # 计算左右子节点索引（原tree_rep1中的索引）
    sll $t3, $a0, 1
    addi $t3, $t3, 1
    addi $t4, $t3, 1
    # 检查索引是否在tree_rep1的范围内（大小7）
    li $t6,7
    blt $t3, $t6, process_left
    j check_right
process_left:
    move $a0, $t3
    jal convert_helper_1_to_2
check_right:
    blt $t4, $t6, process_right
    j return_helper_1_to_2
process_right:
    move $a0, $t4
    jal convert_helper_1_to_2
return_helper_1_to_2:
    jr $ra

2. DFS递归逻辑错误 #

原DFS中修改$a1后无法正确计算右子节点索引，需要保存原索引：