Бинарное дерево паскаль реализация — Мир ПК

Бинарное дерево паскаль реализация

страницы: 1 2 3 4

Содержание

Способы представления деревьев

Поскольку любое дерево является графом , то его можно задавать любым из способов, перечисленных в п. «Способы представления графов ». Однако существуют и специальные способы представления, предназначенные только для деревьев . Мы рассмотрим только два наиболее распространённых частных случая.

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

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

Разумеется, в общем случае значение переменной S (количество потомков ) может достигать N-1 ( N — количество всех вершин в дереве ). Однако ясно, что в такой ситуации особого смысла в динамической древесной структуре нет: экономии памяти не получается. Гораздо лучше, если у всех вершин примерно одинаковое и заранее известное количество потомков .

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

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

Примеры использования деревьев

Здесь мы ограничимся только примерами использования бинарных корневых деревьев : именно такой вид графа чаще всего применяется в программировании.

Дерево двоичного поиска

Дерево двоичного поиска для множества чисел S — это размеченное бинарное дерево , каждой вершине которого сопоставлено число из множества S , причём все пометки удовлетворяют следующим условиям:

1. существует ровно одна вершина , помеченная любым числом из множества S ;
2. все пометки левого поддерева строго меньше, чем пометка текущей вершины ;
3. все пометки правого поддерева строго больше, чем пометка текущей вершины .

Если выражаться простым языком, то структура дерева двоичного поиска подчиняется простому правилу: «если больше — направо, если меньше — налево».

Например, для набора чисел 7 , 3 , 5 , 2 , 8 , 1 , 6 , 10 , 9 , 4 , 11 получится такое дерево (см. рис. 11.14 ).

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

Более подробно процессы построения и анализа дерева бинарного поиска будут изложены в следующей лекции , посвящённой алгоритмам, использующим деревья и графы .

Рис. 11.14. Дерево двоичного поиска

Дерево частотного словаря

Дерево частотного словаря — это результат построения дерева двоичного поиска не для чисел, а для слов некоторого текста. Генерирование дерева частотного словаря полезно при подсчёте количества вхождений каждого слова в некоторый текст.

Приведём описание структуры этого дерева :

Дерево синтаксического анализа

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

Например, на рис. 11.15 изображено дерево синтаксического анализа для выражения ((a / (b + c)) + (x * (y — z))) .

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

Рис. 11.15. Дерево синтаксического анализа

TURBO PASCAL

Цель: изучить фундаментальную абстрактную структуру — дерево

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

В повседневной жизни мы очень часто встречаем примеры деревьев, и Вы уже наверняка знакомы с этой концепцией.

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

Второй пример — это структура большой организации; использование древообразной структуры для представления ее «иерархической структуры» ныне широко используется во многих компьютерных задачах.

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

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

Самые простые из деревьев считаются бинарные деревья.

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

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из девяти узлов, А-корень дерева. Его левое поддерево имеет корень В, а правое- корень С. Это изображается двумя ветвями, исходящими из А: левым — к В и правым — к С. Отсутствие ветви обозначает пустое поддерево.
Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и I имеют пустые левые и правые поддеревья.

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

Если А — корень бинарного дерева и В — корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А.

Узел, не имеющий сыновей (такие как узлы D, G, Н и I), называется листом.

Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2. Например, в дереве из рисунке А-предок G и Н-потомок С, но Е не является ни предком, ни потомком С.

Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

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

Свойство 1. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов.

Уровень узла в бинарном дереве может быть определен следующим образом. Корень дерева имеет уровень 0, и уровень любого другого узла дерева имеет уровень на 1 больше уровня своего отца.

Например, в бинарном дереве на первом рисунке узел Е- узел уровня 2, а узел Н-уровня 3.

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

Стало быть, глубина дерева на первом рисунке равна 3.

Полное бинарное дерево уровня n — это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья

На рисунке приведен пример полного бинарного дерева уровня 3.

Почти полное бинарное дерево — это бинарное дерево, для которого существует неотрицательное целое k такое, что

1. Каждый лист в дереве имеет уровень k или k+1.

2. Если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

Строго бинарное дерево из рис. а не является почти полным, поскольку оно содержит листы уровней 1, 2 и 3, нарушая тем самым условие 1.

Строго бинарное дерево на рис. 6 удовлетворяет условию 1, так как каждый лист имеет уровень 2 или 3. Однако при этом нарушается условие 2, поскольку А имеет не только правого потомка уровня 3 (J), но также и левого потомка, являющегося листом уровня 2 (Е).

Строго бинарное дерево на рис. в удовлетворяет обоим условиям и, следовательно, является почти полным бинарным деревом.

Бинарное дерево на рис. г-также почти полное бинарное дерево, но оно не является строго бинарным, поскольку узел Е имеет лишь левого сына.

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

Есть еще одна разновидность бинарных деревьев, которая называется упорядоченные бинарные деревья.

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

Структура бинарного дерева построена из узлов.

Узел дерева содержит поле данных и два поля с указателями.

Поля указателей называются левым указателем и правым указателем, поскольку они указывают на левое и правое поддерево, соответственно. Значение nil является признаком пустого дерева.

Тогда бинарное дерево можно будет представить в следующем виде.

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

Существует 3 способа обхода бинарного дерева.

1. в прямом порядке
2. в симметричном порядке
3. в обратном порядке

В прямом порядке:

1. Попасть в корень
2. Пройти в прямом порядке левое поддерево
3. Пройти в прямом порядке правое поддерево

В симметричном порядке:

1. Пройти в симметричном порядке левое поддерево
2. Попасть в корень
3. Пройти в симметричном порядке правое поддерево

В обратном порядке:

1. Пройти в обратном порядке левое поддерево
2. Пройти в обратном порядке правое поддерево
3. Попасть в корень

Давайте для закрепления полученных знаний напишем программу.

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

Итак, на сегодняшнем занятии мы познакомились с деревьями и основными операциями над ними.

(с)Все права защищены

По всем интересующим вопросам прошу писать на электронный адрес

Бинарное дерево паскаль реализация

Бинарные деревья (основные понятия)

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

Узел дерева, не имеющий потомков, называется листом.

Схематичное изображение бинарного дерева:

Бинарное дерево может представлять собой пустое множество, и может выродиться в список. Вырожденное бинарное дерево:

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

Бинарное дерево должно реализовывать следующие операции:

Инициализация бинарного дерева:
текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.

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

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

Рассмотрим эти операции более подробно:

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

При создании дерева вызывается рекурсивная процедура следующего вида: Эта процедура добавляет элемент X к дереву, учитывая величину X. При этом создается новый узел дерева.

Получить значение текущего элемента можно так:

Поиск заданного элемента (функция возвращает адрес узла с найденным элементом; если элемент в дереве не найден, возвращается nil):

Удаление узла бинарного дерева.

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

Поступаем так:

• если удаляемый узел имеет только одного «сына», то его значение можно заменить значением этого «сына»
• если у удаляемого элемента 2 «сына», заменяем его элементом с наименьшим значением среди потомков правого «сына» (или элементом с наибольшим значением среди потомков левого «сына»)

Читать еще:  Динамические данные паскаль

Для реализации процедуры Remove желательно иметь функцию DeleteMin, которая будет удалять наименьший элемент непустого дерева Root, и возвращать значение удаленного элемента: Теперь процедура Remove может быть реализована так:

Уничтожение бинарного дерева.

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

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

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

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

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

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

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

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

Еще один вариант обхода — по уровням : сначала выводить корень, потом — все узлы первого уровня, за ними — узлы второго уровня, и т.д.

Это реализуется вот такой процедурой: Вызывать процедуру надо вот так:

Графическое представление бинарного дерева

Для отрисовки бинарного дерева в графическом режиме можно использовать процедуру PrintTreeGraph.
Примечание : приведенная процедура работает с деревьями, состоящими из символов (T = Char) или строк (T = String). Для того, чтобы она работала с другими типами, необходимо изменить функцию так, чтобы она преобразовывала необходимый тип к строке.
pgt.pas

Применение бинарных деревьев

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

Присоединенный модуль содержит основные функции для работы с бинарными деревьями.
treeunit.pas

Кроме основных функций в модуле содержится процедура подсчета числа «листьев» — узлов, не содержащих потомков (количество листьев возвращается в переменной k): Процедуры обхода: Пример программы, использующей реализацию бинарного дерева:

Нерекурсивная работа с бинарным деревом

Для итеративного добавления элемента к бинарному дереву может применяться следующая процедура:

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Занятие №15. Часть 2: Динамические структуры данных: стеки и очереди

Стеки

Стек — динамическая структура данных, в которой добавление и удаление элементов доступно только с одного конца (с верхнего (последнего) элемента).

Существуют такие сокращения:

LIFO = Last In -> First Out — с английского языка «Кто последним вошел, тот первым вышел»

FILO = First In -> Last Out — «первым вошел, последним вышел»

Последовательные этапы засылки в стек чисел 1, 2, 3

Над стеком выполняются следующие операции:

• добавление в стек нового элемента;
• определение пуст ли стек;
• доступ к последнему включенному элементу, вершине стека;
• исключение из стека последнего включенного элемента.

Создание структуры узла:

Добавление элемента в стек:

procedure Push( var Head: PNode; x: char); var NewNode: PNode; begin New(NewNode); < выделение памяти >NewNode^.data := x; < запись символа >NewNode^.next := Head; < сделать первым узлом >Head := NewNode; end;

Забор элемента с вершины:

function Pop ( var Head: PNode ): char; var q: PNode; begin if Head = nil then begin < если стек пустой >Result := char(255); < неиспользуемый символ, т.е. ошибка >Exit; end; Result := Head^.data; < берем верхний символ >q := Head; < запоминаем вершину >Head := Head^.next; < удаляем вершину >Dispose(q); < удаление из памяти >end;

Проверка, пустой ли стек:

function isEmptyStack ( S: Stack ): Boolean; begin Result := (S = nil); end;

Объявления в основной программе:

var S: PNode; . S := nil;

Рассмотрим подробную работу со стеком на примере:

Алгоритм выполнения задания:

1. изначально стек пустой;
2. в цикле просматриваем каждый символ строки;
3. если текущий символ – открывающая угловая скобка, то вставляем ее на вершину стека;
4. если текущий символ – закрывающая угловая скобка, то проверяем верхний элемент стека: там должна находиться открывающая угловая скобка (иначе — ошибка);
5. в конце стек должен стать пустым, иначе — ошибка.

Читать еще:  Константы и переменные паскаль

Создаем структуру стека:

const MAXSIZE = 50; type Stack = record < стек рассчитан на 50 символов >tags: array[1..MAXSIZE] of char; size: integer; < число элементов >end;

Процедура добавления элемента в стек:

procedure Push( var S: Stack; x: char); begin if S.size = MAXSIZE then Exit; // выход, если произошло переполнение стека S.size := S.size + 1; S.tags[S.size] := x; // добавляем элемент end;

Функция взятия элемента с вершины:

function Pop ( var S:Stack ): char; begin if S.size = 0 then begin Result := char(255); // 255 — пустой символ, ошибка — стек пуст Exit; end; Result := S.tags[S.size]; S.size := S.size — 1; end;

Создаем функцию для проверки, пустой ли стек:

function isEmptyStack ( S: Stack ): Boolean; begin Result := (S.size = 0); end;

var expr: string; br1, br2: char; < угловые скобки >i, k: integer; upper: char; < верхний символ, снятый со стека >error: Boolean; < признак ошибки >S: Stack; begin br1 := ‘ ‘; S.size := 0; error := False; writeln(‘Введите html-текст’); readln(expr); . < здесь вставляется цикл с обработкой строки >if not error and isEmptyStack(S) then writeln(‘Текст верный.’) else writeln(‘Текст составлен неверно.’) end.

