Бинарное дерево
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Министерство образования Республики Беларусь
Учреждение образования
Белорусский государственный университет информатики и радиоэлектроники
Факультет непрерывного и дистанционного обучения
Кафедра программного обеспечения информационных технологий
Контрольная работа
Бинарные деревья
Минск - 2011
Введение
Цель работы:
) Изучить нелинейные динамические структуры данных в виде бинарного дерева.
) Научиться решать прикладные задачи с помощью структуры данных бинарное дерево.
Построить дерево двоичного поиска, вывести его на экран компьютера любым способом (графически, вложенными скобками или отступами)
Текст программы размещен в приложении.
бинарный дерево компьютер программа
Построение дерева
Построение дерева состоит в последовательном вводе простых чисел из массива в следующей последовательности: 5, 4, 8, 6, 1, 7, 3, 9. Дерево строится, начиная с корня. Алгоритм построения:
Если узел пустой, то число помещается в него.
Если же он непустой, то входное число сравнивается с числом узла. В случае, если он больше, то он рекурсивно переносится в правое поддерево; если же меньше - в левое.
Таким образом, мы получим бинарное дерево поиска (рис. 1).
Рисунок 1 - Построенное бинарное дерево
В представлении дерева применялись отступы. Перед представлением необходимо определить высоту дерева. Высота дерева определяется как максимальный путь ее прохождения сверху-вниз. В данном случае высота дерева (переменная h) равна 4.
Представление дерева строится на двух массивах и на цикле, начиная со значения высоты дерева до 1. При данной итерации из одного массива в выходную строку с установленными отступами при помощи функции sc(s), где s - число, определяемое значением итерации (уровнем дерева) в зависимости от местоположения узла (листа) в дереве, выносятся узлы (листья) дерева одного уровня. При этом потомки этих узлов заносятся в другой массив (т.е. в массив помещаются узлы и листья следующего уровня по итерации). Первоначально в один массив заносится корень дерева, а его потомки в другой массив. Если у узла нет потомка, в массив заносится цифра 0 (либо два нуля, если это лист). Если же вместо узла - 0, то здесь проверяется последний ли уровень дерева. В случае отрицательного ответа - в массив помещаются два нуля. Это необходимо, чтобы корректно рассчитать количество отступов на данном уровне дерева, в частности между листьями 3 и 7. В конечном счете, получаем представление дерева, показанное на рис. 2
Рисунок 2 - Представление дерева
Реализовать три обхода дерева: сверху-вниз, слева-направо и снизу- вверх. Вывести обходы на экран компьютера. Рекурсивные алгоритмы прохождения бинарного дерева по каждому из способов обходов включают 3 одинаковых процедуры, где нужно пройти корень поддерева, левое поддерево текущего корня и правое поддерево текущего корня. Направление обхода однозначно определяет последовательность выполнения указанных процедур.Сверху-вниз. Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину.
Рисунок 3 - Обход сверху-вниз
Слева-направо. При симметричном порядке дерево проходится слева-направо, порождая лексиграфически упорядоченную последовательность ключей узлов. Симметричность порядка выражается в том, что если бинарное дерево отразить относительно вертикальной оси, поменяв местами левые и правые узлы, то симметричный порядок прохождения заменится на противоположный лексиграфический.
Рисунок 4 - Обход слева-направо
Снизу-вверх. Если применяется концевой порядок прохождения, то получается обход дерева снизу-вверх, когда в момент посещения любого узла все его потомки уже пройдены, а корень дерева проходится последним. Из-за этой особенности обхода, концевой порядок часто называют восходящим или обратным относительно прямого.
Рисунок 5 - Обход снизу-вверх
Выполнить симметричноправую прошивку дерева.
Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу. Симметричноправая прошивка подразумевает обход слева-направо.
Рисунок 6 - Симметричноправая прошивка дерева
Процедура прошивки, в которой осуществляется обход, проводит поиск листьев и узлов, для которых требуется прошивка (в частности это листья 3, 7, 9 и узел 4). Когда этот лист или узел обнаруживается, инициализируется дополнительная процедура, которая таким же обходом находит узел, к которому прошивается лист или узел, найденный первичной процедурой (3, 7, 9 и 4). Такими узлами являются 4, 5 и 8.
Выводы:
в ходе выполнения работы были изучены нелинейные динамические структуры данных в виде бинарного дерева;
была решена задача, связанная со структурой данных - бинарное дерево (создание, представление, обходы и прошивка дерева).
Приложение
bin_tree;n = 8;pnode = ^node;
node = record
v : integer;
right, left : pnode;
lf, rf : boolean;