Shaun Conlon
CS 211
Section 6
2/13/2003 Notes

Topics for this week:
-tree traversals (preorder, postorder, inorder)
-intro. to expression tree parsing

1) Tree traversals:

You should remember the order for preorder, postorder and inorder:

preorder: node, left subtree, right subtree
postorder: left subtree, right subtree, node
inorder: left subtree, node, right subtree

Here is an example:

                      4
                    /    \
                   2      6
                  / \    / \
                 1   3  5   8

The traversals for this tree are:
pre: 4, 2, 1, 3, 6, 5, 8
post: 1, 3, 2, 5, 8, 6, 4
in: 1, 2, 3, 4, 5, 6, 8

2) Intro. to expression tree parsing

We can create trees out of PIEs as follows:

All binary operators become roots of a subtree with two branches, one for each 
subexpression.  The unary - opeator is the root of a subtree with the 
expression as the only branch.  Integers are leaves.

Here is an example:

((5 - (- 4)) + (6 * 3))

                          +
                        /    \
                       -      *
                      / \    / \
                     5  -   6   3
                        |
                        4

Notice the pre, post and inorder traversals of this tree:
pre: +-5-4*63
post: 54--63*+
in: 5--4+6*3

These are the pre- and post- order versions of the expressions, and with proper 
parentesis, the original PIE!

You should be able to relate the tree to the rules for PIEs for A3 (recall the 
rules E -> int, E -> (- E), E -> (E op E)).

Email me (sc235) if you have any questions.