Types of tree traversal
The three tree traversal algorithms you need to know are: Pre order, In order and Post order.
Tree traversal algorithms essentially follow the same rules at each node they visit. This means in essence we can call the same subroutine on each node it visits making it suitable for recursion. The difference between
the three different tree traversal algorithms is simply where we output the data.
Reverse polish notation (RPN)
Reverse polish notation is a method of representing an arithmetic equation without the need for brackets. This makes it efficient for computer evaluation as it is highly suited to evaluating it with the use of a stack. RPN
is used in interpreters based on a stack for example Postscript and bytecode. The standard way we represent equations is known as infix notation.
If a computer were to evaluate the equation below:
x + (y - z)
First it needs to load y, then z and now take z from y, and finally store the result. Next it needs to load x, then add x to the result of y - z. This is
best described as:
y z - x +
The above example is reverse polish notation and easier for a computer to comprehend.
Evaluating RPN with stacks
Once an expression is in reverse polish notation there are a few simple steps to follow to evaluate it.
If the next item is an operand push it to the stack.
If it is an operator, remove the required number of operands,
perform the operation and return the result to the stack.
(2 + 1) x (7 - 3) becomes 2 1 + 7 3 - x
First 2 is pushed to the stack. Then 1 is pushed to the stack. An operator is encountered so the last two items are popped off the stack, the addition performed and the answer 3 returned to the stack. Next 7 is pushed to the
stack followed by 3. The operator - is encountered and so the last two numbers are popped off the stack and the subtraction performed with the result then returned to the stack. The operator x is encountered next, so the two
values are popped from the stac the multiplication performed and the result returned to the stack.
Binary expression trees
Our expression from the last example (2 + 1) x (7 - 3) can be represented as a tree. If you perform an in order traversal you get the original infix notation. If you perform a post order traversal you get reverse polish
notation.
