Алгоритмы прохождения бинарных деревьев.

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

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

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

Алгоритмы поиска в упорядоченном и неупорядоченном целочисленном векторе. Возвращаемые значения при успешном и не успешном поиске. Сравнительный анализ алгоритмов поиска: линейный, двоичный.

std::vector< std::string > v_str; //Пустой вектор v_str

v_str.push_back("zz"); // {"zz"}

 v_str.push_back("aa"); // {"zz", "aa"}

std::sort(v_str.begin(), v_str.end()); //Сортировка всех элементов вектора

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

-Алгоритм последовательного поиска

Шаг 1. Полагаем, что значение переменной цикла i=0. Шаг 2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1.

Шаг 3. Если i<k, где k – число элементов массива x, то выполняется Шаг 2, в противном случае – работа алгоритма завершена и возвращается значение равное -1.

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

-Алгоритм бинарного поиска:

Шаг 1. Определить номер среднего элемента массива middle=(high+low)/2.

Шаг 2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритмзавершает работу.

Шаг 3. Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности). Перейдем к Шагу 1.

int BinarySearch(int *x, int k, int key){ bool found = false; int high = k - 1, low = 0; int middle = (high + low) / 2; while ( !found && high >= low ){

if (key == x[middle])      found = true; else if (key < x[middle]) high = middle - 1; else  low = middle + 1;

 middle = (high + low) / 2; } return found ? middle : -1 ;}

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

Простые алгоритмы сортировки целочисленного вектора.

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

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

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

· линейный выбором элемента;

· метод минимального (максимального) элемента;

· метод сортировки обменами ("пузырьковая" сортировка);

· челночная сортировка;

· метод сортировки вставками;

Алгоритм линейного выбора элемента

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

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

Алгоритм метода минимального (максимального) элемента.

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

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