Лекция: 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.

еще рефераты
Еще работы по информатике