На этом шаге мы рассмотрим нерекурсивные алгоритм изображения бинарного дерева.
Пусть бинарное дерево построено с помощью описанного на предыдущем шаге нерекурсивного алгоритма и определено указателем t.
Нам понадобятся два стека, которые мы реализуем на базе однонаправленных списков. Тип звеньев стека опишем так:
struct no
{
no *sled; // Указатель на вершину.
node *elem; // Информационное поле.
int ch; // Уровень вершины.
}
Изобразим схематично звено стека:
Рис.1. Звено стека
Опишем используемые переменные:
no *stk; // Стек "левых" ссылок.
no *stk1; // Стек "правых" ссылок.
node *u; // Указатель на структуру.
Теперь приведем и сам алгоритм:
stk = stk1 = NULL; // Первоначально оба стека пусты.
n = 0;
while (t!=NULL)
{
PushStack (&stk1,&t,&n);
// Пока не достигнут лист дерева, в стек stk помещаются
// левые ссылки тех структур, по которым перемещается
// указатель t.
if ((*t).Right!=NULL)
{ if ((*t).Left!=NULL) PushStack (&stk,&(*t).Left,&n); t = (*t).Right;}
else {
// Как только будет достигнут самый правый лист, проверяем левую
//ссылку. Если она существует, то из стека правых ссылок удаляем
//последний адрес, и на печать выводим поле ключа этой вершины.
if ((*t).Left!=NULL)
{ if (stk1!=NULL)
{ PopStack (&stk1,&u,&n);
for (i=0; i<=n; i++) cout<<" ";
cout<<(*u).Key<<endl; }
t = (*t).Left; }
if (stk==NULL) t = NULL;
else {
// Если у вершины дерева указатели на правое и
// левое поддеревья равны NULL, а стек левых
// указателей не пуст, то...
while ((*stk).elem!=(*((*stk1).elem)).Left)
{ // Удаляется адрес из стека правых ссылок
//и на печать выводится значение поля ключа
//вершины с данным адресом
PopStack (&stk1,&u,&n);
for (i=0; i<=n; i++) cout<<" ";
cout<<(*u).Key<<endl; }
// Как только выполнится условие
//((*stk).elem==(*((*stk1).elem)).Left), удаля-
//ются адреса из обоих стеков, а поле ключа
//также выводится на экран дисплея.
PopStack (&stk1,&u,&n);
for (i=0; i<=n; i++) cout<<" ";
cout<<(*u).Key<<endl;
PopStack (&stk,&t,&n); }
}
n = n + 1;
}
VyvodStack (&stk1);
Оформим алгоритм в виде функции на языке C++:
void VyvodTree (node *t) // Изображение дерева, заданного указателем t, // на экране дисплея (нерекурсивный алгоритм). { no *stk, *stk1; node *u; int i,n; stk = stk1 = NULL; n = 0; while (t!=NULL) { PushStack (&stk1,&t,&n); if ((*t).Right!=NULL) { if ((*t).Left!=NULL) PushStack (&stk,&((*t).Left),&n); t = (*t).Right; } else { if ((*t).Left!=NULL) { if (stk1!=NULL) { PopStack (&stk1,&u,&n); for (i=0; i<=n; i++) cout<<" "; cout<<(*u).Key<<endl; } t = (*t).Left; } else if (stk==NULL) t = NULL; else { while ((*stk).elem!=(*((*stk1).elem)).Left) { PopStack (&stk1,&u,&n); for (i=0; i<=n; i++) cout<<" "; cout<<(*u).Key<<endl; } PopStack (&stk1,&u,&n); for (i=0; i<=n; i++) cout<<" "; cout<< (*u).Key<endl; PopStack (&stk,&t,&n); } } n = n + 1; } VyvodStack (&stk1); }
На следующем шаге мы приведем пример построения и изображения бинарного дерева с помощью нерекурсивных алгоритмов.
