Сортировка массива с помощью дерева

  • 13 сент. 2014 г.
  • 491 Слова
Отчёт по Лабораторной работе №1
Сортировка массива с помощью дерева

1. Цель работы
Освоение алгоритмов и методов построения деревьев и их применение для сортировки массивов.

2. Алгоритмформирования данных
В основе алгоритма лежит использование формулы ячейки Excel "СЛЧИС". Размер массива выбирается с помощью генератора случайных чисел в диапазоне [1;100]
Собственно алгоритм представлен наблок схеме:

3. Алгоритм построения дерева и сортировки данных
Для построения дерева бы введён пользовательский тип "Node" реализующий функционал узла бинарного дерева. Построение осуществляется спомощью последовательного обхода исходного массива с его второго элемента. Корневым узлом дерева устанавливается первый элемент массива. При добавлении в дерево нового элемента его сравнивают скорневым узлом и нижестоящими узлами, таким образом его в дерево по следующим правилам:
* Если текущий элемент больше или равен корню, установка идёт в правое поддерево и сравнивается с правым дочернимэлементом
* Если текущий элемент меньше или корню, установка идёт в правое поддерево и сравнивается с правым дочерним элементом
Сравнение продолжается пока есть дочерние элементы с которыми можносравнивать, Если элементы закончились, то текущий элемент занимает место в дереве.

После построения дерева вызывается рекурсивная функция для вывода дерева на лист Excel. При входе в процедуру выполняетсяпроверка на наличие значений в левом поддереве, если значение есть выполняется рекурсивный вызов для нижестоящего узла в левом поддереве.
Если в левом поддереве элементов больше нет значение добавляется вмассив ответа. Далее выполняется проверка на наличие значений в правом дереве у родительского узла, если значения есть выполняется рекурсивный вызов процедуры для правого узла.

Коды процедур,реализующих алгоритмы построения дерева и сортировки

Для построения дерева служит функция SortTree принимающая в качестве аргумента не отсортированный массив и возвращающая...
tracking img