Binary_tree graph;. void Inorder(unsigned node, binary_tree graph, unsigned number[], unsigned *counter);

void Inorder(unsigned node, binary_tree graph, unsigned number[], unsigned *counter);

unsigned number[STACK_SIZE], counter=1, index;

void main ()

{

// В этом месте должна стоять функция ввода бинарного дерева в виде структуры,

// состоящей из двух массивов leftson и rightson

// Прохождение дерева во внутреннем порядке

Inorder(ROOT, graph, number, &counter);

} //Конец main

void Inorder(unsigned node, binary_tree graph, unsigned number[], unsigned *counter)

// Рекурсивная процедура прохождения бинарного дерева во внутреннем порядке

{

unsigned vertex, count;

count=*counter;

if (graph.leftson[node]!= 0)

{

vertex=graph.leftson[node];

Inorder(vertex, graph, number, &count);

}

number[node]=count++;

if (graph.rightson[node]!= 0)

{

vertex=graph.rightson[node];

Inorder(vertex, graph, number, &count);

}

*counter=count;

} //Конец Inorder

Сама главная программа предельно проста. В функции Inorder переменная count вводится для обеспечения возможности изменять значение глобальной переменной counter на выходе функции Inorder.

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

1.7. Разделяй и властвуй

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

Рассмотрим задачу нахождения наибольшего и наименьшего элементов множества S, содержащего n элементов. Для простоты будем считать, что n есть степень числа 2. Очевидный путь поиска наибольшего и наименьшего элементов состоит в том, чтобы искать их по отдельности. Например, следующая функция находит наибольший и наименьший элементы множества S, заданного массивом array, произведя 2×n-2 сравнений его элементов. Не ограничивая общности, массив выбрали типа int. Однако если требуется другой тип массива, то необходимо будет изменить тип у самой функции Max_Min_Element, у массива array и у указателя *ptr на соответствующий.

// Программа 4.1 поиска наибольшего и наименьшего элементов массива

void Max_Min_Element(int array[], unsigned Size, unsigned max, unsigned min)

// Функция находит максимальный и минимальный элементы массива array размера Size

{

unsigned index;

int *ptr;

ptr=&array[0];

min=max=*ptr++;

index=1;

while (index++<Size)

{

if (max<*ptr) max=*ptr;

if (min>*ptr) min =*ptr;

*ptr++

}

} // Конец Max_Min_Eletment

Итак, понятно, что для нахождения минимального и максимального элементов множества S требуется 2×n-2 сравнений при n³ 2. (Вообще-то достаточно на одно сравнение меньше, если реализовать поиск данных элементов последовательно и после нахождения максимального не учитывать его при поиске минимального, т.е. 2×n-3 сравнений).

Применяя приём «разделяй и властвуй» (divide and conquer), пришлось разбить бы множество S на два подмножества S ₁ и S ₂ по n/2 элементов в каждом. Тогда описанный выше алгоритм нашёл бы наибольший и наименьший элементы в каждом из двух половин с помощью рекурсии. Наибольший и наименьший элементы всего множества S можно было бы определить, произведя ещё два сравнения - наибольших элементов в S ₁ и S ₂ и наименьших элементов в них. Сформулируем данный алгоритм более точно.