Русская Википедия:Правое скобочное представление

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

а) Если корнем дерева Т служит вершина А с поддеревьями <math>T_1</math> , <math>T_2</math> , … , <math>T_n</math>, то rrep(T)=(rrep(<math>T_1</math>)rrep(<math>T_2</math>)…rrep(<math>T_n</math>))A

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

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

Шаблон:Math-stub Шаблон:Compu-prog-stub Шаблон:Rq