12.1 Основные понятия и определения

Деревья являются удобным способом представления информации. Поэтому в программировании они играют огромную роль. Вместе с тем можно выделить два наиболее важных направления:

1. использование деревьев для представления информации, например древовидная структура каталогов, древовидная структура некоторой фирмы (директор-подразделения-отделы-работники ), иерархические классификации и т.д.
2. использование деревьев для организации эффективного поиска информации (двоичные деревья, АВЛ-деревья, B-деревья и т.д.)

Дадим ряд определений.

Деревом будем называть ациклический ориентированный граф G, обладающий следующими свойствами:

1. имеется узел r, у которого нет входных дуг, назовем его корнем дерева;
2. все узлы, кроме корня, имеют одну входную дугу и несколько выходных дуг (выходные дуги могут отсутствовать).

Узел, у которого нет выходных дуг, назовем листом.
Сыном узла z будем называть узел w, который имеет входную дугу выходящую из z.
Потомком узла z будем считать узел w, к которому есть путь от z по выходным дугам.
Предком узла w будем называть узел z, от которого имеется путь по выходным дугам.
Поддеревом дерева G будем называть дерево, получаемое из G путем отсечения некоторого подмножества входных дуг.

а)Дерево	б)Древовидный список
рис.11.1	рис.11.2

На рис.11.1 узел под номером 1 - корень дерева, узлы 4,5, 6 - листья, узлы 4,5 для узла 2 являются сыновьями, узел 1 для узла 6 является предком, а узлы 4,5, 6 являются потомками для узла 1.