Last Revised: Nov 13, 2022
Assignment 4
Copyright By PowCoder代写 加微信 powcoder
Due date: Monday November 28th 17:00 Late date: Thursday December. 1st 17:00
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 branch first, then print the item value and traverse the left branch. This procedure must
be 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. If you have questions about the code please make sure
you review it early and ask for clarification.
Test your solution with multiple inputs. At the very least show that the following input 44 79 12
57 75 39 66 24 21 will produce a reverse sorted output.
Item Left Right
Last Revised: Nov 13, 2022
Submission
This assignment must be submitted electronically using Sakai by the date above (note: all times
are in EST) as a MIPS assembly file. It cannot be stressed enough how important comments are
to help the markers follow your logic.
The TA will be running your program to ensure it is fully functional. Make the marker happy!!!
For the electronic submission, use Sakai, an assignment 4 submission will be available.
Last Revised: Nov 13, 2022
# Put integers into a binary tree
# node structure will be item, left, right
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
# Prompt for an integer to add to the binary tree
la $a0, prmpt1
li $v0, 5
move $s0, $v0 # move the integer into $s0
beqz $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
la $a0, prmpt1
li $v0, 5
move $s0,$v0 # move the integer into $s0
b 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 current 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
### main ending
#######################################################################
Last Revised: Nov 13, 2022
# 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
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 current node
# $t2 – item in current node
# $t3 – last node we traversed
lw $t1, head # load the address of the head node
beqz $t1, first # if the tree is empty add the first node
# traverse the tree until we find where we need to add the new node
lw $t2, ($t1) # load current item
beq $s0, $t2, end_loop1 # if the item is the same, no new node is needed
ble $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 branch beqz $t3, add_new_right # if there is no right address add the node here move $t1, $t3 # otherwise load the right address and loop lw $t3, 4($t1) # load pointer to left branch beqz $t3, add_new_left # if there is no left address add the node here move $t1, $t3 # otherwise load the left address and loop b loop1 # test the next portion of the tree end_loop1: b add_node_rtn # add the new node to the head and return li $a0,12 # malloc 12 bytes from the heap # 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 b 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 # 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 b add_node_rtn Last Revised: Nov 13, 2022 # add the new node to the right pointer and return add_new_right: li $a0,12 # malloc 12 bytes from the heap # 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 ### 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 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com