Определение

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

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

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

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

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

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

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

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

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

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

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



 

+  a c

a b с d

Рис. 5.15

Висячие вершины изображенного дерева соответствуют операндам, а внутренние вершины  арифметическим операциям в выражении.

Вычисление значения выражения при заданных значениях операндов состоит в последовательной свертке дерева, определяемой следующей схемой:

1) в дереве выделяется внутренняя вершина, все потомки которой являются висячими вершинами;

2) вычисляется значение операции, приписанной найденной вершине, для значений операндов, приписанных потомкам этой вершины;

3) вычисленное значение заменяет символ операции, приписанный вершине, а ее потомки удаляются из дерева вместе с ведущими в них ребрами;

4) если полученное в результате дерево содержит более одной вершины, то действия 1  4 выполняются еще раз.

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

Упражнение. Составить алгоритм вычисления значений формул, использующих простые переменные, элементы массивов, сравнения, традиционные арифметические функции и операцию условного суммирования. (Для этого следует использовать представление таких формул с помощью корневых деревьев.)

Практически важным классом деревьев являются бинарные деревья.