1611678431-0e68e83522cb9d960ac896aa5d90854d (Билеты - Ответы), страница 22

Обходы бинарных деревьев в ширину и в глубину, префиксный, инфиксный ипостфиксные обходы бинарных деревьевЛекции: фото 35, 36Обход корневого дерева (или ордерева) T состоит в посещении вершин этого дерева внекотором порядке. Например, при его обходе в ширину вершины T посещаются по уровням, начинаяс корня, и слева направо (от старших потомков к младшим). Рассмотрим три разных обходаупорядоченного дерева T (с корнем v и его сыновьями v1,…,vn) в глубину: префиксный, постфиксный иинфиксный обходы.Префиксный обход (прямой обход или П-обход) выполняется по следующим правилам:1) посетить корень v;2) выполнитьпоследовательности.префиксныйобходподдеревьевскорнямиv1,…,vnвуказаннойПостфиксный обход (обратный обход или О-обход) описывается следующим образом:1) выполнитьпоследовательности;постфиксныйобходподдеревьевскорнямиv1,…,vnвуказанной2) посетить корень v.Инфиксный обход (обход во внутреннем порядке или В-обход) определяется так:1) выполнить инфиксный обход поддерева с корнем v1;2) посетить корень дерева T;3) выполнитьпоследовательности.инфиксныйобходподдеревьевскорнямиv2,…,vnвуказаннойВозможны два способа прохождения бинарного дерева (если дерево не пусто):а) в глубину:-прямой (префиксный) порядок: корень, левое поддерево в прямом порядке, правое поддерево впрямом порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: ABDCEGFHJ );Алгоритм прямого обхода:{ S = NULL;while ( d != NULL){ обработка ( d );if ( d->left != NULL && d->right != NULL){встек (S, d->right); d = d->left;}else if ( d->left = = NULL && d->right = =NULL)if ( S!= NULL) изстека (S, d); else d = NULL;else if (d->left != NULL) d = d->left;else d = d->right;}}Рекурсивное описание алгоритма прямого обхода:пр_обход ( btree *d){ if ( d != NULL ) { обработка ( d ); пр_обход ( d->left );пр_обход ( d->right ); }}-обратный (инфиксный) порядок: левое поддерево в обратном порядке, корень, правое поддерево вобратном порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: DBAEGCHFJ);Алгоритм обратного обхода:{ S = NULL; F = 1;while ( F ){ while ( d != NULL ){ встек ( S, d ); d = d->left; }if ( S != NULL ) { изстека ( S, d );обработка ( d ); d = d-right;}else F = 0;}}Рекурсивное описание алгоритма обратного обхода:обр_обход ( btree *d ){ if ( d != NULL ) { обр_обход ( d->left ); обработка ( d );обр_обход ( d->right ); }}-концевой (постфиксный) порядок: левое поддерево в концевом порядке, правое поддерево вконцевом порядке, корень (линейная расстановка узлов дерева, представленного на рис.4.1.б:DBGEHJFCA);Алгоритм концевого обхода:{ S = NULL;dowhile ( d != NULL ){ встек ( S, d, 0 ); d = d->left; }if ( S != NULL ){ doизстека ( S, d, F ); if ( F ) обработка ( d );while ( F && S != NULL );if ( ! F ) { встек ( S, d, 1 ); d = d->right; }while ( S != NULL );}Рекурсивное описание алгоритма концевого обхода:конц_обход ( btree *d ){ if ( d != NULL ) { конц_обход ( d->left ); конц_обход ( d->right );обработка ( d ); }}б) в ширину: узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейнаярасстановка узлов дерева, представленного на рис.4.1.б: ABCDEFGHJ).Алгоритм обхода в ширину:{ Q = NULL;if ( d != NULL ) { в_очередь ( Q, d );doиз_очереди ( Q, d ); обработка ( d );if ( d->left != NULL ) в_очередь ( Q, d->left );if ( d->right != NULL ) в_очередь ( Q, d->right );while ( ! пуста_очередь ( Q ) );}}Задаём стек 1, стек 2; в стеке 1 – 1-ый элемент = v0 (root);пока оба стека не пустыпока стек 1 не пуст{{a.

Добавляем в стек 2 все вершины, смежные вершинам стека 1;b. Удаляем вершины из стека 1;c. Стек 1 = стек 2; стек 2 = стек 1.}}42. Корневые и упорядоченные деревья, способы их реализацииЛекции: фото 35, 36Деревом называется связный граф без циклов (у него p вершин и p-1 ребро).Корневое дерево - это дерево с выделенной вершиной, называемой корнем.

