Geology Reference
In-Depth Information
Fig. A2.6 An example of
rooted tree of order 9
adjacency matrix of a rooted tree is easily
recognizable. We also note that the nodes of these
structures can be classified according to their
level . This quantity simply represents the distance
from the root node. The height of a rooted tree
is defined as the maximum number of levels
in the tree (including level zero). For example,
the rooted tree of Fig. A2.6 has height three. A
traversal of a tree structure is an algorithm that
visits each node once, independently from the
type of access that is performed to the nodes.
These algorithms have great practical importance
and derive from the DFS algorithm discussed
above. However, in this application the starting
node always coincides with the root and there
are two different traversal modes. In a preorder
traversal, access to each node is performed before
calling the depth search, whereas in a postorder
algorithm, data access is accomplished after
completion of depth search. Let T ( r )bearooted
tree with root r .If x 2 D is a node, we indicate by
T ( x ) the subtree obtained from T ( r ) after removal
of the incoming arc to x . Clearly, T ( x )isalsoa
rooted tree and its root is x .If J ( x )isthesetof
nodes y that can be reached in one step from x ,it
is easy to modify the recursive DFS algorithm to
the specific case of rooted trees.
1: 8 y 2 J ( x ), preorder ( T ( y ))
g
Algorithm A2 7 postorder ( x ): Postorder traver-
sal from a node x (recursive version).
Input: T ( x )
Output: Nessuno
f 0: 8 y 2 J ( x ), postorder ( T ( y ))
1: access ( x )
g
For both these algorithms, the function ac-
cess ( x ) represents any access procedure to the
data associated with node x . In the case of the tree
in Fig. A2.6 , the two algorithms would generate
the sequences:
Preorder W x 5 x 3 x 9 x 8 x 4 x 2 x 1 x 6 x 7
Postorder W x 9 x 8 x 4 x 3 x 2 x 6 x 7 x 1 x 5
These sequences imply an ordering criterion
within the sets J ( x ) for each x 2 D .Forexam-
ple, in the case of the rooted tree of Fig. A2.6 ,
we have: J ( x 5 ) Df x 3 , x 2 , x 1 g , thereby the subtrees
T ( x 3 ), T ( x 2 ), and T ( x 1 ) will be traversed in this
order. Clearly, any other ordering of the sets J ( x )
will produce a different sequence. In general, the
rooted trees are useful when the data must be
arranged according to a hierarchical order .In
plate kinematics, for example, this is the case
of the rotation models that describe the set of
kinematic relations between conjugate pairs of
tectonic plates.
Algorithm A26 preorder ( x ): Preorder traversal
from a node x (recursive version).
Input: T ( x )
Output: Nessuno
f 0: access ( x )
Search WWH ::




Custom Search