Информатика и информационные технологии
Добавить в закладки К обложке
- 1. Информатика. Информация - Страница 1
- 2. Представление чисел в ЭВМ. Формализованное понятие алгоритма - Страница 2
- 3. Введение в язык Pascal - Страница 3
- 4. Стандартные процедуры и функции - Страница 4
- 5. Операторы языка Pascal - Страница 5
- 6. Понятие вспомогательного алгоритма - Страница 6
- 7. Процедуры и функции в Pascal - Страница 7
- 8. Опережающие описания и подключение подпрограмм. Директива - Страница 8
- 9. Параметры подпрограмм - Страница 9
- 10. Типы параметров подпрограмм - Страница 10
- 11. Строковый тип в Pascal. Процедуры и функции для переменных строкового типа - Страница 11
- 12. Записи - Страница 12
- 13. Множества - Страница 13
- 14. Файлы. Операции с файлами - Страница 14
- 15. Модули. Виды модулей - Страница 15
- 16. Ссылочный тип данных. Динамическая память. Динамические переменные. Работа с динамической памятью - Страница 16
- 17. Абстрактные структуры данных - Страница 17
- 18. Стеки - Страница 18
- 19. Очереди - Страница 19
- 20. Древовидные структуры данных - Страница 20
- 21. Операции над деревьями - Страница 21
- 22. Примеры реализации операций - Страница 22
- 23. Понятие графа. Способы представления графа - Страница 23
- 24. Различные представления графа - Страница 24
- 25. Объектный тип в PascalПонятие объекта, его описание и использование - Страница 25
- 26. Наследование - Страница 26
- 27. Создание экземпляров объектов - Страница 27
- 28. Компоненты и область действия - Страница 28
- 29. Методы - Страница 29
- 30. Конструкторы и деструкторы - Страница 30
- 31. Деструкторы - Страница 31
- 32. Виртуальные методы - Страница 32
- 33. Поля данных объекта и формальные параметры метода - Страница 33
- 34. Инкапсуляция - Страница 34
- 35. Расширяющиеся объекты - Страница 35
- 36. Совместимость типов объектов - Страница 36
- 37. Об ассемблере - Страница 37
- 38. Программная модель микропроцессора - Страница 38
- 39. Пользовательские регистры - Страница 39
- 40. Регистры общего назначения - Страница 40
- 41. Сегментные регистры - Страница 41
- 42. Регистры состояния и управления - Страница 42
- 43. Системные регистры микропроцессора - Страница 43
- 44. Регистры управления - Страница 44
- 45. Регистры системных адресов - Страница 45
- 46. Регистры отладки - Страница 46
- 47. Структура программы на ассемблере - Страница 47
- 48. Синтаксис ассемблера - Страница 48
- 49. Директивы сегментации - Страница 49
- 50. Структура машинной команды - Страница 50
- 51. Способы задания операндов команды - Страница 51
- 52. Способы адресации - Страница 52
- 53. Команды пересылки данных - Страница 53
- 54. Арифметические команды - Страница 54
- 55. Логические команды - Страница 55
- 56. Команды передачи управления - Страница 56
21. Операции над деревьями
Далее будем рассматривать все операции применительно к бинарным деревьям. I. Построение дерева.
Приведем алгоритм построения упорядоченного дерева.
1. Если дерево пусто, то данные переносятся в корень дерева. Если же дерево не пусто, то осуществляется спуск по одной из его ветвей таким образом, чтобы упорядоченность дерева не нарушалась. В результате новый узел становится очередным листом дерева.
2. Чтобы добавить узел в уже существующее дерево, можно воспользоваться вышеприведенным алгоритмом.
3. При удалении узла из дерева следует быть внимательным. Если удаляемый узел является листом, или же имеет только одного потомка, то операция проста. Если же удаляемый узел имеет двух потомков, то необходимо будет найти узел среди его потомков, который можно будет поставить на его место. Это нужно в силу требования упорядоченности дерева.
Можно поступить таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.
II. Поиск узла с заданным значением ключевого поля.
При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.
Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссылкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:
TYPE TreeLink = ^Tree;
Tree = record;
Inf: <тип данных>;
Left, Right: TreeLink;
End.