Правое скобочное представление

Правое скобочное представление дерева — один из способов представить дерево в виде строки.

Пример дерева

Алгоритм построения правого скобочного представления дерева:

Правое скобочное представление дерева Т rrep(T) можно получить, применяя к нему следующие рекурсивные правила:

а) Если корнем дерева Т служит вершина А с поддеревьями $T_{1}$ , $T_{2}$ , … , $T_{n}$, то rrep(T)=(rrep($T_{1}$)rrep($T_{2}$)…rrep($T_{n}$))A

б) Если корнем дерева Т служит вершина А, не имеющая прямых потомков, то rrep(T)=A

Например, правое скобочное представление для дерева на иллюстрации: (((4 5)3 6)2 7 ((10 11)9 12)8)1