Тема «Структуры данных: бинарные деревья. Основные
предикаты. Решение задач с помощью бинарных деревьев»
Введение указанной в заголовке структуры целесообразно начать с задачи о поиске элемента в списке достаточно большой размерности. При этом выяснится, что число сравнений окажется большим, особенно тогда, когда элемент в списке не обнаружится. Введение новой структуры (бинарного дерева) значительно упростит поиск. Далее следует дать определение бинарного дерева, показать на примерах его графовое представление, показать связь с линейными списками: линейное дерево фактически есть список. Даются определения и иллюстрируются на примерах сбалансированные, упорядоченные бинарные деревья.
Запись этой структуры на Прологе особенного труда не составит, но следует учитывать ее громоздкость, поэтому при выделении левых поддеревьев, корней и правых поддеревьев следует Придерживаться определенной системы, например использование Различных строк для каждой части дерева с отступами.
Основные предикаты работы с бинарными деревьями также следует проверять в режиме ручной трассировки, при этом размеры конкретных структур должны быть относительно небольшими.
Выбор задач определяется главным достоинством бинарных Деревьев — эффективностью поиска, но результаты решения на прологе нагляднее в виде списков.
Дата добавления: 2015-12-21; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!