Древовидные структуры

Содержание 1. Исследовательская часть.1. Основные понятия и определения 2. Конструкторская часть 1. Основные операции с бинарными деревьями.2. Поиск по дереву с включением 3. Удаление из дерева3. Технологическая часть 35 Список литературы 1. Исследовательская часть. Древовидные структуры 1. Основные понятия и определения.

Последовательности и списки можно определить следующим образом любая последовательность список с базовым типом Т это либо 1 пустая последовательность список либо 2 конкатенация цепочка из элемента типа Т и последовательности с базовым типом Т. Здесь для определения принципов структурирования следования или итерации используется рекурсия. Следование и итерация встречается настолько часто, что их обычно считают фундаментальными образами как структур данных, так и управления в программах.

Однако всегда следует помнить, что с помощью рекурсии их только можно определять, по рекурсии можно эффективно использовать для определения более сложных структур. Хорошо известным примером служат деревья. Пусть древовидная структура определяется следующим образом древовидная структура с базовым типом Т это либо 1 путая структура либо 2 узел типа Т, с которым связано конечное число древовидных структур с базовым типом

Т, называемых поддеревьями. Из сходства рекурсивных определений последовательностей и древовидных структур видно, что последовательность список есть древовидная структура, у которой каждый узел имеет не более одного поддерева. Поэтому последовательность список называется также вырожденным деревом. Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв такая древовидная структура разными способами изображена

на рис. 1. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину дерево. Однако довольно странно, что деревья принято рисовать перевернутыми или если кто-то предпочитает иначе выразить этот факт изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел

А обычно называют корнем. Хотя мы сознаем, что в природе деревья представляют собой несколько более сложные образования, чем наши абстракции, в дальнейшем древовидные структуры будем называть просто деревьями. Упорядоченное дерево это дерево, у которого ветви каждого узла упорядочены. Следовательно, два упорядоченных дерева на рис. 2 это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом х, называется непосредственным потомком х если

х находится на уровне i, то говорят, что у на уровне i 1. Наоборот, узел х называется непосредственным предком y. Считается, что корень дерева расположен на уровне 1. Максимальный уровень какого-либо элемента дерева называетcz его глубиной или высотой. Если элемент не имеет потомков, он называется терминальным элементам или листом, а элемент, не являющийся

терминальным, называется внутренним узлом. Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Число ветвей, или ребер, которые нужно пройти, чтобы продвинуться от корня к узлу х, называется длиной пути к х. Корень имеет длину пути 1, его непосредственные потомки длину пути 2 и т. д. Вообще, узел на уровне i имеет длину пути i. Длина пути дерева определяется как сумма длин путей всех

его узлов. Она также называется длиной внутреннего пути. a A B D I , E J,K,L, C F O, G M,N ,H P b c d Рис. 1. Представления древовидной структуры а вложенные множества b вложенные скобки с ломаная последовательность d граф. Например, длина внутреннего пути дерева, изображенного на рис. 1 равна 52.I есть 1.1 где ni-число узлов на уровне i.

Для того чтобы определить, что называется длиной внешнего пути, мы будем дополнят дерево специальным узлом каждый раз, когда в нем встречается нулевое поддерево. При этом мы считаем, что все узлы должны иметь одну и ту же степень степень дерева. Следовательно, подобное расширение дерева предполагает заполнение Рис. 2. Два различных бинарных дерева. пустых ветвей, разумеется, при этом специальные узлы не имеют

дальнейших потомков. Дерево на рис. 1, дополненное специальными узлами, показано на рис. 3, где специальные узлы изображены квадратиками. Рис. 3. Тернарное дерево со специальными узлами. Длина внешнего пути теперь определяется как сумма длин путей всех специальных узлов. Если число специальных узлов на уровне i есть .mi то средняя длина внешнего пути PE равна 1.2 У дерева, приведенного на рис. 3, длина внешнего пути равна 153.

Число специальных узлов m, которые нужно добавить к дереву степени d, непосредственно зависит от числа п исходных узлов. Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется mп ветвей. С другой стороны, из каждого исходного узла выходят d ветвей, а из специальных узлов ни одной. Поэтому всего имеется dn1 ветвей 1 дает ветвь, указывающую на корень.

