Java Reference
In-Depth Information
FIGURE 24-9
(a) A general tree; (b) an equivalent binary tree; (c) a more
conventional view of the same binary tree
(a)
(b)
A
A
C
B
C
D
B
D
E
F
G
I
J
E
F
G
H
I
J
H
(c)
A
B
E
C
F
G
D
H
J
I
C
HAPTER
S
UMMARY
•
A node in a binary tree is an object that references a data object and two child nodes in the tree.
•
A basic class of binary trees contains methods common to all trees:
getRootData
,
getHeight
,
getNumberOfNodes
,
isEmpty
,
clear
, and various traversals. The basic class also has a method that sets the root and subtrees of an
existing binary tree to given values.
•
The implementation of
getHeight
and
getNumberOfNodes
is easier if the class of nodes has similar methods.
•
Preorder, postorder, and inorder traversals have simple recursive implementations. But to implement a traversal as
an iterator, you must use an iterative approach, since an iterator needs to be able to pause during the traversal. You
use a stack for preorder, postorder, and inorder traversals; you use a queue for a level-order traversal.
•
You can derive a particular binary tree, such as an expression tree, from the class of basic binary trees.
•
A node in a general tree is an object that references its children and a data object. To accommodate any num-
ber of children, the node can reference a list or a vector, for example. An iterator can provide access to the
children. In this way, the node contains only two references.
•
Instead of creating a general node for a general tree, you can use a binary tree to represent a general tree.
