Instructions
In this homework you will write a program to generate a preorder traversal of a binary search tree from given inorder and postorder traversals using RISC-V. Here is a very simple template.
Input
The input is given by one integer and two array of integers in form of data in data section,
input_size:
.word 4
input_inorder:
.word 1
.word 2
.word 3
.word 4
input_postorder:
.word 1
.word 2
.word 4
.word 3
or in equivalent form of global variable in c language.
int input_size = 4;
int input_inorder[] = {1, 2, 3, 4};
int input_postorder[] = {1, 2, 4, 3};
input_size is the size of both input_inorder and input_postorder, which contain inorder and postorder of a same tree respectively. For example, the previous input specify the following tree.
3
/ \
2 4
/
1
The numbers representing nodes are not necessarily continuous or positive. Output
The output will consist of one single line with input_size number of integers representing the preorder traversal of the binary search tree.
For example the output of the program given the input above would be
3214
Notice that each number is separated by exactly one space, and at the end of the line, there are exactly one space and one line break ('\n'). Any output in other format will be rejected.
Some advice
learn recursive functions
learn save and Load from Memory using RISC-V it is helpful writing in C first write comments
Execution
We will test your program using RISC-V emulator venus. You probably want to read this before you started.
Submission
You need to follow the RISC-V integer register convention and the RISC-V integer calling convention.
You need to have meaningful comments not less than 50% of the total lines of code you wrote. A comment is defined by a sentence followed by #.
You should submit exactly one file, hw3.s. Any other file found will result in a score of zero. Submission containing any of input_size, input_inorder or input_postorder label will be rejected.
soerensch AT shanghaitech.edu.cn>
cd_wang AT outlook.com>
Last modified: 2020-03-11
