Содержание
- 2. Нелинейные структуры данных позволяют выражать более сложные отношения между элементами, нежели линейные отношения соседства, как это
- 3. Деревья
- 4. Деревья представляют собой иерархическую структуру некой совокупности элементов. Примерами деревьев могут служить генеалогические и организационные диаграммы.
- 5. Основная терминология Дерево - это совокупность элементов, называемых узлами (один из которых определен как корень), и
- 6. Основная терминология Формально дерево можно рекуррентно определить следующим образом: 1. Один узел является деревом. Этот же
- 7. Пример 1 Рассмотрим оглавление книги, схематически представленное на рис. 1, а. Это оглавление является деревом, которое
- 8. Основная терминология Путем из узла n1 в узел nk называется последовательность узлов n1, n2, …, nk,
- 9. Основная терминология Если существует путь из узла а в b, то в этом случае узел а
- 10. Основная терминология Высотой узла дерева называется длина самого длинного пути из этого узла до какого-либо листа.
- 11. Порядок узлов Сыновья узла обычно упорядочиваются слева направо. Поэтому два дерева на рисунке различны, так как
- 12. Порядок узлов Упорядочивание слева направо сыновей ("родных детей" одного узла) можно использовать для сопоставления узлов, которые
- 13. Пример 2. Рассмотрим дерево на рисунке. Узел 8 расположен справа от узла 2, слева от узлов
- 14. Прямой, обратный и симметричный обходы дерева Существует несколько способов обхода (прохождения) всех узлов дерева. Обход узлов
- 15. Прямой, обратный и симметричный обходы дерева Если дерево Т является нулевым деревом, то в список обхода
- 16. Прямой, обратный и симметричный обходы дерева Тогда для различных способов обхода имеем следующее. 1. При прохождении
- 17. Листинг 4.1. Рекурсивные процедуры обхода деревьев procedure PREORDER ( n: узел ); begin (1) занести в
- 18. Листинг 4.1. Рекурсивные процедуры обхода деревьев procedure INORDER ( n: узел ); begin if n -
- 19. Пример 3. Прямой обход дерева Сначала запишем (посетим) узел 1, затем вызовем процедуру PREORDER для обхода
- 20. Пример 3. Обратный и симметричный обходы дерева Подобным образом, предварительно преобразовав процедуру PREORDER в процедуру, выполняющую
- 21. Пример 3. Обратный и симметричный обходы дерева При обходе деревьев можно применить следующий полезный прием. Надо
- 22. Помеченные деревья и деревья выражений Часто бывает полезным сопоставить каждому узлу дерева метку (label) или значение,
- 23. Пример 4. Дерево выражения с метками На рисунке показано дерево с метками, представляющее арифметическое выражение (а+b)*(а+с),
- 24. Помеченные деревья и деревья выражений Часто при обходе деревьев составляется список не имен узлов, а их
- 25. Помеченные деревья и деревья выражений Отметим, что в префиксных формах нет необходимости отделять или выделять отдельные
- 26. Помеченные деревья и деревья выражений Обратное упорядочивание меток дерева выражений дает так называемое постфиксное представление выражений.
- 27. Помеченные деревья и деревья выражений При симметричном обходе дерева выражений получим так называемую инфиксную форму выражения,
- 28. Вычисление „наследственных" данных Обход дерева в прямом или обратном порядке позволяет получить данные об отношениях предок-потомок
- 29. Вычисление „наследственных" данных Эти функции позволяют выполнить ряд полезных вычислений. Например, все узлы поддерева с корнем
- 30. Абстрактный тип данных TREE (дерево)
- 31. В теме 4 списки, стеки и очереди получили трактовку как абстрактные типы данных (АТД). В этой
- 32. Операторы, выполняемые над деревьями 1. PARENT(n, Т). Эта функция возвращает родителя (parent) узла n в дереве
- 33. Операторы, выполняемые над деревьями 3. RIGHT_SIBLING(n, Т). Эта функция возвращает правого брата узла n в дереве
- 34. Операторы, выполняемые над деревьями 4. LABEL(n, Т). Возвращает метку узла n дерева Т. Для выполнения этой
- 35. Операторы, выполняемые над деревьями 6. ROOT(T). Возвращает узел, являющимся корнем дерева Т. Если Т - пустое
- 36. Пример 5. Напишем рекурсивную PREORDER и нерекурсивную NPREORDER процедуры обхода дерева в прямом порядке и составления
- 37. Листинг 4.2. Рекурсивная процедура обхода дерева в прямом порядке procedure PREORDER ( n: node ); var
- 38. Пример 5. Теперь напишем нерекурсивную процедуру для печати узлов дерева в прямом порядке. Чтобы совершить обход
- 39. Пример 5. Программа NPREORDER выполняет два вида операций, т.е. может находиться как бы в одном из
- 40. Листинг 4.3. Нерекурсивная процедура обхода дерева в прямом порядке procedure NPREORDER ( T: TREE ); var
- 41. Реализация деревьев
- 42. Представление деревьев с помощью массивов Пусть Т - дерево с узлами 1, 2, ..., n. Возможно,
- 43. Представление деревьев с помощью массивов Дерево и курсоры на родителей: Данное представление использует то свойство деревьев,
- 44. Представление деревьев с помощью массивов Использование указателей или курсоров на родителей не помогает в реализации операторов,
- 45. Представление деревьев с помощью массивов Можно ввести искусственный порядок нумерации узлов, например нумерацию сыновей в возрастающем
- 46. Листинг 4.4. Оператор определения правого брата function RIGHT_SIBLING ( n: node; T: TREE ) : node;
- 47. Представление деревьев с помощью списков сыновей Важный и полезный способ представления деревьев состоит в формировании для
- 48. Представление деревьев с помощью списков сыновей На рис. показано, как таким способом представить следующее дерево: Здесь
- 49. Представление деревьев с помощью списков сыновей Прежде чем разрабатывать необходимую структуру данных, нам надо в терминах
- 50. Листинг 4.5. Функция нахождения самого левого сына function LEFTMOST_CHILD ( n: node; T: TREE ): node;
- 51. Представление деревьев с помощью списков сыновей Теперь представим конкретную реализацию списков, где типы LIST и position
- 52. Листинг 4.6. Функции, использующие представление деревьев посредством связанных списков function LEFTMOST_CHILD ( n: node; T: TREE
- 53. Листинг 4.6. Функции, использующие представление деревьев посредством связанных списков function PARENT ( n: node; T: TREE
- 54. Среди прочих недостатков описанная выше структура данных не позволяет также с помощью операторов CREATEi создавать большие
- 55. Логическим продолжением представления дерева, показанного на слайде 47, будет замена массива заголовков на отдельный массив nodespace
- 56. Пример представления через левых сыновей и правых братьев На рисунке показаны дерево и структура данных, где
- 57. Но и эту структуру можно значительно упростить. Для этого заметим, что цепочка указателей поля next массива
- 58. Представление через левых сыновей и правых братьев Можно упростить структуру, если идентифицировать узел не с помощью
- 59. Массив cellspace можно описать как следующую структуру: var cellspace: array[1..maxnodes] of record label: labeltype; leftmost_child: integer;
- 60. Пример представления через левых сыновей и правых братьев Новое представление для дерева, схематически изображено на рис.
- 61. Используя описанное представление, все операторы, за исключением PARENT, можно реализовать путем прямых вычислений. Оператор PARENT требует
- 62. Листинг 4.7. Функция CREATE2 function CREATE2 ( v: labeltype; T1, T2: integer ): integer; { возвращает
- 63. Здесь мы предполагаем, что неиспользуемые ячейки массива cellspace связаны в один свободный список, который в листинге
- 64. Двоичные деревья
- 65. Деревья, которые мы определили выше, называются упорядоченными ориентированными деревьями, поскольку сыновья любого узла упорядочены слева направо,
- 66. Пример 6. Если принять соглашение, что на схемах двоичных деревьев левый сын всегда соединяется с родителем
- 67. Обход двоичных деревьев в прямом и обратном порядке в точности соответствует таким же обходам обычных деревьев.
- 68. Если именами узлов двоичного дерева являются их номера 1, 2, ..., n, то подходящей структурой для
- 69. Двоичное дерево: Представление двоичного дерева: Представление двоичных деревьев
- 70. Приведем пример применения двоичных деревьев в качестве структур данных. Для этого рассмотрим задачу конструирования кодов Хаффмана.
- 71. Коды Хаффмана В таблице показаны две возможные кодировки для наших пяти символов. Ясно, что первый код
- 72. Задача конструирования кодов Хаффмана заключается в следующем: имея множество символов и значения вероятностей их появления в
- 73. В частности, первый код из примера слайда 71 имеет среднюю длину кода 3. Это число получается
- 74. Можно ли придумать код, который был бы лучше второго кода? Ответ положительный: существует код с префиксным
- 75. Способ нахождения оптимального префиксного кода называется алгоритмом Хаффмана: Находятся два символа а и b с наименьшими
- 76. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну
- 77. Коды Хаффмана Двоичные деревья для кодов 1 и 2:
- 78. Для реализации алгоритма Хаффмана мы используем лес, т.е. совокупность деревьев, чьи листья будут помечены символами, для
- 79. Важным этапом в работе алгоритма является выбор из леса двух деревьев с наименьшими весами. Эти два
- 80. Этапы создания дерева Хаффмана
- 81. Теперь опишем необходимые структуры данных. Во-первых, для представления двоичных деревьев мы будем использовать массив TREE (Дерево),
- 82. Во-вторых, мы используем массив ALPHABET (Алфавит), также состоящий из записей, которые имеют следующий тип: record symbol:
- 83. В-третьих, для представления непосредственно деревьев необходим массив FOREST (Лес). Этот массив будет состоять из записей с
- 84. Начальные значения всех трех массивов, соответствующих данным на рисунке а показаны ниже. Коды Хаффмана Эскиз программы
- 85. Листинг 4.8. Программа построения дерева Хаффмана (1) while существует более одного дерева в лесу do begin
- 86. Для реализации строки (4) листинга 4.8, где увеличивается количество используемых ячеек массива TREE, и строк (5)
- 87. В листинге 4.9 приведены коды двух полезных процедур. Процедура lightones, выполняет реализацию строк (2) и (3)
- 88. Листинг 4.9. procedure lightones ( var least, second: integer ); { присваивает переменным least и second
- 89. Листинг 4.9. function create ( lefttree, righttree: integer ): integer; { возвращает новый узел, у которого
- 90. Теперь все неформальные операторы листинга 4.8 можно описать подробнее. В листинге 4.10 приведен код процедуры Huffman,
- 91. Листинг 4.10. Реализация алгоритма Хаффмана procedure Huffman; var i, j:integer; {два дерева с наименьшими весами из
- 92. На рисунке показана структура данных из рис. слайда 83 после двух итераций, т.е. после того, как
- 93. После завершения работы алгоритма код каждого символа можно определить следующим образом. Найдем в массиве ALPHABET запись
- 94. Таким образом, код символа будет напечатан в виде последовательности битов, но в обратном порядке. Чтобы распечатать
- 95. Для указания на правых и левых сыновей (и родителей, если необходимо) вместо курсоров можно использовать настоящие
- 97. Скачать презентацию