Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 221

The post-order traversal can be used in conjunction with a stack to evaluate the expression. The algorithm is as
follows:

initialize a stack, S, to empty
while we have not reached the end of the traversal
get the next item, x
if x is an operand, push it onto S
if x is an operator
pop its operands from S,
apply the operator
push the result onto S
endif
endwhile
pop S; // this is the value of the expression

Consider the post-order traversal: 54 37 + 72 5 13 * - / . It is evaluated as follows:

The next item is 54 ; push 54 onto S ; S contains 54 . 1.

The next item is 37 ; push 37 onto S ; S contains 54 37 (the top is on the right). 2.

The next item is + ; pop 37 and 54 from S ; apply + to 54 and 37 , giving 91 ; push 91 onto S ; S
contains 91 .

3.

The next item is 72 ; push 72 onto S ; S contains 91 72 . 4.

The next items are 5 and 13 ; these are pushed onto S ; S contains 91 72 5 13 . 5.

The next item is * ; pop 13 and 5 from S ; apply * to 5 and 13 , giving 65 ; push 65 onto S ; S
contains 91 72 65 .

6.

The next item is - ; pop 65 and 72 from S ; apply - to 72 and 65 , giving 7 ; push 7 onto S ; S
contains 91 7 .

7.

The next item is / ; pop 7 and 91 from S ; apply / to 91 and 7 , giving 13 ; push 13 onto S ; S
contains 13 .

8.

We have reached the end of the traversal; we pop S , getting 13 —the result of the
expression.

9.

Note that when operands are popped from the stack, the first one popped is the second operand, and the second
one popped is the first operand. This does not matter for addition and multiplication but is important for subtraction
and division.

8.4 Representing a Binary Tree
As a minimum, each node of a binary tree consists of three fields: a field containing the data at the node, a pointer to
the left subtree, and a pointer to the right subtree. For example, suppose the data to be stored at each node is a word.
We can begin by writing a class ( TreeNode , say) with three instance variables and a constructor that creates a TreeNode
object.

class TreeNode {
NodeData data;
TreeNode left, right;