Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Prefix Notation

In prefix notation  the operator is written before its operands. Therefore, in order to print the prefix expression from an expression tree, preorder traversal is done. I.e., at every non-terminal node we do the following:

  1. Print the root; and then
  2. print a left parenthesis; and then
  3. traverse the left subtree; and then
  4. print a comma; and then
  5. traverse the right subtree; and then
  6. print a right parenthesis.
If we use this procedure to print the tree given in Figure gif we get the prefix expression


While this notation may appear unfamiliar at first, consider the result obtained when we spell out the names of the operators:

plus (div (a,b), times (minus (c,d), e))
This is precisely the notation used in a typical programming language to invoke user defined procedures plus, minus, times, and div.gif

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.