Главная | Обратная связь
МегаЛекции

Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)




{Процедура удаления звена из списка после звена, на которое ссылается указатель Pred; в x содержится информация из удалённого звена} Procedure Iz_Spiska(Pred : U; Var X : BT); Var Vsp : U; Begin Vsp := Pred^.Next; {Забираем ссылку на удаляемое звено} {Удаляем звено из списка, перенаправив ссылку на следующее за ним звено} Pred^.Next := Pred^.Next^.Next; X := Vsp^.Inf; {Забираем информацию из удаляемого звена} Dispose(Vsp); {Уничтожаем звено} End;

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

Определение:

 

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

 

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

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

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

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



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

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

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

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

3. Получение значения текущего элемента

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

5. Удаление узла из дерева

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

 

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

1. Структура для создания корня и узлов дерева имеет вид:

2. type3. T = Integer; { скрываем зависимость от конкретного типа данных }4. 5. TTree = ^TNode;6. TNode = record7. value: T;8. Left, Right: TTree; end;

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

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

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



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

o если удаляемый узел имеет только одного "сына", то его значение можно заменить значением этого "сына"

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

 

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

function DeleteMin(var Root: TTree): T;var WasRoot: TTree;begin if Root^.Left = nil then begin DeleteMin := Root^.value; { Результат функции } WasRoot := Root; { Запоминаем узел для последующего удаления } Root := Root^.Right; { продвигаемся дальше } Dispose(WasRoot); { удаляем бывший корень } end else { узел Root имеет левого "сына" } DeleteMin := DeleteMin(Root^.Left); end;

Теперь процедура Remove может быть реализована так:

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

11. Procedure Delete(T: TTree);12. Begin13. If T = nil Then Exit;14. 15. Delete(T^.Right);16. Delete(T^.Left);17. Dispose(T) End;


Обход дерева

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

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

 

Таблица рекурсивных алгоритмов прохождения бинарного дерева-------------------------------------------------------------------------------- Порядок прохождения-------------------------------------------------------------------------------- Прямой | Симметричный | Концевой--------------------------------------------------------------------------------1. Корень поддерева |1. Левое поддерево |1. Левое поддерево2. Левое поддерево |2. Корень поддерева |2. Правое поддерево3. Правое поддерево |3. Правое поддерево |3. Корень поддерева--------------------------------------------------------------------------------

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

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

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

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





©2015- 2017 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов.