![]() |
| |||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||
О проекте
|
Тема: Представление деревьев. Основные операции над деревом.Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации. Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой – сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два: левое и правое.
Корень дерева опишем в разделе описания переменных:
К основным операциям над деревьями относятся:
Рассмотрим вставку и обход дерева на примере следующей задачи. Задача. Создать и вывести на экран дерево, элементы которого вводятся с клавиатуры и имеют целый тип. Причем для каждой вершины дерева во всех левых вершинах должны находиться числа меньшие, а в правой большие, чем числа, хранящиеся в этой вершине. Такое дерево называется деревом поиска. Опишем процедуру вставки в дерево новой вершины. При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая и правая связи новой вершины должны быть Nil. Когда дерево пусто, значение передаваемое в виде параметра ссылки равно Nil. В этом случае нужно изменить ее так, чтобы она указывала на новую вершину, которая была вставлена как корневая. При вставке второго элемента переданный из основной программы параметр t уже не будет равен Nil, и надо принимать решение о том, в какое поддерево необходимо вставить новую вершину.
Опишем процедуру вывода значений элементов двоичного дерева на экран. Для этого необходимо выполнить полный обход дерева. При обходе дерева его отдельные вершины посещаются в отдельном порядке. Вывод двоичного дерева можно производить рекурсивно, выполняя для каждой вершины три действия:
Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:
Процедура обратного вывода дерева имеет следующий вид:
Задание. Написать процедуры прямого и концевого вывода значений элементов дерева. Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.
Задание. Напишите программу создания и вывода на экран двоичного дерева, используя свою процедуру вывода. Протестируйте программу и представьте учителю файл и листинг для оценки. | |||||||||||||||||||||||||||||||||||||||||
Проект «Pascaler» лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.
|