Information Technology Reference
In-Depth Information
An ordered unlabeled tree is representable by an expression built only by paren-
theses, for example:
((()())(()(()())))
.
In this case, the root correspond to the external parentheses. This root has two sons,
and they have two sons too. The second son of the second son branches again with
two nodes.
Every algebraic expression can be represented by a rooted tree. For example, the
following expression:
2
3
(((
2
+
3
)
×
5
)+(
×
5
))
can be represented by the tree given in Fig. 7.11.
Fig. 7.11
The tree diagram of the expression
(((
2
+
3
)
×
5
)+(
2
3
×
5
))
We can construct any tree by means of a
derivation
, developed in consecutive
steps
.Atany
step
, an element occurs which is either a leaf of the tree, or the father
of elements occurring at previous steps (#
i
is the element occurring at step
i
). The
following derivation provides, at its final step, the expression
2
3
(((
2
+
3
)
×
5
)+(
×
5
(for easier reading, numbers and operations decorating the nodes are indicated,
with the partial expressions corresponding to the steps):
))
1. 2
2. 3
3. 5
4. #1
+
#2 = (2 + 3)
5. #4
×
#3
=((
2
+
3
)
×
5
)
2
3
6. #1
ex p
#2
=
2
3
×
=(
×
)
7. #6
#3
5
2
3
+
= (((
+
)
×
)+(
×
))
8. #5
#7
2
3
5
5
.
