You will find a MIPS assembly program BinTree.asm as downloadable code along with this assignment

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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:

Item

Left Right

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.

 

Attachments:

Expert's Answer

348 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of