[an error occurred while processing this directive]

<h2>
Expected Trees</h2>

Here are all 60 possible trees you should produce for question 9:

<pre>
tiger
   cat
      dog
   feline

tiger
   cat
      dog
   feline

tiger
   cat
   feline
      dog

tiger
   cat
   feline
      dog

tiger
   feline
      dog
   cat

tiger
   feline
      dog
   cat

tiger
   feline
   cat
      dog

tiger
   feline
   cat
      dog

feline
   tiger
      cat
         dog

feline
   tiger
      cat
         dog

feline
   tiger
      cat
      dog

feline
   tiger
      dog
      cat

feline
   tiger
      cat
         dog

feline
   tiger
      cat
         dog

feline
   tiger
      cat
   dog

feline
   tiger
      cat
   dog

feline
   dog
   tiger
      cat

feline
   dog
   tiger
      cat

feline
   tiger
      cat
         dog

feline
   tiger
      cat
         dog

feline
   tiger
      cat
      dog

feline
   tiger
      dog
      cat

feline
   tiger
      cat
         dog

feline
   tiger
      cat
         dog

dog
   tiger
      cat
      feline

dog
   tiger
      feline
      cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

dog
   tiger
      cat
      feline

dog
   tiger
      feline
      cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   feline
      tiger
         cat

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

dog
   cat
      tiger
         feline

cat
   tiger
      feline
         dog

cat
   tiger
      feline
         dog

cat
   tiger
      dog
      feline

cat
   tiger
      feline
      dog

cat
   tiger
      feline
         dog

cat
   tiger
      feline
         dog

cat
   dog
   tiger
      feline

cat
   dog
   tiger
      feline

cat
   tiger
      feline
   dog

cat
   tiger
      feline
   dog

cat
   tiger
      feline
         dog

cat
   tiger
      feline
         dog

cat
   tiger
      dog
      feline

cat
   tiger
      feline
      dog

cat
   tiger
      feline
         dog

cat
   tiger
      feline
         dog 
</pre>

Note that some pairs of trees print out identically.  For example,
<pre>
tiger
   cat
      dog
   feline

tiger
   cat
      dog
   feline
</pre>

This is because in tree 1 the dog is the left child of cat, and in tree
2 the dog is the right child of cat.  Our tree printing routine prints
them indistinguishably.

<p>
Other trees are isomorphically equivalent.  For example,
<pre>
tiger
   cat
   feline
      dog

tiger
   feline
      dog
   cat
</pre>
are equivalent &mdash; there is no meaning associated with being the
left or right child, so if we swap the order of the children of tiger
the two trees are equivalent.

<hr style="height:.5em;background-color:#c00;padding:0;">

<table border="0" rules="none" bgcolor="white" width="100%" align =
center cellpadding=6 cellspacing=2>
<tr>
<td valign="bottom">
<font size="-1">
<a href="http://www.cs.virginia.edu/evans/cs216/"><b>CS216: Program and Data Representation</b></a><br>
<a href="http://www.cs.virginia.edu/">University of Virginia</a><br>
</td>
<td align=right valign="bottom" width=25%>
<font size=-1>
<a href="http://www.cs.virginia.edu/evans/">David Evans</a><br>
<a href="mailto:evans@cs.virginia.edu"><em>evans@cs.virginia.edu</em></a><br>
<font size="-2"><a href="http://www.cs.virginia.edu/evans/cs216/reuse.html">Using these Materials</a></font>
</font>
</td>
</tr>
</table>

</font>

</body>
</html>