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

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

4.2. Реализация алгоритмов работы с бинарными деревьями 49
}
//главная программа
int main()
{
tree<char> t; // задаем дерево с элементами типа char
cout<<endl;
t.in(t.root);
t.btree1(t.root);
t.btree2(t.root);
t.btree3(t.root);
}
Нерекурсивная реализация обхода бинарного дерева
по уровням с помощью FIFO-очереди
Теперь рассмотрим новый обход бинарного дерева, который назы-
вают обходом в ширину. Этот метод использует FIFO-очередь и осу-
ществляет обход дерева по уровням слева направо, в отличие от сте-
кового обхода в глубину, когда алгоритм пытается пройти как можно
дальше вглубь, пока не дойдет до конца какой-либо ветки. В этой про-
грамме приведена параметризованная реализация последовательной
циклической FIFO-очереди и снова описан параметризованный класс
”бинарное дерево”. Другой вариант программы мог бы включать в
одну программу реализацию и стека, и очереди, и описание одного
класса ”бинарное дерево”.
Этот принцип применения стека для обхода в глубину и очере-
ди для обхода в ширину сохраняется и при обходе других структур
данных, например графов. Отметим, что в функции ввода бинарного
дерева для обозначения нулевых связей используется символ точка ”.”.
Это накладывает ограничение на тип информационного узла дерева.
Если необходимо работать не только с типом char, то надо вводить
нулевые связи каким-то другим способом. Такая модификация про-
граммы оставлена читателю в качестве упражнения.
#include <iostream.h>
template<class telem> class queue{
telem *x;
int head;
4.2.    Реализация алгоритмов работы с бинарными деревьями       49


 }

//главная программа
int main()
 {
   tree t; // задаем дерево с элементами типа char
   cout<

template class queue{
    telem *x;
    int head;

Страницы