Дерево левое корень правое

3.7. Обходы бинарных деревьев и леса

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

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

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

Рекурсивное прохождение бинарного дерева.

Postorder(постфиксный)

3. Пройти правое поддерево

3. Пройти правое поддерево

2. Пройти правое поддерево

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

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

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

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

Очередность обработки узлов

Источник

11. Обходы бинарных деревьев (клп — «Корень-Левое-Правое» ,лкп,лпк) с примерами программной реализации.

Обход приведённого бинарного дерева в прямом порядке даст: ABCDEFGH.

2. Обход бинарного дерева в обратном порядке:

a) Обойти левое поддерево корня в обратном порядке;

c) Обойти правое поддерево корня в обратном порядке.

Обход приведённого бинарного дерева в обратном порядке даст: CBEDAGFH.

3. Обход в бинарного дерева в концевом порядке:

а) Обойти левое поддерево корня в концевом порядке;

b) Обойти правое поддерево корня в концевом порядке.

Обход приведённого бинарного дерева в концевом порядке даст: CEDBGHFA.

Следует обратить внимание на то, что при обходе бинарного дерева в прямом порядке, любая его вершина , рассматриваемая как корень, посещается перед обходом поддеревьев этого корня, а при концевом порядке – после.

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

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

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

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

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

В приведённой выше записи, знаком ‘*’ обозначены пустые поддеревья, и для лучшей читабельности, добавлены лишние пробелы.

12. Удаление элемента из бинарного дерева поиска.

Удаление элемента из множества.

Удаление – несколько более сложная процедура, чем вставка. Пусть нам надо удалить элемент x. Найдём узел r, который его содержит. Если такого узла найти не удалось, то и делать ничего не надо.

Если у узла r нет сыновей, то всё хорошо: уничтожаем узел и пишем NIL в указатель, который на него ссылался.

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

Наконец, что делать, если у удаляемого узла r два сына? В этом случае нам надо найти в его правом поддереве узел с самым маленьким элементом. Это несложно: берём правого сына и идём от него влево, пока не найдём узел q, у которого левого сына нет. Он и будет искомым. Теперь значение из q запишем в узел r, а удалять будем уже не r, а q. Как это делается, см. выше.

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

procedure del(var root: PNode; x: Integer);

procedure del_rec(var r: PNode);

if r=NIL then exit;

if x>r^.v then begin del_rec(r^.right); exit; end;

if (r^.left=NIL) or (r^.right=NIL) then

if r^.left=NIL then r:=r^.right else r:=r^.left;

if p^.left=nil then

//идём влево, пока есть куда

while q^.left<>NIL do begin

//значение из q^ кинем в r^, и удалять будем уже не r^, а q^

Источник

3 8(5) .Понятие обхода дерева. Виды обходов двоичного дерева. Определение структуры двоичного дерева по двум заданным обходам. Рекурсивные алгоритмы обходов двоичных деревьев.

Остальные узлы (исключая корень) содержатся в m≥0 попарно не пересекающихся множествах T1, T2, … , Tm, каждое из которых в свою очередь является деревом. Деревья T1, T2, … , Tm называются поддеревьями данного корня.

Если корень дерева имеет не более двух поддеревьев (как и корни поддеревьев), то такое дерево называют бинарным. Будем считать, что пустое множество узлов также является бинарным деревом. В бинарном дереве поддеревья считаются упорядоченными: различают правое и левое поддеревья корня.

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

Для бинарного дерева существует 6 возможных вариантов обходов. Запишем на псевдокоде рекурсивные процедуры для каждого из них:

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

Суть алгоритма сводится к следующему:

Определить корень дерева (по обходам вида КПЛ, КЛП, ПЛК или ЛПК)

Определить последовательности, относящиеся к правому и левому поддеревьям (если они не пустые) (по обходам вида ПКЛ или ЛКП).

Для каждого из поддеревьев повторить описанную процедуру.

1 16(1) . Цикломатика графов. Цикломатическое число. Цикломатический базис. Связь циклов графа с цикломатическим базисом.

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

Цепью в графе называют маршрут, все рёбра которого различны.

Циклом в графе называют замкнутую цепь (то есть цепь, у которой начальная и концевая вершины совпадают). Для орграфов цикл называется контуром. Эйлеров цикл – цикл графа, в котором каждое ребро графа участвует в его образовании ровно один раз. Гамильтонов цикл – цикл графа, в котором каждая верш. графа участвует в его образ-ии ровно один раз.

Пусть — некоторый граф ( – множество вершин, – множество рёбер). Произвольный цикл графа можно представить в виде бинарного вектора размерности q:

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

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

где , , — число компонент связности графа.

Остов графа – максимальный по включению рёбер ациклический частичный граф исходного графа. Хордами называют рёбра графа, не входящие в остов.

Алгоритм нахождения базисной системы циклов.

1)Получить остов графа (удалить из графа рёбер (хорд)).

2)Добавляя поочерёдно к остову по одной хорде ( раз) получаем базис. систему циклов.

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

Источник