Из этих двух формул мы получаем следующее равенство между числом т специальных узлов и п исходных узлов dn 1 т п, или m d ln1.3 Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h, не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел корень, уровень 2 содержит d его потомков, уровень 3 содержит d2 потомков d узлов уровня 2 и т. д.

Это дает следующую величину 1.4 в качестве максимального числа узлов для дерева с высотой h и степенью d. При d 2 мы получаем 1.5 Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество элементов узлов, каждый из которых либо пуст, либо состоит из корня узла, связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня.

В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреблять слово дерево, имея в виду упорядоченное бинарное дерево. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями multiway trees. Знакомыми примерами бинарных деревьев являются фамильное генеалогическое дерево с отцом и матерью человека в качестве его потомков , история теннисного турнира, где узлом является каждая игра, определяемая ее

победителем, а поддеревьями две предыдущие игры соперников арифметическое выражение с двухместными операциями, где каждая операция представляет собой ветвящийся узел с операндами в качестве поддеревьев см. рис. 4. Теперь мы обратимся к проблеме представления деревьев. Ясно, что изображение таких рекурсивных структур точнее, рекурсивно определенных. Прим. ред. с разветвлениями предполагает использование ссылок.

Очевидно, что не имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные Рис. 4. Выражение а bcd ef, представленное в виде дерева. с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указывающих на поддеревья данного узла. Ясно, что ссылка на пустое поддерево обозначается через nil. Следовательно, дерево на рис. 4 состоит из компонентов такого типа type node record op char left, right

node 1.6 end и может строиться, как показано на рис. 5. Ясно, что существуют способы представления абстрактной древовидной структуры в терминах других типов данных, например таких, как массив. Это общепринятый способ во всех языках, где нет средств динамического размещения компонентов и указания их с помощью ссылок. В этом случае дерево на рис. 4 можно представить переменной-массивом, описанной как t аггау1 11 of

record op char left, right integer 1.7 end и со значениями компонентов, приведенными в табл. 1.1. Хотя подразумевается, что массив t представляет абстрактную структуру дерева, мы будем называть его все же не деревом, а массивом согласно явному определению. Мы не будем обсуждать другие возможные представления деревьев в системах, где отсутствует динамическое распределение памяти, Рис. 5. Дерево, представленное как структура данных. поскольку мы считаем, что

системы программирования и языки, имеющие это свойство, являются или станут широко распространенными. Таблица 1.1. Дерево, представленное с помощью массива 2364 951781011а00Ь00с00d00е0000 1 2 3 4 5 6 7 8 9 10 11 Прежде чем обсуждать, как лучше использовать деревья и как выполнять операции с деревьями, мы покажем на примере, как программа может строить дерево. Предположим, что нужно сформировать дерево, содержащее узлы типа, описанного в 1.6, а значениям узлов будут п чисел, прочитанных из входного файла.

Для усложнения задачи потребуем построить дерево с п узлами и минимальной высотой. Чтобы достичь минимальной высоты при данном числе узлов, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие узлы Рис. 6. Идеально сбалансированные деревья. поровну слева и справа от каждого узла. В результате построенное дерево при данном n имеет вид, как показано на рис.

6 для п 1,7. Правило равномерного распределения при известном числе узлов п лучше всего формулируется с помощью рекурсии 1. Взять один узел в качестве корня. 2. Построить левое поддерево с nl n div2 узлами тем же способом. 3. Построить правое поддерево с пr п nl 1 узлами тем же способом. Это правило описано рекурсивной процедурой tree, входящей в программу 1.1, которая читает входной файл

и строит идеально сбалансированное дерево. Мы получаем такое определение program buildtreeinput, output type ref node nоde record кey integer left, right ref end Var n integer root ref function tree n integer ref var newnode ref x, nl, nr integer begin построение идеально сбалансированного дерева с n узлами if n 0 then tree nil else begin nl n div 2 nr n nl 1 readx newnewnode with newnode do begin key x left treenl right treenr end tree newnode end end tree procedure

