Алгоритмы и структуры данных на С++. Аксёнова Е.А - 46 стр.

46                             Глава 4. Нелинейные структуры данных


           btree1 (t->rlink); // обход правого поддерева
      }
}

          Рекурсивная реализация ввода бинарного дерева
                        в прямом порядке
      Дерево вводится в виде ab..c.., где вместо NULL-связей вводим точ-
ки.

void input(node *&t)
{
   char c;
   cin>>c;
   if(c!=’.’)
     {
       t = new node;
       t->info = c;
       input(t->llink);
       input(t->rlink);
     }
   else t=NULL;
}

          Нерекурсивный алгоритм обхода бинарного дерева
                       в обратном порядке
   Пусть есть рабочий указатель node *p и стек указателей на узлы
дерева, t – указатель на корень дерева.

      Алгоритм:
     1) p = t;
     2) пройти до конца самой левой ветки дерева, начинающейся в p,
        запоминая ссылки на узлы в стеке;
     3) если стек непуст, то вытолкнуть из него верхний указатель в p,
        вывести информацию, которая хранится в p, p = p -> rlink,
        и перейти на шаг 2.
   Далее приведена реализация некоторых алгоритмов работы с би-
нарными деревьями с использованием шаблонов.