Определим по индукции понятие упорядоченного дерева:
1) пустое множество и список (a), где a-некоторый элемент, является упорядоченным деревом;
2) если T₁,T₂, … ,Tn-непустые упорядоченные деревья, a-некоторый новый элемент, то список T=(a, T₁,T₂, … ,Tn)есть упорядоченное дерево. При этом элемент aназывается корнем упорядоченного дерева T;
3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.
Если T₁,T₂, … ,Tn-упорядоченные деревья, то список (T₁,T₂, … ,Tn) называется упорядоченным лесом.
Для заданного упорядоченного дерева T определим множество S(T) его упорядоченных поддеревьев:
-если T= , то S(T)= ;
- если T=(a), то S(T)= ;
-если T=(a, T₁,T₂, … ,Tn), то S(T)= S(T1) … S(Tn) .
Непустое упорядоченное дерево T может интерпретироваться в виде системы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T) так, что:
1) если T̕-поддерево упорядоченного дерева T˝, T̕,T˝ S(T), то для соответствующих множеств X̕ и X˝ выполняется включение X̕ X˝;
2) если T̕ не является поддеревом упорядоченного дерева T˝ и T˝ не является поддеревом упорядоченного дерева T̕ (где T̕, T˝ S(T)), то соответствующие множества не пересекаются.
П р и м е р 4.10.1. Упорядоченному дереву
(1,(2,(4),(5)),(3,(6,(8),(9)),(7)))
соответствует система множеств ,изображенная на рис. 4.41.