Java Reference
In-Depth Information
Root
R
Ancestors of V
Parent of V
P
V
S1 S2
C1
C2
C3
Siblings of V
Subtree rooted at V
Children of V
Figure6.1
Notation for general trees. Node P is the parent of nodes V, S1,
and S2. Thus, V, S1, and S2 are children of P. Nodes R and P are ancestors of V.
Nodes V, S1, and S2 are called siblings. The oval surrounds the subtree having V
as its root.
T
j
if i < j. By convention, the subtrees are arranged from left to right with subtree
T
0
called the leftmost child of R. A node's out degree is the number of children for
that node. A forest is a collection of one or more trees. Figure 6.1 presents further
tree notation generalized from the notation for binary trees presented in Chapter 5.
Each node in a tree has precisely one parent, except for the root, which has no
parent. From this observation, it immediately follows that a tree with n nodes must
have n 1 edges because each node, aside from the root, has one edge connecting
that node to its parent.
6.1.1
An ADT for General Tree Nodes
Before discussing general tree implementations, we should first make precise what
operations such implementations must support. Any implementation must be able
to initialize a tree. Given a tree, we need access to the root of that tree. There
must be some way to access the children of a node. In the case of the ADT for
binary tree nodes, this was done by providing member functions that give explicit
access to the left and right child pointers. Unfortunately, because we do not know
in advance how many children a given node will have in the general tree, we cannot
give explicit functions to access each child. An alternative must be found that works
for an unknown number of children.
