Структуры данных. Деревья - 4 стр.

UptoLike

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

Рубрика:

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Деревья, в частности бинарные деревья, представляют собой одну из базо-

вых структур данных в программировании. Они используются в компиляторах,

системах управления базами данных, файловых системах. Для многих приклад-

ных задач использование древовидной структуры представления информации

позволяет существенно повысить временные характеристики алгоритмов обра-

ботки.

Деревья имеют

ярко выраженную рекурсивную структуру. Рекурсивные

алгоритмы при работе с деревьями получаются более компактными, элегантны-

ми, они легче для понимания, чем итеративные алгоритмы.

Деревья часто встречаются в повседневной жизни и хорошо известны по

генеалогическим деревьям (рисунки 1 и 2) и структурам с иерархической органи-

зацией.

Определим дерево как непустое множество T элементов – узлов ( или

вершин ) таких, что

а) имеется единственный особый узел, называемый корнем данного

дерева;

б) остальные узлы содержатся в m >= 0 попарно не пересекающихся мно-

жествах T

, ... , T

, каждое из которых в свою очередь является деревом.