Архив категории ‘Динамические структуры данных’

Изображение дерева

    На этом шаге мы рассмотрим как происходит вывод элементов дерева.     Для того чтобы вывести непустое дерево T, необходимо: изобразить правое поддерево дерева T с отступом вправо на расстояние S; вывести корень дерева; изобразить левое поддерево дерева T с отступом вправо на расстояние S.     Величина S, которую можно выбрать по желанию, - это […]

Обходы дерева

    На этом шаге мы рассмотрим обходы деревьев.     Обход дерева - это способ просмотра узлов дерева, причем каждый узел посещается один раз. Левосторонний обход     Алгоритм обхода: посетите корень дерева; обойдите левое поддерево; обойдите правое поддерево. obhod_left (nil). obhod_left (tr (L, X, R)):- write (X," "), obhod_left (L), obhod_left (R). Концевой обход     Алгоритм […]

Реализация основных операций над деревьями

    На этом шаге мы рассмотрим программу, в которой реализованы основные операции над деревьями.     В приведенной ниже программе для наглядности реализовано меню. Вот текст этой программы: domains /* содержит объявления типов объектов (доменов), используемых в программе */ tre = tr (tre, integer, tre); nil /* структура, состоящая из корня, левого и правого поддерева */ […]

Удаление вершины из дерева

    На этом шаге мы рассмотрим, как удалить вершину из дерева.     Опишем предикат, который будет удалять заданное значение из бинарного дерева. У него будет три аргумента. Два входных (исходное дерево и удаляемое значение) и результат удаления.     Реализовать этот предикат оказывается не так просто, как хотелось бы. Без особых проблем можно удалить элемент, когда […]

Добавление вершины в дерево

    На этом шаге мы рассмотрим добавление вершины в дерево.     Создадим предикат, позволяющий добавить в бинарное дерево новое значение. При этом результирующее дерево должно получиться бинарным деревом. Предикат будет иметь три аргумента. Первым аргументом будет дерево, в которое нужно добавить данное значение, вторым - добавляемое значение, третьим - результат вставки.     Если вставлять любое […]

Поиск вершины в дереве

    На этом шаге мы рассмотрим, как можно найти вершину в дереве.     Пусть X - элемент, который нужно найти. Следуя рекурсивному определению дерева, заметим, что: если X - это корень дерева, то считаем, что X уже найден, иначе если X меньше, чем корень, то искать X в левом поддереве, иначе искать в правом поддереве; […]

Формирование дерева

    На этом шаге мы рассмотрим построение дерева.     Для построения дерева используется предикат while (X, D, D1), где X - добавляемый элемент, D - создаваемое дерево, D1 - дерево, необходимое для передачи параметра. В процессе формирования дерева каждый промежуточный результат (дерево с новым добавленным элементом) запоминается.     После того как выполнится условие окончания ввода […]

Деревья (общие сведения)

    На этом шаге мы рассмотрим определение деревьев и основные операции над ними .     Бинарное дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только элементы, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся […]

Вывод элементов дека

    На этом шаге мы рассмотрим, как происходит вывод элементов дека.     Пусть write_dek (T, N) - предикат, реализующий вывод списка T, N - переменная, с помощью которой определим, пуст ли список. Предикат, выполняющий вывод списка, выглядит следующим образом: write_dek ([], 1): - !. write_dek ([], 0): - write ("Дек пуст!!!"). write_dek ([H|T], _):- write […]

Реализация основных операций над деком

    На этом шаге мы рассмотрим программу, в которой реализованы основные операции над деком. В ней для наглядности создано меню.     Текст этой программы приведен ниже: domains /* содержит объявления типов объектов (доменов), используемых в программе */ list = integer* /* домен типа списка целых чисел */ predicates /* содержит объявление предикатов */ vvod(integer, list) […]