Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

238 BINARY TREES [CHAP. 10

Fig. 10-3 Converting a binary treeTinto a 2-tree

Algebraic Expressions and Polish Notation

LetEbe any algebraic expression which uses only binary operations, such as,

E=(a−b)/((c×d)+e)

ThenEcan be represented by a 2-tree as in Fig. 10-4(a) where the variables inEappear as the external nodes,
and the operations inEappear as internal nodes.

The Polish mathematician Lukasiewicz observed that by placing the binary operation symbol before its
arguments, e.g.,

+abinstead ofa+b and /cdinstead ofc/d

one does not need to use any parentheses. This notation is calledPolish notation in prefix form. (Analogously,
one can place the symbol after its arguments, calledPolish notation in postfix form.) RewritingEin prefix form
we obtain:

E=/−ab+×cde

Observe that this is precisely the lexicographic order of the vertices in its 2-tree which can be obtained by scanning
the tree as in Fig. 10-4(b).

Fig. 10-4