Динамические структуры данных: деревья

Размещено на http://www.allbest.ru/

Введение

В данной работе рассмотрим тему: «Динамические структуры данных: деревья».

Актуальность исследуемой проблемы. В языках программирования (Pascal, C, др.) существует способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.

Работа с динамическими величинами связана с использованием еще одного типа данных -- ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Предметом данного исследования являются динамические структуры данных в программировании.

Объектом исследования являются деревья в динамических структурах данных.

Цель данной курсовой работы - это изучить динамические структуры данных, а именно деревья.

Для достижения поставленной цели необходимо решить следующие задачи:

- рассмотреть понятие, сущность и необходимость динамических структур данных;

- изучить классификацию динамических структур данных;

- выявить динамические структуры данных, а именно деревья;

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

При написании данной работы использовался метод анализа научной литературы отечественных и зарубежных авторов, таких как Кернигана Б., Ритчи Д., Подбельского В. В., Фомина С. С., Будниковой Н.А., Хабибуллина И.Ш., Абилова К.С., Бабаева М.А., Галагузовой М.А. и др.

Глава 1. Теоретические аспекты динамических структур данных: деревья

1.1 Понятие, сущность и необходимость динамических структур данных

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

Динамические структуры данных - это структуры данных, память под которые выделяется и освобождается по мере необходимости.

Динамическая структура данных характеризуется тем что:

- она не имеет имени;

- ей выделяется память в процессе выполнения программы;

- количество элементов структуры может не фиксироваться;

- размерность структуры может меняться в процессе выполнения программы;

- в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры.

Каждой динамической структуре данных сопоставляется статическая переменная типа указатель (ее значение - адрес этого объекта), посредством которой осуществляется доступ к динамической структуре.

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

Необходимость в динамических структурах данных обычно возникает в следующих случаях.

Используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других.

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

Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

Динамические структуры, по определению, характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.

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

Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур:

- размер структуры ограничивается только доступным объемом машинной памяти;

- при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;

- большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

- на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

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

Порядок работы с динамическими структурами данных следующий:

- создать (отвести место в динамической памяти);

- работать при помощи указателя;

- удалить (освободить занятое структурой место).

1.2 Классификация динамических структур данных

Для того, чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.

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

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

Динамические структуры данных бывают линейные и нелинейные. В линейной динамической структуре данные связываются в цепочку. К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Организация нелинейных структур более сложная. Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).

Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят:

- однонаправленные (односвязные) списки;

- двунаправленные (двусвязные) списки;

- циклические списки;

- стек;

- дек;

- очередь;

- бинарные деревья.

Они отличаются способом связи отдельных элементов и/или допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти.

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

1.3 Динамические структуры данных: деревья

Дерево -- это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский-дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.

Каждое дерево обладает следующими свойствами:

- существует узел, в который не входит ни одной дуги (корень);

- в каждую вершину, кроме корня, входит одна дуга.

Дерево -- это связный граф без циклов. Кроме того, в дереве выделена одна вершина, которая называется корнем дерева. Остальные вершины упорядочиваются по длине пути от корня дерева (см. рис. 1).

Рисунок 1 Динамическая структура данных: дерево

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

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



Рисунок 2 Динамическая структура данных-дерево (оглавление книги)

Представим, что книга состоит из частей, части -- из глав, главы -- из параграфов. Сама книга представляется корнем дерева, из которого выходят ребра к вершинам, соответствующим частям книги. В свою очередь, из каждой вершины-части книги выходят ребра к вершинам-главам, входящим в эту часть, и так далее. Файловую систему компьютера также можно представить в виде дерева. Вершинам соответствуют каталоги (их также называют директориями или папками) и файлы. Из вершины-каталога выходят ребра к вершинам, соответствующим всем каталогам и файлам, которые содержатся в данном каталоге. Файлы представляются терминальными вершинами дерева. Корню дерева соответствует корневой каталог диска. Программы, осуществляющие работу с файлами, такие, как Norton Commander в системе MS DOS или Проводник Windows, могут изображать файловую систему графически в виде дерева.

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

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

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

Итак, деревья относятся к разряду структур, которые удобно строить в динамической памяти с использованием указателей. Наиболее важный тип деревьев - двоичные (бинарные) деревья, в которых каждый узел имеет самое большее два поддерева: левое и правое. Подробнее, если имеем дерево вида (см. рис.3a), то ему может соответствовать в динамической памяти структура (см. рис.3б).

Рисунок 3 Двоичное дерево и его представление с помощью списочных структур памяти а - двоичное дерево; б - представление дерева с помощью списков с использованием звеньев одинакового размера

Для построения такого бинарного дерева используется следующий ссылочный тип:

type

T = Integer; { скрываем зависимость от конкретного типа данных }

TTree = ^TNode;

TNode = record

value: T;

Left, Right: TTree;

end;

Здесь поля Left и Right - это указатели на потомков данного узла, а поле value предназначено для хранения информации.

1.4 Операции над бинарными деревьями

Для бинарных деревьев определены операции:

1. формирование корня дерева

2. включение узла в дерево

3. поиск по дереву

4. обход дерева

5. удаление узла.

Для работы с деревьями имеется множество алгоритмов. К наиболее важным относятся задачи построения и обхода деревьев. Пусть в программе дано описание переменных: var t: ptr; s: integer; c: char; b: boolean;

Тогда двоичное дерево можно построить с помощью следующей рекурсивной процедуры:

procedure V (var t: ptr) var st: string begin readln (st) if st<>'. 'then begin new (t) t. info: =st V (t. Llink) V (t. Rlink) end else t: =nil end

Структура дерева отражается во входном потоке данных: каждой вводимой пустой связи соответствует условный символ (в данном случае точка). Для примера на рис.3 входной поток имеет вид:

Существует три основных способа обхода деревьев: в прямом порядке, обратном и концевом. Обход дерева может быть выполнен рекурсивной процедурой и процедурой без рекурсии (стековый обход). В приведенной ниже рекурсивной процедуре выполняется обход дерева в обратном порядке.

Нерекурсивный алгоритм обхода дерева в прямом порядке:

Пусть T - указатель на бинарное дерево; А - стек, в который заносятся адреса еще не пройденных вершин; TOP - вершина стека; P - рабочая переменная.

1. Начальная установка: TOP: =0; P: =T.

2. Если P=nil, то перейти на 4. {конец ветви}

3. Вывести P. info. Вершину заносим в стек: TOP: =TOP+1; A [TOP]: =P; шаг по левой ветви: P: =P. llink; перейти на 2.

4. Если TOP=0, то КОНЕЦ.

5. Достаем вершину из стека: P: =A [TOP]; TOP: =TOP-1;

Шаг по правой связи: P: =P. rlink; перейти на 2.

Итак, деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа - с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения).

Глава 2. Реализация операций по работе с бинарными деревьями

2.1 Описание программы

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

Для описания узла бинарного дерева в программе введем тип, имеющий вид следующей записи:

type

PNode = ^TNode;

TNode = record

Info : string; {поле данных}

Left,Right : PNode; {указатели на левое и правое поддеревья}

end;

Процедура создания нового узла.

{ Создание нового узла со значением информационного поля X.

Возвращается указатель на новый узел}

function NewNode(X:string):PNode;

var

P : PNode;

begin

New(P);

P^.Info := X;

P^.Left := Nil;

P^.Roght := Nil;

NewNode := P;

end;

Процедура создания потомка (поддерева)

procedure SetLeft(P:PNode; X:string);

begin

P^.Left := NewNode(X);

end;

3. Создание бинарного дерева:

- данные (целые числа) заносятся с клавиатуры;

- дубликаты не включаются (но выводятся на экран);

- признаком окончания ввода является ввод числа 0;

- результат - бинарное упорядоченное дерево.

При обработке динамических структур типа «дерево» чаще всего используются рекурсивные алгоритмы.

Рекурсия предполагает определение некоторого понятия с использованием самого этого понятия. Никлаус Вирт приводит следующее утверждение о возможностях рекурсии:

При обработке динамических структур типа «дерево» чаще всего используются рекурсивные алгоритмы.

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

Примером рекурсивного определения является факториал неотрицательного числа:

n! = 1 при n=0

n! = n*(n-1)! при n >0

В Турбо-Паскале рекурсия разрешена: подпрограмма может вызывать сама себя:

program FactDemo;

var

k : integer;

function Factor(n:integer):integer;

begin

if n=0 then

Factor : 1

else

Factor := n * Factor(n-1);

{end if}

end;

begin

write('Введите целое число ');

readln(k);

if k>=0 then

writeln('Факториал ',n:1,' = ', Factor(k));

{end if}

end.

Первое значение Factor вычисляется, когда n=0, оно подставляется в соответствующий экземпляр памяти. Теперь на каждом очередном шаге значения всех членов выражения n*Factor(n-1) известны, и алгоритм подставляет в это выражение значение, полученное на предыдущем шаге. Это происходит в процессе свертывания рекурсии.

Сформулируем два важных свойства рекурсивных алгоритмов:

1. Наличие тривиального случая.

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

Для функции «факториал» тривиальный случай: «0!=1».

2. Определение сложного случая в терминах более простого.

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

Иными словами рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая.

Для функции «факториал» вместо вычисления n! заменяется умножением n*(n-1)!, и при этом с каждым вызовом значение n уменьшается, стремясь к нулю и достигая его за конечное число вызовов.

Из определения структуры типа «дерево» видно, что она рекурсивна по определению, а в силу этого рекурсивными являются и практически все алгоритмы работы с деревьями. Для этого достаточно посмотреть на приведенный выше пример создания бинарного упорядоченного дерева.

В процедуре Add имеется тривиальный случай (когда дерево пустое) и

рекурсивные вызовы: добавить в левое и правое поддеревья - Add (NewData,Root^.left) и Add(NewData,Root^.right).

Алгоритмы работы с деревьями

В приведенных ниже алгоритмах предполагается, что узел (элемент) дерева декларирован следующей записью:

Type

PNode = ^TNode;

TNode = record

Data : integer; {информационное поле}

left,right : PNode;

end;

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

function Sum(Root : PNode) : integer;

begin

if Root=Nil then {узел - пустой}

Sum := 0

else

Sum := Root^.Data + Sum(Root^.left)

+ Sum(Root^.right);

{end if}

end;

Для нетривиального случая результат вычисляется как значение информационного элемента в корне (Root^.Data) плюс суммы информационных полей левого и правого поддеревьев.

А выражение Sum(Root^.left)представляет собой рекурсивный вызов левого поддерева для данного корня Root.

А2. Подсчет количества узлов в бинарном дереве

function NumElem(Tree:PNode):integer;

begin

if Tree = Nil then

NumElem := 0

else

NumElem := NumElem(Tree^.left)+ NumElem(Tree^.right) + 1;

end;

Подсчет количества листьев бинарного дерева

function Number(Tree:PNode):integer;

begin

if Tree = Nil then

Number := 0 {дерево пустое - листов нет}

else if (Tree^.left=Nil) and (Tree^.right=Nil) then

Number := 1 {дерево состоит из одного узла - листа}

else

Number := Number(Tree^.left) + Number(Tree^.right);

{end if}

end;

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

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

Алгоритмы просмотра дерева

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

Прежде чем увидеть, к каким результатам это может привести, приведем

их.

Просмотр дерева слева - направо

procedure ViewLR(Root:PNode); {LR -> Left - Right }

begin

if Root<>Nil then

begin

ViewLR(Root^. left); {просмотр левого поддерева}

{Операция обработки корневого элемента - вывод на печать, в файл и др.}

ViewLR(Root^.right); { просмотр правого поддерева }

end;

end;

Просмотр справа налево

procedure ViewRL(Root:PNode); {LR -> Right - Left}

begin

if Root<>Nil then

begin

ViewRL(Root^.right); { правого }ViewRL(Root^.left); { левого }

end;

end;

Просмотр сверху - вниз

procedure ViewTD(Root:PNode); {TD -> Top-Down}

begin

if Root<>Nil then

begin

Операция обработки корневого элемента - вывод на печать, в файл и др.

ViewTD(Root^.left); {просмотр левого поддерева}

ViewTD(Root^.right); { просмотр правого поддерева }

end;

end;

Просмотр снизу-вверх

procedure ViewDT(Root:PNode); {DT -> Down - Top}

begin

if Root<>Nil then

begin

ViewDT(Root^.left); {просмотр левого поддерева}

ViewDT(Root^.right); { просмотр правого поддерева }

end;

end;

Поиск элемента в двоичном упорядоченном дереве

function Search(SearchValue:integer;Root:PNode):PNode;

begin

if (Root=Nil) or (Root^.Data=SearchValue) then

Search := Root

else if (Root^.Data > SearchValue) then

Search := Search(SearchValue,Root^.left)

else

Search := Search(SearchValue,Root^.right);

end;

2.2 Текст программы

бинарный дерево динамический алгоритм

type link = ^element;

element = record

data : integer;

left : link;

right : link;

end;

var

m,x, depth, minim : integer;

pn : link;

procedure add(var n : link; arg:integer);

var

ind, neo : link;

begin

new(neo);

neo^.data:=arg;

neo^.left:=nil;

neo^.right:=nil;

if n=nil then n:= neo

else begin

ind:=n;

while neo<>nil do begin

if arg<ind^.data then begin

if ind^.left=nil then begin

ind^.left:=neo;

neo:=nil

end

else ind:=ind^.left

end

else

if arg>ind^.data then begin

if ind^.right=nil then begin

ind^.right:=neo;

neo:=nil

end

else ind:=ind^.right

end

else begin

writeln('Such element is already existent');

neo:=nil;

end;

end;

end;

end; { add }

procedure restruct(var d : link);

var

ind1, ind2 : link;

begin

ind1:=d;

if ind1^.right=nil then begin

ind2:=d;

d:=ind2^.left;

dispose(ind2)

end

else

if ind1^.left=nil then begin

ind2:=d;

d:=ind2^.right;

dispose(ind2)

end

else begin

ind2:=ind1^.left;

while ind2^.right<>nil do begin

ind1:=ind2;

ind2:=ind2^.right;

end;

ind1^.right:=ind2^.left;

ind2^.left:=d^.left;

ind2^.right:=d^.right;

dispose(d);

d:=ind2;

end;

end; { restruct }

procedure delete(var n : link; arg:integer);

var

del, ind : link;

t : boolean;

begin

t:=false;

del:=n;

while (del<>nil) and (not t) do begin

if arg=del^.data then t:=true

else

if arg<del^.data then begin

ind:=del;

del:=del^.left;

end

else begin

ind:=del;

del:=del^.right;

end;

end;

if t then begin

if (del^.left=nil) and (del^.right=nil) then begin

if del=n then begin n:=nil; dispose(del) end else

if ind^.left=del then begin

ind^.left:=nil;

dispose(del)

end

else begin

ind^.right:=nil;

dispose(del)

end

end

else

if del=n then restruct(n) else

if ind^.left=del then restruct(ind^.left)

else restruct(ind^.right)

end

else writeln('Element is absent');

end; { delete }

procedure view( n : link; var d:integer);

var

i : integer;

begin

for i:=1 to d do begin

write(' ') end;

writeln(n^.data);

if (n^.left=nil) and (n^.right=nil) then d:=d-1

else begin

if n^.right<>nil then begin

d:=d+1;

view(n^.right,d);

end;

if n^.left<>nil then begin

d:=d+1;

view(n^.left, d);

end;

d:=d-1;

end;

end; { view }

procedure obhod1( n : link; var d, min:integer);

begin

if (n^.left=nil) and (n^.right=nil) then begin

if d<min then min:=d;

d:=d-1 end

else begin

if n^.right<>nil then begin

d:=d+1;

obhod1(n^.right, d, min); end;

if n^.left<>nil then begin

d:=d+1;

obhod1(n^.left, d,min) end;

d:=d-1;

end;

end; { obhod1 }

procedure obhod2( n : link; var d:integer; min:integer);

begin

if (n^.left=nil) and (n^.right=nil) then begin

if d=min then writeln(n^.data);

d:=d-1;

end

else begin

if n^.right<>nil then begin

d:=d+1;

obhod2(n^.right,d,min);

end;

if n^.left<>nil then begin

d:=d+1;

obhod2(n^.left, d,min);

end;

d:=d-1;

end;

end; { obhod2 }

begin

m:=1;

pn:=nil;

while m<>0 do begin

writeln;

writeln('--- Type "1" to ADD new element');

writeln('--- Type "2" to DELETE element');

writeln('--- Type "3" to VIEW tree');

writeln('--- Type "4" to FIND elements with minimal depth');

writeln('--- Type "0" to EXIT program');

writeln;

write('Enter : ');

readln(m);

writeln;

case m of

1 : begin

write('Enter new element : ');

readln(x);

add(pn, x);

end;

2 : begin

write('Enter element you want to delete : ');

readln(x);

delete(pn, x);

end;

3 : begin

depth:=1;

if pn=nil then writeln('The tree is empty') else begin

writeln('The tree is : ');

view(pn, depth);

end;

end;

4 : begin

depth:=1;

minim:=20;

if pn<>nil then begin

writeln('Elements with minimal depth');

obhod1(pn,depth,minim);

writeln(minim);

depth:=1;

obhod2(pn,depth,minim);

end

else writeln('The tree is empty');

end;

end; { case }

end;

end.

Заключение

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

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

Деревья особенно часто используют на практике при изображении различных иерархий.

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

Список используемой литературы

• Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си. М.: Финансы и статистика, 2011 г., стр. 290

• Керниган Б., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 2012 г., стр. 270

• Подбельский В. В., Фомин С. С. Программирование на языке Си. Учеб.пособие. М.: Финансы и статистика, 2010 г., стр. 600

• Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ, Ростов на Дону, 2011 г., стр. 350

• Хабибуллин И.Ш. Программирование C++: Пер. с англ. - 3-е изд. - СПб.: БХВ-Петербург, 2012 г., стр. 512

• Абилов К.С. Информатика для вузов. Москва, 2011 г., стр. 290

• Бабаев М.А. Программирование и его основы. Уфа, 2010 г., стр. 320

• Галагузова М.А. Информатика. Высшая школа. № 7, 2012 г., стр. 380

• Голант Е.Я. Информатика. М., 2011 г., стр. 250

• Кантарбаев С.Е. Языки программирования. Алма-Ата, 2012 г., стр. 340

• Лордкипанидзе Д.О. Принципы организации и методы программирования. М., 2010 г., стр. 269

Размещено на Allbest.ru

...