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

Содержание 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 обозначает корень, а А и В левое и правое поддеревья, мы може... left postordert .right 2.3 Pt end end procedure inordert ref begin if ... программу 1.1. Очевидно, что дерево намного более подходящая форма организации такого... nil Л - found do begin 2.6 if t .key x then found true else if t .key ...

Поиск по дереву с включением

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

Технологическая часть

Технологическая часть.

Список литературы

Список литературы 1. Н. Вирт Алгоритмы структуры данных программа. 2. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. М. Издательство ОМД Групп. 3. Фаронов В.В. Delphi 6. Учебный курс. М. Издатель Молгачева С.В 2003.