CPS 100, Spring 2000, Test 1 Redux

For credit you must turn in written (or typed) solutions to these problems in person on or before 2:00 pm on Wednesday, March 1. Please make sure your name is on your work and that you've signed the honor code pledge.

Name ____________________   Login _________

Section ________________

Pledge _________________

There are four questions here, the first two are repeated from the test. If you do the questions that are repeated, your new version can replace what you did on the test. The last two questions will be added to the test. If you don't do these other questions your test score will be affected (for the worse).

You are expected to work without consulting any human. You can use books, notes, and programs from class but you cannot search the web or ask for assistance from any human or machine.

1. Swap Shop (repeated from test)

   Write the function swapCopy that creates a new tree that's a swapped copy of its parameter and returns a pointer to the root of the new tree. In a swapped copy, nodes with two-children are copied by interchanging the copies of the left and right subtrees. Nodes with no children or one child are simply copied (no swapping).

   

   For the tree above, the swapped copy is shown below.

   

   Use the header below.

   Tree * swapCopy(Tree * t) // post: returns a pointer to the root of a tree that's a swapped copy of t
2. Why the Oak Room? Two parts (repeated from test)

   A tree S is a subset of another tree T if every value of S is contained in T. There may be values in T that are not in S, but every value stored in S must also stored in T for S to be a subset of T. The empty tree is a subset of every tree (there are no values in the empty tree not in another tree). For search trees, the function below correctly determines if a single value is contained in a tree.

   bool contains(Tree * t, const string& s) // pre: t is a search tree // post: returns true if t contains s, else return false { if (t == 0) return false; else if (t->info == s) return true; else if (t->info < s) return contains(t->right,s); else return contains(t->left,s); }

   Part A

   Write the function subset that returns true if search tree s is a subset of search tree t, and returns false otherwise.

   Hint: traverse s in any order calling contains

   bool subset(Tree * s, Tree * t) // pre: s and t are both search rees // post: returns true if s is a subset of t, false otherwise Part B

   What is the complexity of the code you wrote in Part A. In answering the question assume s contains n nodes and t contains m nodes, and that trees are roughly balanced (average case). The answer should be in terms of both n and m. Justify your answer briefly.

3. Jack and the Beanstalk (6 points)

   The function height below correctly satisfies its postcondition, returning a string that represents the height of its parameter t. For example, for the tree below the function will return the string "RLLR"

   

   #include <iostream> #include <string> using namespace std; struct Tree { string info; Tree * left; Tree * right; Tree(const string& s, Tree * lptr, Tree * rptr) : info(s), left(lptr), right(rptr) { } }; string height(Tree * t) // post: returns a string representing the height of t // in the form "LRLLRRR..RL" where the length // of the string is the height of t and the letters // indicate the path from the root to one of the deepest // leaves { if (t == 0) return ""; string left = height(t->left); string right = height(t->right); if (left.length() > right.length()) { return "L" + left; } else { return "R" + right; } }

   Write a different function heightII that returns (via a reference parameter) a tvector of pointers so that for the original call of heightII, t[0] is the root, t[t.size()-1] is a deepest leaf, and t[k] is the child of t[k-1] on the path that represents the height from the root to a deepest leaf.

   The picture below shows the vector returned for the tree shown.

   

   For full credit your function should run in time O(N) for an N-node tree. You can call height and you can write other functions and call them.

   void heightII(Tree * t, tvector<Tree *> & tv) // post: tv holds nodes that represent the path that's the // height of t

4. Trees Again (6 points) Write the function vec2tree that returns a balanced binary search tree storing the same values that are in a sorted vector passed to the function. It's suggested that you write the auxiliary function vectreehelper shown below, but you don't have to.

   For each node N in the tree returned, the size (number of nodes) in N's left subtree should be roughly the same as the size of N's right subtree.

   For full credit your function should run in O(N) time for an N-node tree.

   Tree * vectreehelper(const tvector<string> & a, int first, int last) // pre: first <= last and a[first]<= ... <= a[last] (a is sorted) // post: returns a balanced search tree storing same values in // a[first] ... a[last] { } Tree * vec2tree(const tvector<string> & a) // pre: a is sorted, contains a.size() elements // post: returns a balanced search tree storing same values // in a { return vectreehelper(a, 0, a.size()-1); }