Objectives of this lab:

        Write a recursive procedure that traverses a tree and prints
        the secret message in it.

        Use macros to simplify some of the steps in writing a
        procedure call.

	Master memory access by indexing an array of data structures.

Preparation

	Read lab lecture notes.

Understand Trees

In this lab we abuse the notion of a binary tree. A binary tree is normally used to provide rapid access to sorted information of some kind. Binary trees therefor have an ordering inherent in their construction. In this lab a secret message has been stored in a tree an it is you job to traverse it in the correct manner and print the message. 3 tree diagrams illustrating pre, post, and in order tree traversal go here. More explanation of tree concepts needed.

Tree Nodes

As an assembly programmer it is your job to understand how your data structures are layed out. To implement the tree we need a node data structure that holds:

1. Data
2. Location of left child
3. Location of right child

The following diagram illustrates just such a data structure. Its basic layout is reiterated in the comments of the program.

Your lab instructor has already set up the array of nodes for this program. You will use math to figure out the address to print the string, and the addresses of the indices for the right and left nodes.

The indices for the left and right children indicate positions in the array of nodes. To access a node you will need to multiply its index by the size of a node in bytes (8) and add the result to the base address of the array of nodes. A value of 0 indicates a dead end - do not traverse - because no node should link back to the root of the tree.

Lab Assignment

Complete the recursive procedure called traverse. Use the algorithm in the comments to help you.

Get the program here.

Notice that it uses m4 macros. Refer to the macro lab if you need help processing macros.

You will hand in the following:

1. The source code in the files printLib.m4, stackOps.m4, reverse.s, reverseMac.m4, and reverseMac.s
2. For each of reverse.s and reverseMac.s
• The print out of the screen shot (print screen) to show the program has been successfully loaded
• The print out of the screen shot of the console dislaying the results.

This page last modified:

Accessed     times.

CS Dept Home Page

CS Dept Class Files

CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.