You will find a MIPS assembly program BinaryTree.asm as downloadable code. You can assemble and run this program. It will prompt you to enter intege
Part A:
You will find a MIPS assembly program BinaryTree.asm as downloadable code. You can assemble and run this program. It will prompt you to enter integers until a 0 is entered, terminating the input. These integers are stored in Input. The call to BuildTree will build a Binary Search Tree from Input, where Root points to the root node of the tree. Each Node is laid out in the following format:
128270032385Left
Right
Data
Left
Right
Data
A node consumes 12 bytes, i.e. 3 words. The first 2 words hold pointers to other nodes in the tree while the last word will hold the integer payload. Note: that null is represented as -1 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.
Write the procedure InOrder which will traverse the tree yielding an InOrder output of the data values. This procedure will be recursive and must comply with the standards as taught in class.
Each recursive call will need an activation record. 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 66 44 75 21 57 79 39 24 will produce an InOrder output.
Part B
Consider the following fake student number 7654321. Take the last 5 digits and add in a radix point as follows 5.4321. Using the tool https://www.h-schmidt.net/FloatConverter/IEEE754.html create the FPS for that number. This will give you:
01000000101011011101001111000011
Or 1. 010110 x 22 with the hidden bit truncated to 7 bits.
Do the above exercise for your own student number. Each student should have a unique 7 bit number, with a corresponding exponent.
Multiply the above number by 1.000110 using the process shown in lecture. Be sure to show all steps, dont forget to calculate the exponent.
Verify, by dividing the result obtained in part a by 1.000110.
In both parts, be sure to show all steps, solutions obtained by magical means will not be awarded marks.
Part C A4 Course bonus + 2%
Rewrite the BuildTree procedure as a recursive method.
Submission
The TA will be running your program to ensure it is fully functional. Make the marker happy!!! If something is not working, then let the marker know. Be sure to properly comment your source code.
The End
