Follow instructions in the link. You will need to call your file
recur1.am.
You can debug in Mars, or use mapp recur1 to produce
recur1.a and use qtspim recur1.a
When you are ready to test, you MUST use mapp and then mipsmark
recur1.a
You must submit recur1.a. You may also submit
recur2.am if you wish. Should it have a .include, then you
should also submit your .include file(s)
There is considerable setup already done for this programming question. A binary tree exists with exactly one node "marked." You must write a (recursive) function search that attempts to find the marked node. As your function traverses the tree, it must call store_path to record the results. It also needs to cease further searching once the marked node is found.
Providing your search works correctly and calls store_path properly, the main program will take care of printing the requred result, which is the path from the root to the marked node.
Each node is a record, or structure, consisting of 4 words. The
first 3 are addresses (also known as pointers.) * means
"points to" or "is the address of", as in C. See examples/tree.c or tree.cc
struct node // C++ - a struct is a type
{ string name; // a "fancy" type defined in C++
node *left; // pointers to subtrees
node *right;
int value; //{TRUE = 1 for the marked node}
};
typedef struct node_s // C -- a little bit awkward syntax
{ char * name;
struct node_s *left; // we'd like node*, but not defined yet
struct node_s *right;
int value;
} node; // now we can declare nodes:
node node2 = {"apple",0,0,0};
node root = {"orange",0,&node2,1}; /* has to come after subtree defs */
Remember that you must save registers $ra and any $s0..$s7 registers you want to use, on the stack, and restore them before returning. In programming a recursive function, you just describe what you do at one node. The recursion takes care of processing all the other nodes. The first thing to check is whether the node exists (is not nil = 0).
store_path is already written for you. It stores the path to the node you found in an array. To this end, you pass it 2 parameters:
It is fine to call store_path more than once with the same depth,
so long as the last time called for that depth is the node "on the
path."
The suggested algorithm given in the file does not test for null
pointers until the subtrees. This is fine, and saves some trivial
calls, but it might be easier to grasp an algorithm that tests the
pointer first, eliminating 2 if statements later on:
## The code for search could also look like:
## boolean search(tree, depth)
## if (tree is null) return 0 # test for null pointer right away, avoid if's later
## call store_path
## if (value == 1)
## return 1 # true
## if (search(left subtree, depth+1)) # if found on left, done!!!
## return 1
## return search(right subtree, depth+1) # else try to find it on right
0: 0-apple
/---------/ \--------\
1: 1-orange 2-banana
/ \ / \
2: 3-pear 4-plum 5-peach 6-nectarine
/ / \ / \
3: 7-pinapple 8-grapefruit 9-grape 10-melon 11-avocado
/ \
4: 12-star 13-mango
/ \
5: 14-passion 15-cantaloupe
/ \
6: 16-watermelon 17-apricot
See class notes on recursion , and tree traverse class example.
## ## Question: ## ## Write a function named search that will ## search for a node whose name matchs a desired string ## in a binary search tree. ## The string to be found will be input, or supplied by mipsmark. ## ## A search tree has the property that the left subtree ## of any node has entries that are "less" than the current ## node, and likewise the right subtree's entries are ## "greater", in this case by alphabetic ordering. ## ## I have attempted to make the tree defined in this ## data segment such a tree. ## ## The parameters to search are a pointer to the ## tree, a pointer to the string being sought, ## and the current depth. On each recursive ## call add 1 to the depth. This parameter is ## used to keep track of the path from the root ## to the marked node; as you visit a node, you ## will call a procedure named store_path to ## record the fact that you have visited this ## node. The code for store_path and print_path ## (called after you get back from the procedure) ## have been written for you -- all you need to ## do is understand how to set up the parameters ## for store_path and make the call. ## ## The code for search could look like: ## ## call store_path ## if (Name == seek) ## return Value #TRUE, found it ## if (seek < Name) AND (left tree exists) ## return search(left tree, depth+1, seek) ## else if (right tree exists) ## return search(right tree, depth+1, seek) ## return 0 ## ## You also need a function to COMPARE 2 STRINGS ## ## Output format should follow the pattern: ## "peachgt;-->avocado-->cantaloupe-->orange-->passion 80" ## or "cherry not found" ## Output format for this file's data must be: ## "peach-->pineapple-->pear 40" ## And case0 output should be: ## "peach 10"
## Question: ## ## Write a function named traverse that will ## do an preorder traverse of a binary tree. ## ## RETURN the sum of all fruit found ## ## The tree defined in the data segment such that ## an INorder traverse would be alphabetical ## in preorder, the root node will come first ## ## The argument to travrese is a pointer to ## a node of the tree, ## ## A node consists fo 4 words: ## name - address of string such as "apple" ## left - pointers to child nodes visit LEFT first ## right " " then RIGHT ## value - an integer, might represent number of apples, for example ## ## IMPORTANT!! ## A value of 0 indicates a dead branch. It has no apples, ## and any further branches will also be dead, ## so return the value 0 immediately ## ## The code for traverse could look like: ## ## if (pointer is null OR value is 0) return 0 ## print_name (name) ## val1 = traverse (left) ## val2 = traverse (right) ## return val1 + val2 + value # sum of all values found so far ## ## ## Output format should follow the pattern: ## "apple, apricot, orange, peach, pear, pineapple 42" ## ## ## Output format should follow the pattern: ## ""apple, apricot, orange, peach, pear, pineapple 42"
Back to CS 216 or Lin Jensen .
23 March 2000 rev. 8 March 2009, 17 Mar 2010 (to show C++ struct)