+
    /   \
   6     -
       /   \ 
      *     9
     / \
    4   3

So the answers are...

Preorder  - output = +6-*439
Inorder   - output = 6+4*3-9
Postorder - output = 643*9-+

Hmmmm...  this is interesting.  So inorder traversal prints out the tree as if you were evaluating
some mathematical expression.  The preorder and postorder traversals yield notations called
prefix and postfix notation (respectively) for expressions.

As you may know from lecture, the tree above represents the expression 6+(4*3)-9.  If you're
working with the grammar presented in assignment 2, it would be (6 + ((4 * 3) - 9)).  This method 
of working with binary trees to evaluate expressions is called EXPRESSION PARSING, which you will 
be doing in assignment 3.

Assume we have no unary operators (like negative signs, etc.).  Notice then that every vertex has 
either 0 or 2 children.  If a node has 0 children (also called a LEAF), then it
must be a number (why?  Think about it...)  If a node has 2 children, then the node must contain
a binary operator (again, think about why this is).  Every time we encounter a binary operator in
a tree, we should look at it this way...

   +
  / \
 E1  E2

where E1 and E2 are separate expressions represented by subtrees.  Thus, this tree is evaluated to
(E1 + E2).  If we extend the tree such that E1 = (6 * 4), the tree would look like...

     +
   /   \
  *     E2
 / \
6   4

and if E2 = (E3 - 4) and E3 = (1 # 8), then we would get the tree...

     +
   /   \
  *     -
 / \   / \
6   4 #   4
     / \
    1   8

Therefore, the entire tree is equivalent to the expression ((6 * 4) + ((1 # 8) - 4))
-----------------------------------------------------------------------------------------------------

Makes sense?  If not, shoot me some mail... rgl8@cornell.edu