Упорядоченные и бинарные деревья. Соответствия между ними

Определим по индукции понятие упорядоченного дерева:

1) пустое множество и список (a), где a – некоторый элемент, является упорядоченным деревом;

2) если T₁, T₂,…, T_n – непустые упорядоченные деревья, a – некоторый новый элемент, то список T=(a, T₁,…,T_n) образует упорядоченное дерево. При этом элемент a называется корнем упорядоченного дерева T;

3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.

Если T₁,…,T_n – упорядоченные деревья, то список (T₁,…,T_n) называется упорядоченным лесом.

Для заданного упорядоченного дерева T определим множество S(T) его упорядоченных поддеревьев:

- если , то

- если T=(a), то S(T)={(a)}

- если T=(a,T₁,…,T_n), то

Непустое упорядоченное дерево Т может интерпретироваться в виде системы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T) так, что:

1) если T’ – поддерево упорядоченного дерева T’’; , то для соответствующих множеств X’ и X’’ выполняется включение

2) если T’ не является поддеревом упорядоченного дерева T’’; , соответствующие множества не пересекаются.

Упорядоченное дерево может также интерпретироваться в виде уступчатого списка, который обычно используется в оглавлениях. Любая иерархическая классификационная схема интерпретируется некоторым упорядоченным деревом. Частным случаем упорядоченного дерева является бинарное дерево. Определение понятия бинарного дерева повторяет определение для упорядоченного дерева с ограничением в п.2. Любой упорядоченный лес взаимно однозначно соответствует некоторому бинарному дереву.

Опишем алгоритм преобразования упорядоченного леса T=(T₁,…,T_n) в бинарное дерево B(T):

1) Если n=0,

2) Если n>0, то корнем бинарного дерева B(T) является корень упорядоченного дерева T₁, левое поддерево дерева B(T) – бинарное дерево B(T₁₁,…,T_1m), где T₁=((a₁),T₁₁,…,T_1m), правое поддерево дерева B(T) – бинарное дерево B(T₂,…,T _n).