printreetref h integer var i integer begin печать дерева t со сдвигом h if t nil then with t do begin printtreeleft, h1 for i 1 to h do write writelnkey printtreeright, hl end end printtree begin первое целое число есть число узлов readn root treen printtreeroot,0 end . Программа 1.1. Построение идеально сбалансированного дерева. Дерево идеально сбалансировано, если для каждого его узла количества узлов в левом и правом поддереве

различаются не более чем на 1. Предположим, например, что имеются следующие входные данные для дерева с 21 узлом 21 8 9 11 15 19 20 21 7 3 2 15 6 4 13 14 10 12 17 16 18 Тогда программа 1.1 строит идеально сбалансированное дерево, показанное на рис. 7. Рис. 7. Дерево, построенное с помощью программы 1.1. Отметим простоту и ясность этой программы, достигнутые благодаря использованию рекурсивных процедур.

Очевидно, что рекурсивные алгоритмы особенно уместны, когда программа должна обрабатывать данные, структура которых определена рекурсивно. Это вновь отражается в процедуре printtree, которая печатает полученное дерево пустое дерево не печатается для поддерева уровня L, а вначале печатается его левое поддерево, затем узел, который выделяется предшествующими L пробелами, и, наконец, печатается его правое поддерево.

Преимущество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. Читателю предлагается проявить свою изобретательность и написать нерекурсивную программу, строящую такие же деревья, прежде чем смотреть на 1.8. Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя. Ему предлагается выяснить, как и почему она работает. program buildtreeinput,output type ref node node record key integer left, right ref end

Var i,n,nl,nr,x integer root,p,q,r,dmy ref s array 1 30 of стек record n integer rf ref end begin первое целое число есть число узлов readn newroot newdmy фиктивный элементi 1 s1.n n s1.rf root repeat n si.n r si .rf i i 1 из стека if n 0 then r.right nil else begin p dmy 1.8 repeat nl n div 2 nr n nl 1 readx newq q.key x i i1 si.n nr si.rf q в стек n nl p.left q p q until n 0 q.left nil r.right dmy.left end until I 0 printtree root.right,0 end . 2. Конструкторская часть.

2.1. Основные операции с бинарными деревьями. Имеется много задач, которые можно выполнять на древовидной структуре распространенная задача выполнение заданной операции Р с каждым элементом дерева. Здесь Р рассматривается как параметр более общей задачи посещения всех узлов, или, как это обычно называют, обхода дерева. Если рассматривать эту задачу как единый последовательный процесс, то отдельные узлы посещаются в некотором

определенном порядке и могут считаться расположенными линейно. В самом деле, описание многих алгоритмов существенно упрощается, если можно говорить о переходе к следующему элементу дерева, имея в виду некоторое упорядочение. Существуют три принципа упорядочения, которые естественно вытекают из структуры деревьев. Так же как и саму древовидную структуру, их удобно выразить с помощью рекурсии.

Обращаясь к бинарному дереву на рис. 8, где R обозначает корень, а А и В левое и правое поддеревья, мы можем определить такие три упорядочения 1. Сверху вниз R, А, В посетить корень до поддеревьев 2. Слева направо A, R, В 3. Снизу вверх А, В, R посетить корень после поддеревьев Обходя дерево на рис. 4 и выписывая символы, находящиеся в узлах, в том порядке, в котором они встречаются,

мы получаем следующие последовательности 1. Сверху вниз ab c d ef 2. Слева на право a bc d e f 3. Снизу вверх abc def Мы узнаем три формы записи выражений обход сверху вниз дает префиксную запись, обход снизу вверх постфиксную запись, Рис. 8. Бинарное дерево. а обход слева направо дает привычную инфиксную запись, хотя и без скобок, необходимых для определения порядка выполнения операций.

Теперь выразим эти три метода обхода как три конкретные программы с явным параметром t, означающим дерево, с которым они имеют дело, и неявным параметром Р, означающим операцию, которую нужно выполнить с каждым узлом. Введем следующие определения type ref node node record 2.1 left,right ref end Эти три метода легко сформулировать в виде рекурсивных процедур они вновь служат примером того, что

действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. procedure preordert ref begin if t nil then begin Pt preordert .left 2.2 preordert .right end end procedure postordert ref begin if t nil then begin posordert . left postordert .right 2.3 Pt end end procedure inordert ref begin if t nil then begin wordcrt .left Pt 2.4 Inordert .right end end. Отметим, что ссылка t передается как параметр-значение.

Это отражает тот факт, что здесь существенна сама ссылка указание на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изменить значение, если бы t передавался как параметр-переменная. Пример подпрограммы, осуществляющей обход дерева, это подпрограмма печати дерева с соответствующим сдвигом, выделяющим каждый уровень узлов см. программу 1.1. Бинарные деревья часто используются для представления множеств данных, элементы которых ищутся по уникальному,

только им присущему ключу. Если дерево организовано таким образом, что для каждого узла ti все ключи в левом поддереве, меньше ключа ti, а ключи в правом поддереве больше ключа ti, то это дерево называется деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа. Как мы видели, п элементов можно организовать в бинарное дерево с высотой не более чем log п.

Поэтому для поиска среди п элементов может потребоваться не более log n сравнений, если дерево идеально сбалансировано. Очевидно, что дерево намного более подходящая форма организации такого множества данных, чем линейный список, который рассматривался в предыдущем разделе. S Рис. 9. Дерево поиска с барьером. Так как этот поиск проходит по единственному пути от корня к искомому узлу, его можно запрограммировать с помощью итерации 2.6 function locx integer t ref ref var found boolean

begin found false while t . nil Л - found do begin 2.6 if t .key x then found true else if t .key x then t t .left else t .right end loc t end. Функция locx, t имеет значение nil, если в дереве с корнем t не найдено ключа со значением х. Так же как в случае поиска по списку, сложность условия окончания цикла заставляет искать лучшее решение. При поиске по списку .конце его помещается барьер. Этот прием можно применить в случае поиска по дереву.

Использование ссылок позволяет связать все терминальные узлы дерева с одним и тем же барьером. Полученная структура это уже не просто дерево, а скорее, дерево, все листья, которого прицеплены внизу к одному якорю см. рис. 9. Барьер можно также считать общим представлением всех внешних специальных узлов, которыми дополняется исходное дерево см. рис. 3. Полученная в результате упрощенная процедура поиска описана ниже function locx integer t ref ref

begin s .key x барьер 2.7 while t .key x do if x t .key then t t .left else t t .right loc t end. Отметим, что если в дереве с корнем t не найдено ключа со значением х, то в этом случае locx,t принимает значение s, т. е. ссылки на барьер. Ссылка на s просто принимает на себя роль ссылки nil. 2.2. Поиск по дереву с включением. Возможности техники динамического размещения переменных с доступом к ним через ссылки вряд ли полностью проявляются в тех примерах, где построенная структура данных остается

неизменной. Более подходящими примерами служат задачи, в которых сама структура дерева изменяется,т. е. дерево растет иили уменьшается во время выполнения программы. Это также .случай, когда другие представления данных, такие, как массив, не подходят и когда дерево с элементами, связанными ссылками, как раз и есть подходящая структура. Прежде всего рассмотрим случай постоянно растущего, но никогда не убывающего дерева.

Хорошим примером этого является задача построения частотного словаря, которая уже разбиралась, когда речь шла о связанных списках. Вернемся к ней снова. В этой задаче задана последовательность слов н нужно установить число появлений каждого слова. Это означает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появлений, если нет в дерево вставляется новое слово с

.начальным значением счетчика, равным 1. Мы называем эту задачу поиском по дереву с включением. Предполагаются следующие описания типов type ref word, word record key integer 2.8 count integer left, right ref end Считая, кроме того, что у нас есть исходный файл ключей f, а переменная root указывает на корень дерева поиска, мы можем записать программу следующие образом resetf while -eoff do 2.9 begin readf,x searchx,root end Определение пути поиска здесь вновь очевидно.

