5. Binary tree and reverse Polish
The reverse Polish expression in this example is : 6 4 5 + * 25 - 2 3 + /
The algorithm to use to derive the reverse Polish expression is listed below
- Traverse the left sub tree until there isn't one
- Traverse the right sub tree (if there is one)
- Re-visit the root of the current branch
- Repeat 1,2,3 until every node has been visited.
This is called the 'postorder' algorithm. The algorithm is an example of recursion because it repeats the same set of actions at every node.
The flash movie below shows how the algebraic expression in reverse polish format can be derived by following this algorithm
It is possible to also derive the expression in reverse polish by using another algorithm called the preorder algorithm. This is
- Visit the root node
- Visit the left branch
- Visit the right branch
Challenge see if you can find out one extra fact on this topic that we haven't already told you
Click on this link: post-order algorithm
Copyright © www.teach-ict.com