Шаг 131.
Основы языка Haskell.
Рекурсивные типы данных. Бинарные деревья поиска. Понятие "лес"

    На этом шаге мы рассмотрим это понятие.

Определение [1, с.353] (содержательное).
  1. Лес - это множество деревьев (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев.
  2. Иногда для леса из n деревьев используется термин "дерево с n-кратным корнем".

    Приведём пример изображения леса:


Рис.1. Пример леса

    Между лесами и деревьями имеется следующая связь: если мы удалим у дерева корень, то получим лес, а определённым добавлением к любому лесу всего одного узла можно образовать дерево.


(1)Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы. - М.: Издательский дом "Вильямс", 2000. - 720 с.

    На следующем шаге мы рассмотрим бинарное (двоичное) дерево.




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