Лабораторная работа N 4

Бинарные деревья

Цель работы

1. Научиться описывать рекурсивные типы данных.

2. Выработать навыки представления структур в виде дерева.

Задание для подготовки к работе

Изучить лекционный материал по теме «Рекурсивные типы данных. Деревья.»

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

1. Решить задачу соответствующего варианта.

2. Подобрать тестовые данные и протестировать программу на компьютере.

3. Составить отчет о проделанной работе.

Содержание отчета

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

Основные понятия

Типы данных являются рекурсивными, если они допускают, чтобы в его структуре данных была рекурсия.

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

· корень;

· левое поддерево;

· правое поддерево.

Где левое и правое поддеревья сами являются бинарными деревьями. Таким образом, рекурсивность бинарного дерева заложена уже в его определении.

Бинарное дерево упорядочено, если в нем все вершины левого поддерева меньше корня, все вершины правого поддерева больше корня, и оба поддерева также упорядочены. Такое дерево называется бинарным справочником. Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в бинарном справочнике достаточно просмотреть не более одного поддерева.

Стоит заметить, что поиск в двоичном справочнике наиболее эффективен для сбалансированного дерева, то есть дерева, в котором два поддерева содержат примерно равное количество элементов. Если же дерево полностью разбалансировано, то поиск в нем так же неэффективен, как и поиск в списке.

Опишем предикаты для создания и модификации бинарного дерева. Бинарное дерево задается с помощью функтора

tree(K, LeftT, RightT),

где К – элемент, находящийся в вершине; LeftT и RightT – левое и правое поддерево соответственно.

create_tree(A, tree(A, empty, empty)). % создание дерева

insert_left(X, tree(A, _, B), tree(A, X, B)). % включение элемента данных A, как левого поддерева B

insert_right(X, tree(A, B, _), tree(A, B, X)). % включение элемента данных A, как правого поддерева B

Для обхода бинарного дерева «сверху вниз» опишем предикат:

up_to_down(tree(X, LTr, RTr), Xs):- up_to_down(Ltr, Ls), up_to_down(RTr, Rs), append([X|Ls], Rs, Xs).

up_to_down(empty, []).

append – это процедура append(LeftList, RightList, ListRes), где ListRes является результатом слияния списков LeftList, RightList.

Аналогичным образом можно описать процедуру обхода дерева «снизу вверх», «слева направо».

Поиск по сайту: