ОПРЕДЕЛЕНИЕ. Неориентированный связный граф, не имеющий петель, называется деревом, если он не содержит циклических ребер

Неориентированный связный граф, не имеющий петель, называется деревом, если он не содержит циклических ребер.

Если граф D - это дерево и v - некоторая вершина в D, то D может быть представлен в виде корневого дерева с корнем v.

Изобразим вершину v, расположив её в первом ярусе. Вершины, соседние с v, поместим в первый ярус и соединим дугами с корнем. Вершины, соседние с вершинами первого яруса, отличные от корня, поместим во второй ярус и соединим с соседними с ними вершинами первого яруса.

Продолжаем описанный процесс до тех пор, пока все вершины D не окажутся распределенными по ярусам. Процесс распределения вершин D по ярусам заканчивается через конечное число шагов, так как D имеет конечное число вершин.

Та из двух соседних вершин корневого дерева, которая располагается в ярусе с меньшим номером, называется предком. Вторая из этих вершин называется потомком.

Вершина корневого представления дерева называется висячей, если она не имеет потомков из следующего яруса.

Корневое представление всякого дерева D обладает следующими свойствами:

1) в D имеются висячие вершины;

2) каждая внутренняя вершина корневого дерева является соседней с единственной вершиной предшествующего яруса.

Деревья имеют много различных приложений. Одно из них - представление структур арифметических выражений с помощью корневых деревьев. Это позволяет алгоритмизировать процесс вычисления значений произвольных выражений.

Например, арифметическое выражение (a + b) ´ (c - d)/(a - c) представляется в виде дерева, изображенного на рис. 5.15:

/

´ -

+ - a c