Все вершиныкорневого дерева распадаются на уровни по величине их расстояния от корня, так, что все ребрасоединяют вершины соседних уровней. Рассматривая каждое ребро <u,v> корневого дерева как дугу(u,v) от вершины меньшего уровня к вершине большего уровня, получаем понятие ориентированногодерева (или ордерева). Это - связный орграф без циклов, удовлетворяющий следующим условиям:а) имеется ровно одна вершина, называемая корнем, к которой не ведет ни одна дуга;б) к каждой вершине, отличной от корня, ведет ровно одна дуга; говорят, что она соединяетотца с сыном.В упорядоченном ордереве на множестве всех вершин, достижимых из данной (ее потомков),задано линейное упорядочение, при котором все потомки одного сына предшествуют всем потомкамлюбого более младшего.

(Существует два основных типа деревьев. В рекурсивном дереве илинеупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомковдля каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку,присвоены различные натуральные числа) называется деревом с именованными рёбрами илиупорядоченным деревом со структурой данных, заданной перед именованием и называемойструктурой данных упорядоченного дерева.)43. Поисковые деревья, операции вставки, использование поисковых деревьев в задачахсортировкиЛекции: фото 36Поисковое дерево – дерево, у которого все числа в левом поддереве меньше корня, а вправом больше.Деревом (двоичного) поиска для множества чисел S называется размеченное двоичноедерево, в котором каждая вершина v помечена числом (v) ∈ Sи которое удовлетворяет следующимусловиям: lа) ( ) < (v) для всех вершин u, v, если вершина u находится в поддереве, корень которого левый преемник v;б) ( ) > (v) для всех вершин u, v, если вершина u находится в поддереве, корень которого правый преемник v;в) для всякого числа a существует единственная вершина v, для которой (v) = a.Дерево двоичного поиска для целых чисел44, 45.

Графы и орграфы, их реализация с использованием матриц смежности иинцидентности(45) Представление орграфов с использованием списков смежных вершинЛекции: фото 37, 38, 39Граф – это пара (V, E), где V – конечное множество вершин, E – конечное множество рёбер, E2⊆V .Граф – это совокупность двух конечных множеств: множества точек и множества линий,попарно соединяющих некоторые из этих точек. Множество точек называется вершинами (узлами)графа. Множество линий, соединяющих вершины графа, называются ребрами (дугами) графа.Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрамкоторого присвоено направление.Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е.ребрам которого не задано направление.Смешанный граф – граф, содержащий как ориентированные, так и неориентированныеребра.Петлей называется ребро, соединяющее вершину саму с собой.

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

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

Рассмотрим несколько способов представленияграфа.Пусть задан граф (например, рис. 44.1), у которого количество вершин равно n, а количестворебер – m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф неявляется помеченным, то считается, что вес равен единице.Рис. 44.1. Граф1. Список ребер – это множество, образованное парами смежных вершин. Для его храненияобычно используют одномерный массив размером m, содержащий список пар вершин,смежных с одним ребром графа. Список ребер более удобен для реализации различныхалгоритмов на графах по сравнению с другими способами.2. Список смежностиV1 вершины, смежные с v1...vn вершины, смежные с vn3. Матрица смежности – это двумерный массив размерности n x n, значения элементовкоторого характеризуются смежностью вершин графа. При этом значению элементаматрицы присваивается количество ребер, которые соединяют соответствующие вершины.Данный способ действенен, когда надо проверять смежность или находить вес ребра подвум заданным вершинам.[ , ] =1, смежна0иначе4.

Матрица инцидентности – это двумерный массив размерности n x m, в которомуказываются связи между инцидентными элементами графа (ребро и вершина). Столбцыматрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейкематрицы указывает связь между вершиной и ребром. Данный способ является не самымемким для хранения, но облегчает нахождение циклов в графе.Неориентированный граф:[ , ] =1, инцидентна0иначеОриентированный граф:−1, если[ , ]==,,∈1, если = , , ∈0иначе.