The goal is to implement a function named tree_traverse that visits the nodes an
ID: 640404 • Letter: T
Question
The goal is to implement a function named tree_traverse that visits the nodes and leaves of a binary tree in MIPS assembler. Some examples are shown in the output below.
Binary trees are an essential part of the study of data structures, and in some programming languages they are the only complex data structure.
Here is an example of an abstract binary tree; the root is A, the leaves are O, J, P, Q and M, and the (interior) nodes are B, H, C, N, I, D, E, K, F, L and G. The root is also a node, and the interior nodes are roots of their subtrees.
For this assignment, the function tree_traverse starts at the root, and counts how many nodes and leaves have the indicated tag. The function prototype in C or C++ is
int tree_traverse(int *tree, int k, int n);
or
int tree_traverse(int tree[], int k, int n);
which has the same meaning. Assuming the int array T represents a valid tree, and rv is an int variable, the initial call to tree_traverse would look like
rv = tree_traverse(T, 0, tag);
If you wrote the function correctly, it will make two similar recursive calls replacing 0 with left and right.
here is the starter program:
th correct output is the following:
tree0 0x10010000 0
tree0 1
tree0 0x10010000 1
tree0 0
tree1 0x10011000 0
tree1 1
tree1 0x10011000 1
tree1 0
tree1 0x10011000 2
tree1 1
tree1 0x10011000 3
tree1 0
tree2 0x10012000 0
tree2 4
tree2 0x10012000 1
tree2 1
tree2 0x10012000 2
tree2 2
tree2 0x10012000 3
tree2 1
tree3 0x10013000 0
tree3 15
tree3 0x10013000 1
tree3 6
tree3 0x10013000 2
tree3 5
tree3 0x10013000 3
tree3 5
All done!
I will award double the points listed here to the best anwerr. I will do this by posting another question easy to answer like 1 +1 and the person who gave me the best answer to this question will answer and I will give them maximum points. So for answering this question i will award a grand total of 3000 points PLZZ HELP SO LOST
JI O J P LG Q MExplanation / Answer
prompt:
li $v0, 4
la $a0, prompt1 #your part starts here
syscall
li $v0, 4
la $a0, prompt2 #[A] - Add a record to the tree
syscall
li $v0, 4
la $a0, prompt3 #[F] - Find a record in the tree
syscall
li $v0, 4
la $a0, prompt4 #[P] - Preorder traversal
syscall
li $v0, 4
la $a0, prompt5 #[I] - Inorder traversal
syscall
li $v0, 4
la $a0, prompt6 #[Q] - Quit the program
syscall
###################
##Get User Input ##
###################
getinput:
li $v0, 4 #Choose a character:
la $a0, prompt7
syscall
li $v0, 12 #Read a single character from console
syscall
move $s0, $v0
beq $s0, 97, addrecord #If you press 'a', addrecord
beq $s0, 102, findrecord #If you press 'f', findrecord
beq $s0, 112, preorder #If you press 'p', preorder
beq $s0, 105, inorder #If you press 'i', inorder
beq $s0, 113, exit #If you press 'q', exit
li $v0, 4 #If you press something random
la $a0, nl #Display new line
syscall
j getinput #And ask for a new character
###################
## Add A Record ##
###################
addrecord:
li $v0, 9 #allocate memory for new record
li $a0, 344 #enough memory for 2 addresses and all the data
syscall
move $s0, $v0 #hang onto the initial address of all our info
li $v0, 4 #prompt for ID
la $a0, addid
syscall
li $v0, 5 #enter integer
syscall
sw $v0, 0($s0) #store our ID into memory Offset: 0
li $v0, 4 #prompt for add year
la $a0, addyear
syscall
li $v0, 5 #enter integer
syscall
sw $v0, 4($s0) #store year into our memory Offset: 4
li $v0, 4 #prompt for add title
la $a0, addtitle
syscall
li $v0, 8 #read our title into the allocated space
la $a0, 8($s0) #Offset: 8
li $a1, 64
syscall
li $v0, 4 #prompt for add description
la $a0, adddescription
syscall
li $v0, 8 #read our description into the allocated space
la $a0, 72($s0) #Offset: 72
li $a1, 256
syscall
bne $s7, 0, setlocations #if this isn't root node let's set the locations
add $s7, $s7, 1 #add 1 to the size of the records
move $s5, $s0 #store this address as root node for now
j prompt
########################
##Set Memory Locations##
########################
setlocations:
move $s6, $s5 #Keep $s5 as our root and use $s6 as temporary storage
move $s4, $s6 #Use $s4 to find the null node slot
storelocations:
beqz $s4, store #If we've reached a leaf, store
lw $t2, 0($s4) #get ID from current node
lw $t1, 0($s0) #get Current ID from new node node we're adding
ble $t1,$t2,goleft #get left location if new node <= current node
move $s6, $s4
lw $s4, 336($s4) #get node to the right if new node > current node
li $t3, 336 #be ready to store to the right slot
j storelocations
goleft:
move $s6, $s4
lw $s4, 328($s4) #load the node to the left
li $t3, 328 #be ready to store to the left slot
j storelocations
store:
beq $t3, 336, storeright #if $t3 was set to storeRight, then store to the right
sw $s0, 328($s6) #else store the new node's location into our node's left slot
add $s7, $s7, 1 #remind our size register that it's growing
j prompt #back to the prompt
storeright:
sw $s0, 336($s6) #store new node to the right slot
j prompt #back to the prompt
########################
## Find Record by ID ##
########################
findrecord:
move $s6, $s5
bne $s7, 0, search
li $v0, 4 #if tree is empty
la $a0, empty #display message Tree is empty
syscall
j prompt #and go wait for input
search:
move $s6, $s5
li $v0, 4 #print ID:
la $a0, id
syscall
li $v0, 5 #let user enter ID
syscall
move $t1, $v0 #store the id we're looking for in $t1
checkagain:
lw $t2, ($s6) #store the id we're currently looking at
bne $t1, $t2, checkempty #if this isn't the right ID, is it the last one?
###########################
##If we find the record:
###########################
li $v0, 4
la $a0, recordfound #Record Found:
syscall
li $v0, 4 #Print ID:
la $a0, id
syscall
li $v0, 1 #Print the ID stored at $s6 [Offset: 0]
lw $a0, 0($s6)
syscall
li $v0, 4 #Print Year:
la $a0, year
syscall
li $v0, 1 #Print the Year stored at $s6 [Offset: 4]
lw $a0, 4($s6)
syscall
li $v0, 4 #Print Title:
la $a0, title
syscall
li $v0, 4 #Print the Title stored at $s6 [Offset: 8]
la $a0, 8($s6)
syscall
li $v0, 4 #Print Description:
la $a0, description
syscall
li $v0, 4 #Print descript stored at $s6 [Offset: 72]
la $a0, 72($s6)
syscall
j getinput
checkempty:
ble $t1, $t2, checkleft #If $t1 <= $t2 check the left node
lw $s6, 336($s6) #Otherwise check the right node
bne $s6, 0, checkagain #If this record isn't empty, check again
li $v0, 4 #Otherwise
la $a0, recordnotfound #Record not found
syscall
j getinput
checkleft:
lw $s6, 328($s6) #Check the left node
bne $s6, 0, checkagain #If the record isn't empty, check again
li $v0, 4 #Otherwise
la $a0, recordnotfound #Record not found
syscall
j getinput
treeempty:
li $v0, 4 #if tree is empty
la $a0, empty #display message Tree is empty
syscall
j prompt
#####################################
#
# The Inorder Function
#
#####################################
inorder:
beq $s7, 0, treeempty #If the tree is empty display empty message
move $s6, $s5 #$s6 is the record we're currently at
move $t0, $s6 #t0 will iterate $s6 is our starting node
move $t1, $t0 #t1 will be thrown on the stack to keep track of everything
jal printinorder
j prompt
printinorder:
addi $sp, $sp, -12 #allocate 8 bytes for the stack
sw $ra, 0($sp) #4 for the $ra variable
sw $t1, 4($sp) #4 for $t1
bne $t0, 0, dontreturn #if $t0 isn't null don't return
lw $ra, 0($sp) #otherwise:
lw $t1, 4($sp) #pop stack
addi $sp, $sp, 12 #and prepare
jr $ra #to return
dontreturn:
move $t1, $t0 #put $t0 in $t1
lw $t0, 328($t0) #load the next pointer to the left
jal printinorder #and recurse back to printorder
move $s6, $t1 #if we're back here, it's time to print
j goprint #so go print
afterprint:
move $t0, $t1 #after we print, move $t1 back to $t0
lw $t0, 336($t0) #get the next pointer to the right
jal printinorder #recurse to see if it's the last one
move $s6, $t1 #if we made it here, it is, let's print
beq $s6, $t1, done #if we already printed this one, we're done (Root Node)
j goprint #Go print the node to the right
done:
lw $ra, 0($sp) #if we're done, pop our stack
lw $t1, 4($sp) #clean it up
addi $sp, $sp, 12 #8 bytes worth
jr $ra #and return
goprint:
li $v0, 4 #Print ID:
la $a0, id
syscall
li $v0, 1 #Print the ID stored at $s6 [Offset: 0]
lw $a0, 0($s6)
syscall
li $v0, 4 #Print Year:
la $a0, year
syscall
li $v0, 1 #Print the Year stored at $s6 [Offset: 4]
lw $a0, 4($s6)
syscall
li $v0, 4 #Print Title:
la $a0, title
syscall
li $v0, 4 #Print the Title stored at $s6 [Offset: 8]
la $a0, 8($s6)
syscall
li $v0, 4 #Print Description:
la $a0, description
syscall
li $v0, 4 #Print descript stored at $s6 [Offset: 72]
la $a0, 72($s6)
syscall
j afterprint
#####################################
#
# The Preorder Function
#
#####################################
preorder:
beq $s7, 0, treeempty #If the tree is empty display empty message
move $s6, $s5 #$s6 is the record we're currently at
move $t0, $s6 #t0 will iterate $s6 is our starting node
move $t1, $t0 #t1 will be thrown on the stack to keep track of everything
jal printpreorder
j prompt
printpreorder:
addi $sp, $sp, -12 #allocate 8 bytes for the stack
sw $ra, 0($sp) #4 for the $ra variable
sw $t1, 4($sp) #4 for $t1
bne $t0, 0, dontreturnpo #if $t0 isn't null don't return
lw $ra, 0($sp) #otherwise:
lw $t1, 4($sp) #pop stack
addi $sp, $sp, 12 #and prepare
jr $ra #to return
dontreturnpo:
move $s6, $t0 #if we made it here, it is, let's print
j goprintpo #so go print
afterprintpo:
move $t1, $t0 #put $t0 in $t1
lw $t0, 328($t0) #load the next pointer to the left
jal printpreorder #and recurse back to printorder
move $t0, $t1 #after we print, move $t1 back to $t0
lw $t0, 336($t0) #get the next pointer to the right
jal printpreorder #recurse to see if it's the last one
donepo:
lw $ra, 0($sp) #if we're done, pop our stack
lw $t1, 4($sp) #clean it up
addi $sp, $sp, 12 #8 bytes worth
jr $ra #and return
goprintpo:
li $v0, 4 #Print ID:
la $a0, id
syscall
li $v0, 1 #Print the ID stored at $s6 [Offset: 0]
lw $a0, 0($s6)
syscall
li $v0, 4 #Print Year:
la $a0, year
syscall
li $v0, 1 #Print the Year stored at $s6 [Offset: 4]
lw $a0, 4($s6)
syscall
li $v0, 4 #Print Title:
la $a0, title
syscall
li $v0, 4 #Print the Title stored at $s6 [Offset: 8]
la $a0, 8($s6)
syscall
li $v0, 4 #Print Description:
la $a0, description
syscall
li $v0, 4 #Print descript stored at $s6 [Offset: 72]
la $a0, 72($s6)
syscall
j afterprintpo
exit:
li $v0, 4 #Say
la $a0, goodbye #Goodbye!
syscall
li $v0, 10 #your part end here
syscall
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.