Обработка строки в цикле:

for i:=1 to length(expr) < проходимся по всем символам строки expr >do begin if expr[i] = br1 then begin < открывающая скобка br1; < ошибка: стек пуст или не та скобка >break; end; if error then break; // была ошибка, значит, прерываем цикл end;

Очереди

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

Существует сокращение для очереди: FIFO = First In – First Out, с английского — «Кто первым вошел, тот первым вышел».

Для очереди доступны следующие операции:

• добавить элемент в конец очереди (PushTail);
• удалить элемент с начала очереди (Pop).

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

Работа с очередью с помощью кольцевого массива:

Если в очереди 1 элемент:

Если очередь пуста:

Если очередь заполнена:

Определение размера массива (при пустой и заполненной очереди):

Очередь в Паскале (использование кольцевого массива)

Создание структуры:

type Queue = record data: array[1..MAXSIZE] of integer; head, tail: integer; end;

Как добавить в очередь:

procedure PushTail( var Q: Queue; x: integer); begin if Q.head = (Q.tail+1) mod MAXSIZE + 1 then Exit; < очередь уже полна >Q.tail := Q.tail mod MAXSIZE + 1; Q.data[Q.tail] := x; end;

Как выбрать из очереди:

function Pop ( var S: Queue ): integer; begin if Q.head = Q.tail mod MAXSIZE + 1 then begin Result := MaxInt; Exit; end; Result := Q.data[Q.head]; Q.head := Q.head mod MAXSIZE + 1; end;

Создание очереди посредством списка

Объявление узла:

type PNode = ^Node; Node = record data: integer; next: PNode; end; type Queue = record head, tail: PNode; end;

Добавляем новый элемент:

procedure PushTail( var Q: Queue; x: integer ); var NewNode: PNode; begin New(NewNode); NewNode^.data := x; NewNode^.next := nil; if Q.tail <> nil then Q.tail^.next := NewNode; Q.tail := NewNode; if Q.head = nil then Q.head := Q.tail; end;

Выбираем элемент из списка:

function Pop ( var S: Queue ): integer; var top: PNode; begin if Q.head = nil then begin Result := MaxInt; Exit; end; top := Q.head; Result := top^.data; Q.head := top^.next; if Q.head = nil then Q.tail := nil; Dispose(top); end;

Дек — англ. double ended queue, т.е. очередь с двумя концами – это динамическая структура данных, добавлять и удалять элементы в которой можно с обоих концов.

Деревья

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

• Корнем называется главный или начальный узел дерева.
• Листом называется узел, из которого не выходят дуги.

Перечислим некоторые иерархические отношения в дереве:

1 — предок для всех других узлов в дереве
6 — потомок для узлов 5, 3 и 1
3 — родитель узлов 4 и 5
5 — сын узла 3
5 — брат узла 4

Высота дерева определяется как наибольшее расстояние от корня до листа (количество дуг).

Двоичные деревья

В двоичном (бинарном) дереве каждый узел имеет не более двух дочерних узлов (сыновей).
Объявление:

type PNode = ^Node; < указатель на узел >Node = record data: integer; < данные >left, right: PNode; end;

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

• если дерево пустое, значит, ключ не найден;
• если ключ узла равен k, то остановка;
• если ключ узла меньше k, то искать k в левом поддереве;
• если ключ узла больше k, то искать k в правом поддереве.

Сравним поиск в массиве c n элементами с поиском в бинарном дереве:

Поиск в массиве: каждое сравнение — отбрасываем 1 элемент.
Число сравнений – N.

При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений

Поиск в бинарном дереве на Паскале:

Создадим функцию для поиска. На вход функции из главной программы подаются два параметра: tree — адрес корня дерева и x — искомое число. Функция возвращает адрес узла с искомым значением или nil, если ничего не найдено.

function SearchInTree(Tree: PNode; x: integer): PNode; begin if Tree = nil then begin Result := nil; Exit; end; if x = Tree^.data then Result := Tree else if x