Информатика ← ЛабораторныеЛабораторная работа №23

Динамические структуры данных: деревья

Задание

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

  1. Добавление нового узла (для двоичного дерева положение нового узла определяется в соответствии с требованием сохранения порядка, для дерева общего вида должен задаваться путь до добавляемого узла, добавляемый узел становится младшим сыном).
  2. Текстовая визуализация дерева (значение каждого узла выводится на отдельной строке, с отступом пропорциональным глубине узла (шаг отступа --- 2 пробела), в порядке старшинства узлов).
  3. Удаление узла (двоичное дерево перестраивается в соответствии с требованием сохранения целостности и порядка; для дерева общего вида удаляется все поддерево, исходящее из удаляемого узла; 4. должно быть предусмотрено корректное освобождение памяти). вычисление значения некоторой функции от дерева (целой или логической) в соответствии с номером варианта.

Определения

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

Входные данные

На стандартный ввод программе подаются команды четырех типов:

p — печать дерева;
+ 2 (или +ssbb 2) — вставка в дерево (для дерева общего вида путь задается строкой, где r создание корня, s --- переход к старшему сыну, b --- переход к брату);
- 5 — удаление из дерева элемента со значением 5 (удаление первого найденного при обходе элемента со значением 5 и его поддерева);
t [params] — выполнение заданного вариантом действия. Параметры, если они есть, перечислены через пробел.

Выходные данные

После чтения и выполнения каждой команды программа должна вывести результат операции.

Распечатать дерево (для пустого дерева вывести «Empty»).
Вывести сообщение «OK» в случае успеха (если элемент уже есть в двоичном дереве, вывести «Exists», если в дереве общего вина не существует указанного пути, вывести «Error»).
Вывести сообщение «OK» при успешном удалении или «Not found», если элемента с таким значением в дереве нет.
Вывести вычисленное значение (для логических значений выводить true или false).

Варианты

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

Пример (дерево общего вида)

Входные данные:

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7
p
- 3
p 

Выходные данные:

OK (7 раз)
1
  2
    5
  3
    6
    7
  3
OK
1
  2
    5
  3

Пример (двоичное дерево поиска)

Входные данные:

+ 5
+ 2
+ 1
+ 3
+ 7
+ 6
p
- 3
p 

Выходные данные:

OK (6 раз)
    1
  2
    3
5
    6
  7
OK
    1
  2
5
    6
  7

Пример объявления и описания структуры дерева

typedef struct node node;

struct node
{
  int val;
  node *left;
  node *right;
};

typedef node *tree;

Печать дерева через обход правое-корень-левое (rRl):

void rRl(tree t, int l)
{
  if (t != NULL) {
    rRl(t->right, l + 1);
    printf("%*s%d\n", 4*l, " ", t->data);
    rRl(t->left, l + 1);
  }
  else
    printf("%*sNULL\n", 4*l, " ");
}

void printree(tree t)
{
  rRl(t, 0);
  printf("\n");
}