Но сели он приводит в тупик, т. е. к пустому поддереву, обозначен- Рис. 10. Включение в упорядоченное бинарное дерево. ному ссылочным значением nil, то данное слово нужно вставить в дерево на место пустого поддерева. Рассмотрим, на пример, бинарное дерево, показанное на рис. 10, и включение в него слова Paul. Результат показан пунктирными линиями на том же рисунке. Целиком работа алгоритма приведена в программе 2.1.

Процесс поиска представлен в виде рекурсивной процедуры. Отметим, что ее параметр р передастся как параметр-переменная, а не как параметр-значение. Это существенно, поскольку в случае включения переменной должно присваиваться некоторое новое значение ссылке, которая перед этим имела значение nil. Для входной последовательности, состоящей из 21 числа, которая обрабатывалась с помощью программы 1.1, построившей дерево на рис.

7, программа 2.1 строит бинарное дерево поиска, показанное на рис. 11. Рис. 11. Дерево поиска, построенное с помощью программы 2.1. Использование барьера вновь несколько упрощает задачу, что показано в 2.10. Понятно, что в начале программы переменная root должна инициироваться ссылкой на барьер, а не значением nil, и перед каждым поиском очередного слова искомое значение х должно присваиваться нолю ключа в барьере

procedure searchx integer var p ref begin if x p .key then searcltx,p .left elseif x p .key then searchx,p .right elseit p s then p .count p .count 1 elsebegin включение newp 2.10 with p do begin key x left s right s count 1 end end end. program treesearchinput,output поиск с включением по двоичному дереву type ref word word record key integer count integer left, right ref end var root ref k integer procedure printtreew ref l integer var i integer begin if w nil then with w do begin printtreeleft, l1 for i 1

to i do write writelnkey printtreeright, l1 end end procedure searchx integer var p ref begin if p nil then begin слова нет в дереве включить его new p with p do begin key х count 1 left nil right nil end end else if x p.key then searchx, p.left else if x p.key then searchx, p.right else p.count p.count 1 end search begin root nil while - eof input do begin readk searchk, root end printtreeroot,0 end Программa 2.1. Поиск с включениями. Еще раз, теперь уже последний, построим альтернативную версию этой

программы, отказавшись от использования рекурсии. Но сейчас избежать рекурсии не так просто, как в случае без включения, так как для того, чтобы производить включение, нужно помнить пройденный путь по крайней мере на один шаг назад. В программе 2.1 он запоминается автоматически при использовании параметра-переменной. Чтобы правильно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она в качестве правого или левого поддерева. Для этого вводятся две переменные р2 и d для направления

procedure searchx integer root ref var p1, p2 ref d integer begin p2 root p1 p2.right d 1 while р1 nil Л d 0 do begin p2 p1 if x p1.key then begin p1 p1.left d - 1 end else if x p1.key then begin p1 p1.right d 1 end else d 0 end if d 0 then p1.count p1.count 1 else begin включение newp1 with p1 do begin key x left nil right nil count 1 end if d 0 then p2 left p1 else p2.right p1 end end. 2.11 Как и в случае поиска с включением по списку, используются две ссылки

pi и р2, такие, что в процессе поиска р2 всегда указывает на предикат pl. Чтобы удовлетворить этому условию в начале поиска, вводится вспомогательный фиктивный элемент, на который указывает root. Начало действительного дерева поиска обозначается ссылкой root.right. Поэтому программа должна начинаться операторами newroot root.right nil вместо начального присваивания root nil Хотя задача этого алгоритма поиск, его можно применить и для сортировки.

В самом деле, он очень напоминает метод сортировки включением, а поскольку вместо массива используется дерево, пропадает необходимость перемещения компонента выше места включения. Сортировку с помощью дерева можно запрограммировать почти столь же эффективно, как и лучшие методы сортировки массивов. Но необходимо принять некоторые меры предосторожности. Разумеется, при появлении одинаковых ключей, теперь надо поступать иначе.

Если в случае х р .key алгоритм работает так же, как и в случае х р.key, то он представляет метод устойчивой сортировки, т. е. элементы с одинаковыми ключами появляются в той же последовательности при обычном обходе дерева, что и в процессе их включения в дерево. Вообще говоря, имеются лучшие способы сортировки, но в задачах, где требуется и поиск, и сортировка, алгоритм поиска по дереву с включением весьма рекомендуется.

