Лекция: Binary_tree graph;
unsigned number[STACK_SIZE], counter=1, node=ROOT, index;
void main()
{
// Опустошение стека
vertex.top=0;
// В этом месте должна стоять функция ввода бинарного дерева в виде структуры,
// состоящей из двух массивов leftson и rightson
// Процедура прохождения дерева
Left: while (graph.leftson[node] != 0)
{
vertex.name[++vertex.top]=node; // Заталкивание узла в стек
node=graph.leftson[node];
}
Center: number[node]=counter++;
if (graph.rightson[node] != 0)
{
node=graph.rightson[node];
goto Left;
}
if (vertex.top != 0)
{
node=vertex.name[vertex.top--]; // Выталкивание узла из стека
goto Center;
}
} // Конец main
Корректность работы этого алгоритма была проверена на практике, но её можно доказать и теоретически по индукции. Следует обратить внимание на то, что использование языка C позволяет здесь обойтись без создания специальных функций (подпрограмм, процедур) Pull и Pop для вталкивания и выталкивания узла из стека.
Недостаток данного алгоритма заключается в том, что он в двух местах использует оператор goto, что считается “дурным тоном” у современных программистов. Действительно, использование данного оператора затрудняет понимание алгоритма, так как зачастую тяжело уследить за причинами, приведшими к переходу программы на указанную метку. Поэтому современные программисты стараются избегать использования оператора goto. Однако goto часто применяют, когда непредвиденное состояние или ошибка могут возникнуть внутри многократно вложенных циклов. В этой ситуации goto может значительно упростить программу. Похожая ситуация имеет место и в запрограммированном алгоритме, где обойтись без оператора goto достаточно сложно.
При создании алгоритма, который присваивает узлам номера в соответствии с внутренним порядком, постоянно приходится сталкиваться с ситуациями, когда используемая процедура должна повториться с самого начала. Хорошо было бы описать подобную процедуру специальной функцией и обращаться к ней по мере надобности при прохождении бинарного дерева во внутреннем порядке. Здесь на помощь приходит рекурсия, которая позволяет сделать программу прохождения дерева более наглядной и простой, однако коэффициент c в выражении для порядка временной сложности O(c×na) у этой программы может быть выше, чем у программы 1.