ВУЗ:
Составители:
63
нем любые две вершины соединены единст-
венным путем. Деревья могут ориентиро-
ванными и неориентированными. На рис.
2.30 приведен пример неориентированного
дерева.
Двоичное дерево – это такое ориенти-
рованное дерево, для которого справедливо
следующее:
• имеется ровно одна вершина, в ко-
торую не входит ни одного ребра; эта вершина называется
корнем двоичного дерева
;
• в каждую вершину дерева, кроме корня, входит одно ребро;
• из каждой вершины, включая корень, исходит не более двух
ребер.
Примеры двоичных деревьев
приведены на рис. 2.31. Для ребер,
выходящих из любой вершины, име-
ется две возможности – быть на-
правленными влево вниз или вправо
вниз. Направление является сущест-
венным, если мы не хотим указывать направление на дугах графа.
Приведенные на рис. 2.31 два графа – различны.
При решении многих прикладных задач бывает удобно пред-
ставлять наборы объектов в виде двоичных деревьев. Рассмотрим,
для примера, задачу кодирования последовательности целых чисел.
Пусть имеется последовательность целых чисел а
1
,а
2
,…,а
n
и функция
целочисленного аргумента F(x), принимающая целые значения. Зна-
чение F(x) будем называть кодом числа x. Пусть требуется закодиро-
вать данные числа, т.е. вычислить значения F(a
1
),F(a
2
),…,F(a
n
), и
Рис. 2.31
а
а
b
c
b
c
d
e
f
d
e
f
Рис. 2.30
Страницы
- « первая
- ‹ предыдущая
- …
- 65
- 66
- 67
- 68
- 69
- …
- следующая ›
- последняя »
