S4 g, Theory ofComputer Science
(b) Which vertices are the sons of 57
(c) Which vertex is the father of 57
(d) \Xlhat is the length of the path from 1 to 97
(e) What is the left-right order of leaves?
(f) What is the height of the tree?
2
10
7
8
o
Fig. 2.13 The directed tree for Example 2.18.
Solutions
(a) 10, 4, 9, 8, 6 are leaves. 1, 2. 3, 5, 7 are internal vertices.
(bi 7 and 8 are the sons of 5.
(c) 3 is the father of 5.
(d) Four (the path is 1 ~ 3 ~ 5 ~ 7 ~ 9).
(e) 10 - 4 - 9 - 8 - 6.
(f) Four (1 ~ 3 ~ 5 ~ 7 ~ 9 is the longest path).
2.3 STRINGS AND THEIR PROPERTIES
A string over an alphabet set 2: is a finite sequence of symbols from 2:.
NOTATION: 2:* denotes the set of all strings (including A, the empty string)
over the alphabet set 2:. That is, 2:+ = 2:* - {A}.
2.3.1 OPERATIONS ON STRINGS
The basic operation for strings is the binary concatenation operation. We
define this operation as follows: Let x and y be two strings in 2:*. Let us form
a new string :: by placing y after x, i.e. z = xy. The string z is said to be
obtained by concatenation of x and y.