Assignment
You will find a MIPS assembly program BinTree.asm as downloadable code along with this
assignment (it is also copied at the end of this assignment sheet). You can assemble and run this
program altough until you implement the print_tree procedure it will just drop off the end of the
code. The code provided will prompt the user to enter integers until a 0 is entered, terminating
the input. The integers are stored in a binary tree structure using dynamic memory allocated from
the heap and using the allocated variable “head” to store the memory address of the root node of
the binary tree. If you encounter a value of 0 in any element representing an address, that means
there are no nodes down that path of the tree (ie: if “head” is still 0 the tree is empty).
Each Node is laid out in the following format:
A node consumes 12 bytes, (i.e. 3 words). The first word contains the item value and the next
two words hold pointers (addresses) to next nodes in the tree. Note: that null is represented as 0
in the nodes, and non null values are addresses in the heap space. You can inspect the heap and
see the structure of the tree.
You must write the procedure print_tree which will traverse the tree in a marner to output the
data values, one per line, from maximum to minimum value. This is achieved by a traversal of
the right
anch first, then print the item value and traverse the left
anch. This procedure must
e implemented using recursion and must comply with the standards as taught in class.
Each recursive call will need an activation record base on the use of the $fp register. These
should be created and destroyed using the conventions set out in lecture. Following convention is
important to show your understanding of activation records.
Be sure to properly document your code.
Test your solution with multiple inputs. At the very least show that the following input XXXXXXXXXX
XXXXXXXXXXwill produce a reverse sorted output.
Item Left Right
Submission
This assignment must be submitted as a MIPS assembly file. It cannot be stressed enough how
important comments are to help the markers follow your logic.
The End
# Put integers into a binary tree
# node structure will be item, left, right
.data
head: .word 0 # address of the first element in the binary tree
prmpt1: .asciiz "Enter an integer to insert: "
msge: .asciiz "Tree is empty\n"
.globl main
.text
main:
# Prompt for an integer to add to the binary tree
li $v0, 4
la $a0, prmpt1
syscall
li $v0, 5
syscall
move $s0, $v0 # move the integer into $s0
while1:
eqz $s0, end_while1 # test if the user entered 0
move $a0, $s0 # pass integer in $a0
jal add_node
# Prompt for next integer to add to the binary tree
li $v0, 4
la $a0, prmpt1
syscall
li $v0, 5
syscall
move $s0,$v0 # move the integer into $s0
while1 # loop back
end_while1:
# Now that we have our binary tree, print the items
lw $a0, head # load head into the first argument
addi $sp, $sp, -8 # make room on stack for frame pointer and return address
sw $fp, 4($sp) # save cu
ent frame pointer
addi $fp, $sp, 8 # set frame pointer location
jal print_tree
move $sp, $fp # restore the stack pointer from frame pointer
lw $fp, -4($sp) # restore previous frame pointer
li $v0,10
syscall
### main ending
#######################################################################
# This is not a nested procedure so we will use a leaf procedure call
# This procedure will take $a0 and put it in the binary tree if it is not there
already
add_node:
addi $sp, $sp, -8
sw $a0, 8($sp) # save $a0 as we will overwrite it
sw $s0, 4($sp) # save contents of $s0 as we are overwriting it
move $s0, $a0 # copy input argument into $s0
# $s0 - number to store
# $t1 - address of cu
ent node
# $t2 - item in cu
ent node
# $t3 - last node we traversed
lw $t1, head # load the address of the head node
eqz $t1, first # if the tree is empty add the first node
loop1:
# traverse the tree until we find where we need to add the new node
lw $t2, ($t1) # load cu
ent item
if1:
eq $s0, $t2, end_loop1 # if the item is the same, no new node is needed
le $s0, $t2, go_left # if the new item is <= move to the left
# else we are continuing to the right
lw $t3, 8($t1) # load pointer to right
anch
eqz $t3, add_new_right # if there is no right address add the node here
move $t1, $t3 # otherwise load the right address and loop
endif1
go_left:
lw $t3, 4($t1) # load pointer to left
anch
eqz $t3, add_new_left # if there is no left address add the node here
move $t1, $t3 # otherwise load the left address and loop
endif1:
loop1 # test the next portion of the tree
end_loop1:
add_node_rtn
# add the new node to the head and return
first:
li $a0,12 # malloc 12 bytes from the heap
li $v0,9
syscall
# address to new memory is in $v0
la $t1, head # get the memory location of head
sw $v0, ($t1) # save the address of the new node to head
sw $s0, ($v0) # set item value
sw $0, 4($v0) # empty left pointer
sw $0, 8($v0) # empty right pointer
add_node_rtn
# add the new node to the left pointer and return
add_new_left:
li $a0,12 # malloc 12 bytes from the heap
li $v0,9
syscall
# address to new memory is in $v0
sw $v0, 4($t1) # link the new node into left pointer of parent
sw $s0, ($v0) # set item value
sw $0, 4($v0) # empty left pointer
sw $0, 8($v0) # empty right pointer
add_node_rtn
# add the new node to the right pointer and return
add_new_right:
li $a0,12 # malloc 12 bytes from the heap
li $v0,9
syscall
# address to new memory is in $v0
sw $v0, 8($t1) # link the new node into right pointer of parent
sw $s0, ($v0) # item
sw $0, 4($v0) # left
sw $0, 8($v0) # right
add_node_rtn:
lw $a0, 8($sp) # restore incoming value of $a0
lw $s0, 4($sp) # restore value $s0 had when we were called
addi $sp, $sp, 8
jr $ra
### End of add_node
#######################################################################
###
# This will need to be a recursive procedure to print from max integer to min
# That means a depth first traversal from right to left
#
# $a0 is the address of the head node of the tree segment
print_tree:
# This procedure must be implemented