Язык С++ и программирование на нем. Рейзлин В.И. - 151 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

153
case ‘)’ : case ‘]’ : case ‘}’ :
if ( s.empty () || !accord (s, sym)) b = 0; break;
}
}
if (!b || !s.empty ()) cout <<”\nБаланса скобок нет!\n”;
else cout <<”\nСкобки сбалансированы\n”;}
26. Двоичные деревья
26.1. Определение и построение
Связанный граф, в котором нет циклов, называется деревом. Де-
рево называется ориентированным, если на каждом его ребре указано
направление.
Двоичное дерево – это такое ориентированное дерево, в котором:
1) Имеется ровно одна вершина, в которую не входит ни одного
ребра. Эта вершина называется корнем двоичного дерева.
2) В каждую вершину, кроме корня, входит одно ребро.
3) Из каждой вершины исходит не более двух ребер.
Будем изображать двоичные деревья так, чтобы корень распола-
гался выше других вершин.
Для ребер, выходящих из любой вершины, имеется две возможно-
сти – быть направленными влево вниз и вправо вниз. При этом, если из
вершины выходит одно ребро, то указание направления ребра влево
вниз или вправо вниз является существенным. При таких соглашениях
нет необходимости указывать направление на ребрах – все ребра ориен-
тированы вниз.
При решении некоторых задач бывает удобно представить наборы
объектов в виде двоичных деревьев.
Рассмотрим задачу кодирования непустой последовательности
целых чисел.
Пусть дана последовательность целых чисел а
1
, … , а
n
и функция
целочисленного аргумента F(x), принимающая целые значения. Значе-
ние F(x) будем называть кодом числа x. Пусть требуется закодировать
данные числа, т.е. вычислить значения F(a
1
), ... , F(a
n
), и пусть в после-
довательности a
1
, ... ,
a
n
имеются частые повторения значений элемен-
тов.
Чтобы избежать повторных вычислений одного и того же значе-
ния, следует по ходу кодирования строить таблицу уже найденных ко-

Страницы