Lab Assignment 10

Topic: Tree Grafting 2
Source Code: graft2.cpp
Live Archive Ref#: 3821

Pre-lab Due:

Tuesday April 17 by the start of class
Submission Deadline: Friday, 27 April 2016, 11:59pm

Techniques:

Recursion, Tree traversals

More Information:

General information about labs, testing, judging utility

Collaboration Policy

The pre-lab requirement must be completed and submitted individually.

The remainder of the lab activity should be completed working in pairs. One person should submit the result, making sure that both partners' names are clearly identified in that submission.


Pre-Lab Requirement

Read the complete problem description and then determine what the expected output should be if given the following input:
Prelab input: Prelab output:
dddududuuu
dduudduduu
duddduduuu
#


Tree Grafting 2

Trees have many applications in computer science. Perhaps the most commonly used trees are rooted binary trees, but there are other types of rooted trees that may be useful as well. One example is ordered trees, in which the subtrees for any given node are ordered. The number of children of each node is variable, and there is no limit on the number. Formally, an ordered tree consists of a finite set of nodes T such that

Also, define root(T1), ..., root(Tm) to be the children of root(T), with root(Ti) being the i-th child. The nodes root(T1), ..., root(Tm) are siblings.

It is often more convenient to represent an ordered tree as a rooted binary tree, so that each node can be stored in the same amount of memory. The conversion is performed by the following steps:

  1. remove all edges from each node to its children;
  2. for each node, add an edge to its first child in T (if any) as the left child;
  3. for each node, add an edge to its next sibling in T (if any) as the right child.

This is illustrated by the following:

         0                             0
       / | \                          /
      1  2  3       ===>             1
        / \                           \
       4   5                           2
                                      / \
                                     4   3
                                      \
                                       5
In most cases, the height of the tree (the number of edges in the longest root-to-leaf path) increases after the conversion. This is undesirable because the complexity of many algorithms on trees depends on its height.

You are asked to write a program that computes the height of the tree before and after the conversion.

Input

The input is given by a number of lines giving the directions taken in a depth-first traversal of the trees. There is one line for each tree. For example, the tree above would give dudduduudu, meaning 0 down to 1, 1 up to 0, 0 down to 2, etc. The input is terminated by a line whose first character is #. You may assume that each tree has at least 2 and no more than 10000 nodes.

Output

For each tree, print the heights of the tree before and after the conversion specified above. Use the format:

Tree t: h1 => h2
where t is the case number (starting from 1), h1 is the height of the tree before the conversion, and h2 is the height of the tree after the conversion.

Example input: Example output:
dudduduudu
ddddduuuuu
dddduduuuu
dddduuduuu
#
Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4

Submit

One member of the team should submit the file graft2.cpp via git. Please make sure that the names of both members of the team are included in the email and in the comments at the beginning of the source code.


Hints

Upon first glance, this problem seems like it's going to require you to build a tree data structure and then implement the conversion from the general tree to the binary tree. But as is the case with many of these contest problems, there's a much easier way.

It is possible to compute the resulting depths without ever building the trees. We suggest a recursive approach. In the end we want a function that can compute the depth of the entire tree; we will design a recursion that computes the depth of any subtree. Consider the following local view:

If you were told the traditional depths for each of the four children, can you compute the traditional depth of the larger subtree? Consider the "converted" case. If you were told the "converted" depth for each of the four children, can you determine the converted depth for the larger subtree?

Here is how we recommend setting up the recursion. Remember that the original input is just a sequence of 'd' and 'u' designators to describe the shape of the tree. We want to think about starting the recursion at the root. Technically, there is no 'd'/'u' pair in the input for going down to the root up up from it, but for consistency sake, we recommend that you alter the original input string by adding a preceding 'd' and a trailing 'u'.

There are several strategies you might use in order to compute BOTH versions of the depth. One is to have two separate recrusive functions

int originalDepth(string::iterator& i);
int modifiedDepth(string::iterator& i);
and then call each of them from within main (although note well that you will need to reset the iterator to the beginning of the string before the second call). Given that we are in "contest mode" and just want to get this done, two separate functions is permissible.

Of course, the two functions will have almost the same logic in the way that parse the string and make recursive calls. The only difference is in how they use the information gathered about the children in determining their defined height. A slight improvement in design would be to code the function once, using an extra boolean parameter to denote which version of the logic you want to use.

int depth(string::iterator& i, bool converted);
With this design, you only need to code the core logic once, with some care to denote how the height calculation is done based on the boolean. But from within main, you will still need to call the function twice (once with coverted=false and once with converted=true).

The idea design would be to have a single function that simultaneously computes BOTH definitions of height during the same run, so that the string is only parsed once. Such a function can be coded with the signature

pair<int,int> depth(string::iterator& i);
so that the function is tasked with returning a pair of integers to represent the two notions of height. Similarly, each recursive call will be tasked with returning the pair of integers representing its subtree. See documentation for the C++ pair class for more technical details; that class is quite useful for experienced C++ programmers.