/hs3-lab

Задание на третью лабораторную работу

Primary LanguageHaskellMIT LicenseMIT

hs3-lab

Задание на третью лабораторную работу

###Реализовать:

  1. Тип данных для представления произвольного дерева
  2. Функцию обработки дерева в соответствии с вариантом задания
  3. Функцию генерации случайного дерева. Для получения последовательности случайных чисел можно использовать генератор псевдослучайных чисел типа StdGen и функцию random, или функции получения случайных значений из внешнего мира randomIO, randomRIO, и т.д. В первом случае сложность может возникнуть в правильной передаче нового состояния вашего генератора дальнейшим вычислениям. В этом случае удобно обернуть генерирующие функции в монаду State. Во втором случае придётся работать внутри монады IO, что может быть неприятно. Номера заданий такие же, как и в первой лабораторной работе. Для многих заданий полезно опередить дерево как экземпляр класса Monoid

Номера вариантов совпадают с первой лабораторной.

###Тесты Нужно будет написать тесты, в которых проверить работу программы на нескольких модельных примерах, показывающих правильность реализованного алгоритма, а также на случайно сгенерированном дереве.

###Определения Глубиной вершины дерева называется длина пути в эту вершину из корня. Глубиной (высотой) дерева называется максимальная глубина его вершин. Листом или терминальной вершиной дерева называется вершина, не имеющая поддеревьев. Степенью вершины называется число исходящих из неё ветвей. Степенью дерева называется максимальная степень его вершин. Шириной уровня дерева называется число вершин на данной глубине. Шириной дерева называется максимальная ширина по всем уровням. Подобие деревьев отличается от равенства возможным несовпадением значений данных, хранящихся в узлах.

###Варианты заданий

  1. Определить ширину дерева
  2. Определить глубину максимальной вершины дерева
  3. Определить глубину дерева
  4. Определить степень дерева
  5. Определить число нетерминальных вершин дерева
  6. Определить число вершин дерева, степень которых совпадает со степенью дерева
  7. Определить уровень дерева, на котором находится максимальное число вершин
  8. Определить значение листа дерева, имеющего минимальную глубину
  9. Определить значение нетерминальной вершины дерева с максимальной глубиной
  10. Проверить, находятся ли во всех листьях двоичного дерева элементы со значениями в заданном диапазоне
  11. Определить число вершин дерева, степень которых совпадает со значением элемента
  12. Проверить монотонность возрастания ширины уровня дерева
  13. Проверить монотонность убывания ширины уровня дерева
  14. Проверить, является ли дерево линейным списком вершин
  15. Проверить, находятся ли все листья дерева на одном уровне
  16. Увеличить значения всех листьев дерева на их уровень
  17. Увеличить на единицу значения листьев дерева, находящихся на нечётных уровнях
  18. Добавить произвольный элемент в дерево
  19. Найти количество вхождений элемента в дерево
  20. Удалить элемент из дерева
  21. Проверить, является ли дерево симметричным (равным своему отражению)
  22. Проверить, является ли двоичное дерево самоподобным (подобным своему отражению)