SKEDSOFT

Postfix / Post-order: Traversing a binary tree using postfix or post-order means to trace the outline of the tree, again starting just to the left of the root node, and going downward. You identify node contents when the trace passes upward on the right side of the node. The root node is always the last node. Here is our example of 2 3:

2 3
One way to interpret this is: Using 2 and 3, add them together. This produces a result which at first looks like just the opposite of prefix/pre-order, but it is not. Notice that the sequence of the values is the same, but the placement of the operator has changed. This becomes more obvious when we perform the same operation on our other expression tree:

6 3 * 1 -
One way to interpret this is: using 6 and 3, multiply them, then using 1, subtract. (Still potentially confusing, but it gets better.)

Reverse Polish Notation (RPN): Similar to Polish notation, Reverse Polish Notation was invented in the 1950’s by Charles Hamblin. It uses Polish notation, and reverses part of the process, placing operators after the values or terms.

Stack Based Processing: It turns out that one of the most important operational structures in modern computers is something called a stack. In a stack, values can be placed or removed only from the “top”. There are commonly two operations which access the stack: push and pop3. The push operator places a value on the top of the stack, adjusting a memory pointer to the address. Usually, the address is just the next one in line, so the system only has to increment or decrement (depending on the system) to calculate the next storage location.

The pop operator uses the address defined by the push operator, and gets the value currently at that location. As part of the operator, the address is adjusted to its previous value by reversing the arithmetic of the push operation.

Arithmetic operations are performed by popping values from the stack, performing the calculation, and then pushing the result back onto the stack. A final operation pops the value on the stack for storage or display.

Thus, our operations for 2 3 could be translated into code…

PUSH 2
PUSH 3
ADD
DISPLAY
…and could look something like this: