Chapter 2: Mathematical Preliminaries J;1 51
By adopting the following convention, we can simplify Fig. 2.8. The root
is at the top. The directed edges are represented by arrows pointing downwards.
As all the arrows point downwards, the directed edges can be simply
represented by lines sloping downwards, as illustrated in Fig. 2.9.
Fig. 2.9 Representation of an ordered directed tree.
Note: An ordered directed tree is connected (which follows from T 2 ). It has
no circuits (because of T 3 ). Hence an ordered directed tree is a tree (see
Definition 2.17).
As we use only the ordered directed trees in applications to grammars, we
refer to ordered directed trees as simply trees.
Defmition 2.19 A binary tree is a tree in which the degree of the root is 2 and
the remaining vertices are of degree 1 or 3Note: In a binary tree any vertex has at most two successors. For example, the
trees given by Figs. 2.11 and 2.12 are binary trees. The tree given by Fig. 2.9
is not a binary tree.
Theorem 2.5 The number of vertices in a binary tree is odd.
Proof Let n be the number of vertices. The root is of degree 2 and the
remaining n - 1 vertices are of odd degree (by Definition 2.19). By
Theorem 2.4, n - 1 is even and hence 11 is odd. I
We now introduce some more terminology regarding trees:
(i) A son of a vertex v is a successor of 1'.
(ii) The father of v is the predecessor of 1'.
(iii) If there is a directed path from v] to 1'2> VI is called an ancestor of V.:,
and V2 is called a descendant of V1' (Convention: v] is an ancestor of
itself and also a descendant of itself.)
(iv) The number of edges in a path is called the length of the path.
(v) The height of a tree is the length of a longest path from the root. For
example, for the tree given by Fig. 2.9, the height is 2. (Actually there
are three longest paths, 1'1 -+ 1'2 -+ V.., 1'1 -+ 1'3 -+ VS, VI -+ V2 -+ V6'
Each is of length 2.)
(vi) A vertex V in a tree is at level k if there is a path of length k from the
root to the vertex V (the maximum possible level in a tree is the height
of the tree).
By adopting the following convention, we can simplify Fig. 2.8. The root
is at the top. The directed edges are represented by arrows pointing downwards.
As all the arrows point downwards, the directed edges can be simply
represented by lines sloping downwards, as illustrated in Fig. 2.9.
Fig. 2.9 Representation of an ordered directed tree.
Note: An ordered directed tree is connected (which follows from T 2 ). It has
no circuits (because of T 3 ). Hence an ordered directed tree is a tree (see
Definition 2.17).
As we use only the ordered directed trees in applications to grammars, we
refer to ordered directed trees as simply trees.
Defmition 2.19 A binary tree is a tree in which the degree of the root is 2 and
the remaining vertices are of degree 1 or 3Note: In a binary tree any vertex has at most two successors. For example, the
trees given by Figs. 2.11 and 2.12 are binary trees. The tree given by Fig. 2.9
is not a binary tree.
Theorem 2.5 The number of vertices in a binary tree is odd.
Proof Let n be the number of vertices. The root is of degree 2 and the
remaining n - 1 vertices are of odd degree (by Definition 2.19). By
Theorem 2.4, n - 1 is even and hence 11 is odd. I
We now introduce some more terminology regarding trees:
(i) A son of a vertex v is a successor of 1'.
(ii) The father of v is the predecessor of 1'.
(iii) If there is a directed path from v] to 1'2> VI is called an ancestor of V.:,
and V2 is called a descendant of V1' (Convention: v] is an ancestor of
itself and also a descendant of itself.)
(iv) The number of edges in a path is called the length of the path.
(v) The height of a tree is the length of a longest path from the root. For
example, for the tree given by Fig. 2.9, the height is 2. (Actually there
are three longest paths, 1'1 -+ 1'2 -+ V.., 1'1 -+ 1'3 -+ VS, VI -+ V2 -+ V6'
Each is of length 2.)
(vi) A vertex V in a tree is at level k if there is a path of length k from the
root to the vertex V (the maximum possible level in a tree is the height
of the tree).