На этом шаге мы приведем различные типы древовидных структур.

Можно определить огромное количество различных типов древовидных структур (по [1, с.188-189]).

Рассмотрим несколько примеров.

Деревья, содержащие информацию в листьях, а не в узлах:
```
   data Tree2 a = Leaf2 a | Node2 (Tree2 a) (Tree2 a)
```
Деревья, в которых информация типа a размещена в узлах, а информация типа b - в листьях:
```
   data Tree3 a b = Leaf3 b | Node3 (Tree3 a b) (Tree3 a b)
```
Деревья, в которых из каждого узла выходят три ветви:
```
   data Tree4 a = Leaf4 | Node4 (Tree4 a) (Tree4 a) (Tree4 a)
```
Деревья, в которых число ветвей, исходящих из узла, является переменной величиной:
```
   data Tree5 a = Node5 a [Tree5 a]
```
(в данном примере дерева нет необходимости отдельно определять листья, поскольку в качестве таковых могут быть использованы узлы, не содержащие исходящих ветвей);
Деревья, в которых каждый узел имеет только одну ветвь:
```
   data Tree6 a = Leaf6 | Node6 a (Tree6 a)
```
(такой пример дерева по сути является списком, поскольку имеет линейную структуру);

Деревья с различными видами узлов:

   data Tree7 a b =  Leaf7a b
                   | Leaf7b Int
                   | Node7a Int a (Tree7 a b) (Tree7 a b)
                   | Node7b Char (Tree7 a b)

⁽¹⁾Роганова Н.А. Функциональное программирование. - М: ГИНФО, 2002. - 260 с.

На следующем шаге мы рассмотрим несколько демонстрационных примеров.

Предыдущий шаг Содержание Следующий шаг