编程代考 headptr: .word 0 #address of the headptr pointer

headptr: .word 0 #address of the headptr pointer
enter_list_prompt: .asciiz “Enter in a number that you would like to be added to the tree: ”
output_preorder_tree: .asciiz “The numbers in preorder:\n”
output_inorder_tree: .asciiz “The numbers in inorder:\n”

Copyright By PowCoder代写 加微信 powcoder

output_postorder_tree: .asciiz “The numbers in postorder:\n”
end_user_prompt: .asciiz “Enter 0 to stop input.\n”
end_line_prompt: .asciiz “\n”

.globl main
addi $sp, $sp, -4
sw $ra, 0($sp)

jal user_input

# exit the program
lw $ra, 0($sp)
addi $sp, $sp, 4

user_input:
addi $sp, $sp, -4
sw $ra, 0($sp)

jal get_input_from_user

li $t5, 0
mtc1 $t5, $f2
c.eq.d $f0, $f2
bc1t end_loop_user_input

mov.d $f12, $f0
jal create_new_tree

loop_user_input:
jal get_input_from_user

li $t5, 0
mtc1 $t5, $f2
c.eq.d $f0, $f2
bc1t end_loop_user_input

mov.d $f12, $f0
jal insert_new_node

j loop_user_input

end_loop_user_input:
# if(tree_is_empty)
lw $t0, headptr # get a pointer to the first node
beqz $t0, end_user_input # if(rootNode != null)
jal print_tree_traversals

end_user_input:
lw $ra, 0($sp)
addi $sp, $sp, 4

get_input_from_user:
addi $sp, $sp, -4
sw $ra, 0($sp)

la $a0, enter_list_prompt

lw $ra, 0($sp)
addi $sp, $sp, 4

create_new_tree:
addi $sp, $sp, -4
sw $ra, 0($sp)

jal allocate_memory_for_node

sw $v0, headptr # copy the pointer to first

sdc1 $f12, 0($v0)

# initalize the current node left and right nodes to null
sw $zero, 8($v0)
sw $zero, 12($v0)

lw $ra, 0($sp)
addi $sp, $sp, 4

insert_new_node:
# $f12 = value for the new node
addi $sp, $sp, -4
sw $ra, 0($sp)

lw $t0, headptr # get a pointer to the first node
or $t1, $zero, $zero

loop_to_find_correct_spot:
beqz $t0, if_current_node_equals_null
l.d $f0, 0($t0)

c.eq.d $f12, $f0
bc1t end_insert
c.lt.d $f12, $f0
bc1t transverse_left_for_insert
bc1f transverse_right_for_insert

transverse_left_for_insert:
# get the left node of the current node
or $t1, $t0, $zero
lw $t0, 8($t0)
j loop_to_find_correct_spot

transverse_right_for_insert:
# get the right node of the current node
or $t1, $t0, $zero
lw $t0, 12($t0)
j loop_to_find_correct_spot

if_current_node_equals_null:
# allocate memory for the new node, $v0 is the new node memory address
jal allocate_memory_for_node

# link this node to the previous, $v0 = &(previous node)
# copy address of the new node into the previous node
l.d $f0, 0($t1)
c.lt.d $f12, $f0
bc1t attach_node_left
bc1f attach_node_right

attach_node_left:
sw $v0, 8($t1)
j end_attach_if_else

attach_node_right:
sw $v0, 12($t1)

end_attach_if_else:
# initalize the current node value to the passed in argument on the $f12 register
sdc1 $f12, 0($v0)

# initalize the current node next value to null
sw $zero, 8($v0)
sw $zero, 12($v0)

end_insert:
lw $ra, 0($sp)
addi $sp, $sp, 4

allocate_memory_for_node:
addi $sp, $sp, -4
sw $ra, 0($sp)

# allocate 16 bytes in memory for the new node
ori $v0, $zero, 9
ori $a0, $zero, 16

#$v0 = address of current node

lw $ra, 0($sp)
addi $sp, $sp, 4

print_tree_traversals:
addi $sp, $sp, -4
sw $ra, 0($sp)

# print preorder tree traversal
la $a0, output_preorder_tree
lw $a0, headptr # get a pointer to the head node
jal print_preorder

la $a0, end_line_prompt
ori $v0, $zero, 4

# print inorder tree traversal
la $a0, output_inorder_tree

lw $a0, headptr # get a pointer to the head node
jal print_inorder

la $a0, end_line_prompt
ori $v0, $zero, 4

# print postorder tree traversal
la $a0, output_postorder_tree

lw $a0, headptr # get a pointer to the head node
jal print_postorder

lw $ra, 0($sp)
addi $sp, $sp, 4

print_preorder:
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $s0, 4($sp)

beqz $a0, end_print_preorder # if(node != null)

or $s0, $a0, $zero
jal print_current_node_value

lw $a0, 8($s0)
jal print_preorder

lw $a0, 12($s0)
jal print_preorder

end_print_preorder:
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 8

print_inorder:
addi $sp, $sp, -8 # adjust stack pointer
sw $ra, 0($sp) # store the return pointer
sw $s0, 4($sp) # store the ending condition

beqz $a0, end_print_inorder # if(node != null) we achieve this by checking ==0?
or $s0, $a0, $zero # if a0 !=0, s0 = 1. a0 is our node

lw $a0, 8($s0) # load the left most data(length == 1 word)
jal print_inorder # recursively go to the left

or $a0, $s0, $zero # now we are at the left most leaf
jal print_current_node_value # print the content

lw $a0, 12($s0) # now go to the right
jal print_inorder

end_print_inorder:
lw $s0, 4($sp) #
lw $ra, 0($sp) # return to the parent node
addi $sp, $sp, 8 # adjust the stack pointer

print_postorder:
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $s0, 4($sp)

beqz $a0, end_print_postorder # if(node != null)
or $s0, $a0, $zero

lw $a0, 8($s0)
jal print_postorder
lw $a0, 12($s0)
jal print_postorder

or $a0, $s0, $zero
jal print_current_node_value

end_print_postorder:
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 8

print_current_node_value:
addi $sp, $sp, -4
sw $ra, 0($sp)

# print out current item
l.d $f12, 0($a0)
ori $v0, $zero, 3 # print double

la $a0, end_line_prompt
ori $v0, $zero, 4 # print string

lw $ra, 0($sp)
addi $sp, $sp, 4

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com