- Дерево — это граф, в котором нет циклов, т. е. в нём нельзя из некоторой вершины пройти по нескольким различным рёбрам и вернуться в ту же вершину.
- Дерево, как и любой граф, состоит из вершин (узлов) и соединяющих их рёбер.
- Основные термины:
- корень (самый верхний узел дерева);
- потомок (узел, имеющий родительский узел);
- родитель (узел, имеющий ребро, соединяющее его с узлом-потомком);
- листья (последние узлы на дереве, узлы без потомков);
- высота (длина самого дальнего пути к листу);
- глубина (длина самого дальнего пути от корня к листу).
- Деревья используются для организации поиска в базах данных, выполнении арифметических выражений, алгоритмах принятия решений. С помощью дерева можно перебирать варианты в логической игре.
![](https://cdn.oblakoz.ru/IMUMKContent/687439/content/493242/497242.png)