Деревья — это структура данных, которая используется для описания иерархии. Можно дать и другие определения, например: дерево — связный граф (граф, в котором из любой вершины существует путь к любой другой вершине) без циклов. Дерево — это граф, в котором существует единственный путь между любыми двумя вершинами.
Примеры графов представлены ниже.
Дерево состоит из узлов (вершин) и дуг (связей между узлами).
Первая вершина дерева, из которой выходят дуги, называется корнем дерева. Корень дерева расположен на верхнем уровне.
Узел, который находится на более высоком уровне, называется родителем, а на более низком — сыном. У корня дерева нет родителей, а у листьев дерева — сыновей.
Предками некоторого узла называются все узлы на пути от корня дерева до данного узла, включая корень и исключая сам узел.
Потомком некоторого узла b называется любой узел дерева, который является сыном или потомком данного узла b.
Вершины дерева, которые не имеют потомков, называются листьями.
Высотой дерева называется наибольшая длина пути от корня к листу.
Поддерево — это подграф (часть графа, содержащая некоторые узлы и дуги) дерева.
Рассмотрим пример:
Обозначим узлы дерева, используя определения, приведенные выше.
Корень дерева: b.
Сыновья b: a, d, c.
Родитель a, d, c: b.
Потомки с: e.
Листья: a, d, e.
Предки e: c, b.
