Java Reference
In-Depth Information
A
B
C
D
E
F
G
H
I
Figure5.8
Illustration of a typical pointer-based binary tree implementation,
where each node stores two child pointers and a value.
−
C
*
+
*
X
A
4
*
2
X
Figure5.9
An expression tree for 4x(2x + a) c.
Java allows us to differentiate leaf from internal nodes through the use of class
inheritance. A base class provides a general definition for an object, and a subclass
modifies a base class to add more detail. A base class can be declared for binary tree
nodes in general, with subclasses defined for the internal and leaf nodes. The base
class of Figure 5.10 is named
VarBinNode
. It includes a virtual member function
named
isLeaf
, which indicates the node type. Subclasses for the internal and leaf
node types each implement
isLeaf
. Internal nodes store child pointers of the base
class type; they do not distinguish their children's actual subclass. Whenever a node
is examined, its version of
isLeaf
indicates the node's subclass.
Figure 5.10 includes two subclasses derived from class
VarBinNode
, named
LeafNode
and
IntlNode
. Class
IntlNode
can access its children through
pointers of type
VarBinNode
. Function
traverse
illustrates the use of these
classes. When
traverse
calls method
isLeaf
, Java's runtime environment
determines which subclass this particular instance of
rt
happens to be and calls that
subclass's version of
isLeaf
. Method
isLeaf
then provides the actual node type
