Я пытаюсь создать поиск в двоичном дереве в MIPS Assembly.Можете ли вы взглянуть на мой код и сказать, где может быть моя проблема.Большое спасибо.
# Description: Binary tree building functions.
#
# Revisions: $Log$
.text # this is program code
.align 2 # instructions must be on word boundaries
#
# Name: add_elements
#
# Description: loops through array of numbers, adding each (in order)
# to the tree
#
# Arguments: a0 the address of the array
# a1 the number of elements in the array
# a2 the address of the root pointer
# Returns: none
#
.globl add_elements
add_elements:
addi $sp, $sp, -16
sw $ra, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)
#***** CODE BLOCK 1 ***************************
#
# Insert your code to iterate through the array, calling build_tree
# for each value in the array. Remember that build_tree requires
# two parameters: the address of the variable which contains the
# root pointer for the tree, and the number to be inserted.
#
# Feel free to save extra "S" registers onto the stack if you need
# more for your function.
#
#
# If you saved extra "S" reg to stack, make sure you restore them
#
MAXIMUM_NUM = 20 # Maximum number of values to
# stop reading in node values
MAXIMUM_VALUE = 9999 # Value to stop reading in node values
li $t0, 0 # Variable for total number of nodes added
move $s1, $a0 # Saving pointer within array of node values
move $s2, $a1 # Saving the total number of elements remaining
iterate_array_values:
lw $t2, 0($s1)
li $t3, MAXIMUM_VALUE # Place the Maximum value (9999) in $t3
beq $t2, $t3, add_done # Call to a stop if the value read was 9999
addi $t0, $t0, 1 # Increase value of $t0 by 1
addi $s2, $s2, -1 # Decrease value of $s2 by 1
move $a0, $a2 # Place the pointer to the root node
move $a1, $t2 # Place the value of the node to be added to the tree
jal build_tree # Jump to the build_tree function
li $t4, MAXIMUM_NUM
beq $s2, $zero, add_done # If no values left, go to add_done
beq $t0, $t4, add_done # Check to see 20 values have been read
addi $s1, $s1, 4 # Shift the pointer location
j iterate_array_values # Jump back to the function call
#***** CODE BLOCK 1 *****************************
add_done:
lw $ra, 12($sp)
lw $s2, 8($sp)
lw $s1, 4($sp)
lw $s0, 0($sp)
addi $sp, $sp, 16
jr $ra
#***** CODE BLOCK 2 ***************************
#
# Put your build_tree subroutine here.
#
build_tree:
.globl allocate_mem # Allocating some memory space for nodes
# Restoring the stack registers
addi $sp, $sp, -20
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $s3, 12($sp)
sw $ra, 16($sp)
move $s0, $a0 # Move argument a0 to s0 stack
move $s1, $a1 # Move argument a1 to s1 stack
li $a0, 3 # Three spaces to be created
jal allocate_mem # Bringing a pointer to the node (v0)
lw $t0, 0($s0) # Check to see if the root node is empty
beq $zero, $t0, node_creation
lw $s0, 0($s0) # Retrieve the pointer of the current node
node_evaluation:
lw $t3, 0($s3) # value of current node into register $t3
beq $s1, $t3, completion # Value of the node is inside the tree
slt $t5, $t3, $s1
bne $t5, $zero, insert_left # Add to the left node
addi $s0, $s0, 4 # Proceed to insert to the right
j insert_node # Jump to insert_node
insert_node:
lw $t4, 0($s0) # Check to see if the pointer of the given node is empty
bne $t4, $zero, repeat # Jump to the repeat function
j node_creation # Jump to the node_creation function
repeat:
move $s0, $t0
j node_evaluation # Jump to the node_evaluation function
insert_left:
addi $s0, $s0, 8 # Shift the current position of the node by 8
node_creation:
sw $v0, 0($s0)
sw $s1, 0($v0) # Put value of node into the pointer of node
j completion # Jump to the completion function
completion:
# Restoring the stack registers
lw $s0, 0($sp) # Top stack restored
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp) # Bottom stack restored
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra # Returning to the function call
#***** CODE BLOCK 2 *****************************
# Description: Binary tree traversal functions.
#
# Revisions: $Log$
# CONSTANTS
#
# traversal codes
PRE_ORDER = 0
IN_ORDER = 1
POST_ORDER = 2
.text # this is program code
.align 2 # instructions must be on word boundaries
#***** CODE BLOCK 3 *****************************
#
# Put your traverse_tree subroutine here.
#
traverse_tree:
# Saving registers onto the stacks
addi $sp, $sp, -20
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $s3, 12($sp)
sw $ra, 16($sp)
beq $zero, $a0, complete_block # If the node in a0 is empty
lw $s0, 4($a0) # Left node is inserted in $s0
lw $s1, 8($a1) # Right node is inserted in $s1
# Flag temporary registers for traversals
li $t0, POST_ORDER
li $t1, IN_ORDER
li $t2, PRE_ORDER
beq $a2, $t0, post_order_traversal
beq $a2, $t1, in_order_traversal
beq $a2, $t2, pre_order_traversal
post_order_traversal:
# Post Order Traversal loop
# From Left to Right to Root
move $a0, $s0 # Traversing to the left
jal traverse_tree
move $a0, $s1 # Traversing to the right
jal traverse_tree
move $a0, $s2 # Traversing the root
jalr $s3 # Call function for node printing
j complete_block # Jump to the completion
in_order_traversal:
# In Order Traversal loop
# From Left to Root to Right
move $a0, $s0 # Traversing to the left
jal traverse_tree
move $a0, $s2 # Traversing the root
jalr $s3 # Call function for node printing
move $a0, $s1 # Traversing to the right
jal traverse_tree
j complete_block # Jump to the completion
pre_order_traversal:
# Pre Order Traversal loop
# From Root to Left to Right
move $a0, $s2 # Traversing the root
jalr $s3 # Call function for node printing
move $a0, $s0 # Traversing to the left
jal traverse_tree
move $a0, $s1 # Traversing to the right
jal traverse_tree
j complete_block
complete_block:
# Completion of tree traversal
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra # Returning to the function caller
#***** CODE BLOCK 3 *****************************
Вывод не так, как кажется.У кого-нибудь есть предложения?Большое спасибо.Похоже, что порядок обхода неверен, но как вы думаете?