Вернигор Виталий ТК-3

Задача: 4. Бінарна куча. Для заданого масиву ключів (більше 15 значень, задати випадково – цілі числа з множини [0, 100]) побудувати бінарну кучу, реалізувати операції додавання елемента, видалення мінімального елемента. Вивести побудовані дерева. Описание: Реализуется структура данных с абстрактным типом данных. Для хранения вершин используется ArrayList. Для каждой вершины под номером i её левый сын хранится в 2i+1 вершине, а правый — в 2i+2 вершине.

Класс содержит следующие методы:

Heap() — конструктор.

shiftUp() — восходящее восстановление свойства кучи. Сложность: О(Log(n))

shiftDown() — нисходящее восстановление свойства кучи. Сложность: О(Log(n))

insert() — добавление элемента в кучу.

delete() — удаление первой вершины. Сложность: О(Log(n))

size() — размер кучи.

isEmpty() — проверка на пустоту.

toString() — преобразование в строку.

max() — максимальный элемент. Сложность: О(1)

print() — вывод кучи на экран.

Задача: 2. Бінарне дерево пошуку. Для заданого масиву ключів (більше 15 значень, задати випадково – цілі числа з множини [0, 100]) побудувати бінарне дерево пошуку, реалізувати всі варіанти обходів (прямий, обернений, симетричний). Вивести побудоване дерево і результати обходів. Описание: Класс Node хранит значение и ссылки на дочерние элементы (Левый и правый). Класс BinaryTree реализует модель бинарного дерева поиска

.addRecursive() Рекурсивный метод вставки элементов.

.add() - безопасный вызов .addRecursive

.createBinaryTree() - конструктор (Сейчас содержит тестовый набор элементов, которые можно заменить по желанию)

.containsNodeRecursive() - Рекурсивный метод поиска элемента.

.containsNode() - безопасный запуск .containsNodeRecursive()

.deleteRecursive() - Удаляет элемент из дерева. есть 3 основных случая:

1. Узел не имеет дочерних элементов - (самый простой случай) Заменяет этот узен на null у родительского узла
2. У узла есть только один дочерний элемент - ** в родительском узле,меняет местами узел со своим единственным ребенком.
3. У узла есть два потомка - (самый сложный случай) реорганизация дерева

.delete() - безопасный запуск .deleteRecursive()

.findSmallestValue() - Находит наименьший узел для замены в операции удаления.

Операции поиска (Обхода) дерева:

.traverseInOrder() - поиск в глубину, левое поддерево > корень > правое поддерево

.traversePreOrder()- поиск в глубину, корень > левое поддерево > правое поддерево

.traversePostOrder()- поиск в глубину, левое поддерево > правое поддерево > корень

.traverseLevelOrder() - поиск в ширину, посещает все узлы уровня перед переходом на следующий уровень.

Задача: 5. Біноміальні кучі. Для заданого масиву ключів (більше 15 значень, задати випадково – цілі числа з множини [0, 100]) побудувати біноміальну кучу, реалізувати операції додавання елемента, видалення мінімального елемента. Вивести побудовані дерева. Описание:

Класс BinomialHeap содержит реализацию биномиальной кучи

Класс BinomialHeapNode содержит экземпляр нода для кучи

BinomialHeapTest содержит все необходимое для тестового запуска алгоритма

Задача: 3. Червоно-чорне дерево. Для заданого масиву ключів (більше 15 значень, задати випадково – цілі числа з множини [0, 100]) побудувати червоно-чорне дерево, реалізувати операції додавання елемента, видалення елемента. Вивести побудовані дерева.

Задача:

1. Кодування Хаффмана. Взяти фрагмент тексту (не менше 100 символів). Реалізувати алгоритм кодування Хаффмана. Отриману систему кодування представити у вигляді дерева. Описание: Текст помещённый в input.txt преобразовывается в двоичный с помощью алгоритма кодировки Хаффмана Если отсутствует файл - пользователю предлогается ввести текст вручную. Есть возможность декодировать полученный код, дабы убедиться в его корректности. Управление:

[-1] Завершение

[1] Вод нового текста

[2] Кодирование текста

[3] Декодирование текста