Деревья

Для начала введем основную терминологию:

• узел (node) - фундаментальная часть дерева. Может иметь имя, которое называют ключом. Узел может также хранить дополнительную информацию (полезная нагрузка);
• ребро (edge) - еще одна фундаментальная часть дерева. Ребро соединяет два узла, чтобы показать, что между ними есть связь (отношение). Узел имеет ровно одно входящее ребро и переменное число исходящих ребер;
• корень (root) - корень дерева это узел, но у которого нет входящих ребер;
• путь (path) - путь это упорядоченный список узлов, которые соединены ребрами;
• потомок (child) - набор узлов, которые имеют входящие ребра от одного и того же узла, называют потомками этого узла;
• родитель (parent) - узел является родителем всех узлов, соединённых с ним по исходящим ребрам;
• поддерево (subtree) - набор узлов и ребер, состоящих из родителя и всех потомков этого родителя;
• лист - узел, не имеющий потомков;
• глубина узла - уровень узла n это число ребер, входящих в путь от корня до узла n;
• высота дерева - совпадает с высотой корня.

Определение 1: Дерево состоит из множества узлов и множества ребер, которые соединяют пары узлов. Дерево имеет следующие свойства:

• один из узлов дерева обозначается как корень дерева;
• каждый узел n, кроме корня, соединён ребром ровно с одним узлом p, где p родитель n;
• существует единственный путь от корня до каждого узла;
• если каждый узел в дереве имеет не более двух потомков, то такое дерево называют бинарным.

Определение 2 (рекурсивное): Дерево является или пустым или состоящим из корня и нуля или более поддеревьев, каждое из которых также является деревом.

Определение 3: Дерево это связный граф, который не содержит циклов.