Он действительно очень часто применяется в трансляторах и программах работы с банками данных для организации объектов, которые нужно хранить и искать в памяти. Подходящий пример построение таблицы перекрестных ссылок для заданного текста. Исследуем эту задачу подробно. Наша цель написать программу, которая читая текст f и печатая его с добавлением последовательных номеров строк собирает все слова этого текста, сохраняя при этом номера

строк, в которых они встречались. Когда этот просмотр закончится, нужно построить таблицу, содержащую все собранные слова в алфавитном порядке, со списками соответствующих строк. Очевидно, что дерево поиска называемое также лексикографическим деревом лучше всего подходит для представления слов, встречающихся в тексте. Теперь каждый узел не только содержит слово в качестве значения ключа, но одновременно представляет собой начало списка номеров строк.

Каждую запись номера строки мы будем называть отметкой. Следовательно, в этом примере мы встречаем и деревья, и линейные списки. Программа состоит из двух основных частей см. программу 2.2 фазы чтения текста и построения дерева и фазы печати таблицы. Ясно что последняя является частным случаем процедуры обхода дерева, где посещение каждого узла предполагает печать, значения ключа слова и проход по связанному с ним списку номеров строк

отметок. Кроме того, полезно привести еще некоторые пояснения, относящиеся к программе 2.2 1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы. program crossreff,output построение таблицы перекрестных ссылок с использованием двоичного дерева const c1 10 длина слова с2 8 количество слов в строке с3 6 количество цифр в числе с4 9999 максимальный номер строки type alfa packed array 1 c1 of char wordref word itemref item word record key alfa first, last itemref left, right wordref

end item packed record lno 0 c4 next itemref end var root wordref k,kl integer n integer номер текущей строки id alfa f text a array 1 c1 of char procedure search var wl wordref var w wordref x itemref begin w wl if w nil then begin neww newx, with w do begiu key id left nil right nil first x last x end x.lno n x.next nil w1 w end else if id it w .key then searchw.left else if id w.key then searchw.right else begin newx x.lno n x.next nil w.last.next x w.last x end end search procedure printtreew wordref procedure

printwordwword var l integer x itemref begin write , w.key x w.first I 0 repeat if l c2 then begin writlen l 0 write cll end l l1 writex.lnoсЗ x х.next until x nil writeln end printword begin if w nil then begin printtreew .left printwordw printtreew.right end end printtree begin root nil n 0 k1 cl pageoutput resetf while - eoff do begin if n c4 then n 0 n nl writenсЗ следующая строка write while eolnf do begin просмотр непустой строки if f in a z then begin k 0 repeat if k cl

then begin k k1 ak f end writef getf until -f in a z,0 9 if k k1 then k1 k else repeat ak1 k1 k1-1 until k1 k pack a,l,id searchroot end else begin проверка на кавычку или комментарий if f then repeat writef getf until f else if f then repeat writef getf until f writef getf end end writeln getf end pageoutput printtreeroot end Программа 2.2. Построение таблицы перекрестных ссылок. 2. В качестве ключа хранятся только первые с1 символов.

Таким образом, два слова, у которых первые с1 символов не различаются, считаются одинаковыми. 3. Эти с1 символов упаковываются в массив id типа alfa.Если достаточно мало, во многих вычислительных машинах такие упакованные массивы могут сравниваться с помощью одной команды. 4. Переменная k1 это индекс, который, используется в следующем инвариантном условии, касающемся буфера символов а аi для i k1 1 cl.

Это означает, что слова, состоящие из менее чем с1 символов, дополняются соответствующим количеством пробелов. 5. Желательно, чтобы номера строк в таблице перекрестных ссылок печатались в возрастающем порядке. Поэтому список отметок должен формироваться в. том же. порядке, в каком они печатаются. Это требование предполагает использование в каждом слове-узле двух ссылок, из которых одна указывает на первый, а вторая на последний элемент списка отметок.

