Прежде чем приступать к решению задачи, необходимо ознакомиться с предметной областью.
Деревом называется одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Прежде всего, дерево является связанным графом, не содержащим циклы.
У любого дерева есть корень. Это узел, расположенный в самом верху дерева (см. Рисунок 1). У дерева может быть только один корень.
К любому узлу дерева можно дойти из корня. Кроме того, существует только один путь связывающий корень и узел. Следует обратить внимание на то, что любой узел дерева сам по себе является деревом и именуется поддеревом.
Расстояние от корня до узла называется уровнем. Корень расположен на нулевом уровне.
Глубина дерева – это максимальный уровень любого его узла. Или глубина дерева – это длина самого длинного пути от корня до узла.
Если между узлами b и a есть дуга, и узел a расположен на более высоком уровне, то a называется – родителем (предком), а b - потомком. Каждый узел дерева является корнем поддерева, которое состоит из данного узла и всех его потомков. У узла дерева может быть любое количество потомков.
Самые нижние узлы дерева называют листьями, и они не имеют потомков.
Рисунок 1 - Дерево
