ВУЗ:
Составители:
47
Рис. 23. Прошитое бинарное дерево, представляющее лес из двух деревьев
Исходя из отмеченного выше естественного соответствия между ле-
сами и бинарными деревьями, идеи прохождения, изложенные для би-
нарных деревьев, можно применить к лесам (и, следовательно, к деревь-
ям). Известные нам три порядка прохождения принимают такой вид.
Прямой порядок: попасть в корень первого дерева, пройти поддере-
вья первого дерева (в прямом порядке), пройти оставшиеся деревья
(в прямом порядке).
Обратный порядок: пройти поддеревья первого дерева (в обратном
порядке), попасть в корень первого дерева, пройти оставшиеся деревья
(в обратном порядке).
Концевой порядок: пройти поддеревья первого дерева (в концевом
порядке), пройти оставшиеся деревья (в концевом порядке), попасть в
корень первого дерева.
Для того чтобы понять значение этих трёх методов прохождения,
рассмотрим следующую запись леса с помощью вложенных скобок:
(A (B, C (K)), D (E (H), F (J), G)) (31)
Эта запись соответствует нашему лесу из двух деревьев. В ней дере-
во представлено так, что сначала записан корень дерева, а затем пред-
ставлены его поддеревья аналогичным образом. Следовательно, пред-
ставлением непустого леса служит заключённый в скобки список пред-
ставлений его деревьев, разделяемых запятыми. Если наш лес проходится
в прямом порядке, то получается последовательность ABCKDEHFJG, а
это не что иное, как выражение (31) без скобок и запятых. Заметим, что
прямой порядок является династическим порядком. После смерти короля,
его титул переходит к его первому сыну, а затем к потомкам первого сы-
на, и если же все таковые умирают, то титул таким же самым образом
переходит к другим сыновьям этой семьи.
J
E
F
G
D
H
K
B
C
A
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