6. Сканер строится таким образом, что слова в кавычках и внутри комментариев не включаются в таблицу перекрестных ссылок при этом предполагается, что кавычки и комментарии не переходят через концы строк. В табл. 1.2 показан результат обработки некоторого текста программы. 2.3. Удаление из дерева. Теперь мы переходим к задаче, обратной включению, а именно удалению. Нам нужно построить алгоритм для удаления узла с ключом х из дерева с упорядоченными ключами.

К сожалению, удаление элемента обычно не так просто, как включение. Таблица 2.1. Пример распечатки, полученной в результате работы программы 2.2. 1. PROGRAM PERMUTE OUTPUT 2. CONST N 4 3. VAR IINTEGER 4. AARRAY1 N OF INTEGER 5. 6. PROCEDURE PRINT 7. VAR IINTEGER 8. BEGIN FOR I1 TO N DO WRITE AI3 9. WRITELN 10. END PRINT 11. 12.

PROCEDURE PERM KINTEGR 13. VAR I,XINTEGER 14. BEGIN 15. IF K1 THEN PRINT ELSE 16. BEGIN PERM K-1 17. FOR I1 TO K-1 DO 18. BEGIN XAIAK AKX 19. PERM K-1 20. XAI AI AK AKX 21. END 22. END 23. END PERM 24. 25. BEGIN 26. FOR I1 TO N DO AI 1 27. PERMN 28. END. ARRAY 4 A 4 8 18 18 18 20 20 20 20 26

BEGIN 8 14 16 18 25 CONST 2 DO 8 17 26 ELSE 15 EMD 10 21 22 23 28 FOR 8 17 26 IF 15 INTEGER 3 4 8 12 13 I 3 7 8 8 13 17 18 18 20 20 26 26 26 K 12 15 16 17 18 18 19 20 20 N 2 4 8 26 27 OF 4 OUTPUT 1 PERMUTE 1 PERM 12 16 19 27 PRINT 6 15 PROCEDURE 6 12 PROGRAM 1 THEN 15 TO 8 17 26 VAR 3 17 13 WRITELN 9

WRITE 8 X 13 18 18 20 20 Оно просто в случае, когда удаляемый элемент является терминальным узлом или имеет одного потомка. Рис. 12. Удаление из дерева. Трудность заключается в удалении элементов с двумя потомками, поскольку мы не можем указывать одной ссылкой на два направления. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева.

Ясно, что такие элементы не могут иметь более одного потомка. Подробно это показано в рекурсивной процедуре, называемой delete 2.12. Она различает три случая 1. Компоненты с ключом, равным х, нет. 2. Компонента с ключом х имеет не более одного потомка. 3. Компонента с ключом х имеет двух потомков. procedure delete x integer var pref var q ref procedure

del var r ref begin if r.right nil then del r.right else begin q.key r.key q.count r.count q r r r.left end end begin delete 2.12 if p nil then writeln word is not in tree else if x p.key then deletex, p.left else if x p.key then deletex, p.right else begin delete p q p if q.right nil then p q.left else if q.left nil then p q.right else del q.left disposeq end end delete Вспомогательная рекурсивная процедура del вызывается только в 3-м случае.

Она спускается вдоль самой правой ветви левого поддерева удаляемого узла q и затем заменяет существенную информацию ключ и счетчик в q соответствующими значениями самой правой компоненты r этого левого поддерева, после чего от r можно освободиться. Процедуру disposeq можно рассматривать как обратную процедуре newq. Последняя занимает память для новой компоненты, а первая может применяться для указания вычислительной системе, что память, которую занимает q, можно освободить и потом вновь использовать некоторый вид чистки

памяти. Для иллюстрации работы процедуры 2.12 мы отсылаем читателя к рис. 12. Задано начальное дерево а, из которого последовательно удаляются узлы с ключами 13, 15, 5, 10. Полученные деревья показаны на рис. 12 b е. 3. Технологическая часть. Список литературы 1. Н. Вирт Алгоритмы структуры данных программа. 2. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс.

Учебное пособие. М. Издательство ОМД Групп. 3. Фаронов В.В. Delphi 6. Учебный курс. М. Издатель Молгачева С.В 2003.