Упорядоченные и бинарные деревья

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

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

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

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

Если T₁, T₂, ..., Т_n - упорядоченные деревья, то список (T₁, T₂, ..., Т_n) называется упорядоченным лесом.

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

-если Т = Æ, то S(T) = Æ;

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

- если Т=(a, T₁, T₂, ..., Т_n), то S(T)=S(T₁)È...ÈS(T_n)È{Т}.

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

1) если Т' - поддерево упорядоченного дерева Т", Т',Т"ÎS(T), то для соответствующих множеств X' и X" выполняется включение X' Í X";

2) если Т' не является поддеревом упорядоченного дерева Т", Т',Т"ÎS(T), то соответствующие множества не пересекаются.

Пример. Упорядоченному дереву

(1, (2, (4), (6)), (3, (6, (8), (9)), (7)))

соответствует система множеств, изображенная на рис. 4.38.

Рис. 4.38 Рис. 4.39

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

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

Тезис.Любая иерархическая классификационная схема интер­претируется некоторым упорядоченным деревом.

Например, и виде упорядоченного дерева представляется любой терм. На рис. 4.40 изображено упорядоченное дерево, соответствующее терму t=a-b(c:d+e:f).

Рис. 4.40

Частным случаем упорядоченного дерева является бинарное дерево. Определение понятия бинарного дерева повторяет определение для упорядоченного дерева с ограничением пÎ{0,1,2} в п.2. При этом для бинарного дерева Т = ((a),T₁,T₂), бинарное поддерево T₁ называется левым поддеревом, а T₂ – правым поддеревом.

Бинарные деревья имеют более простое устройство, чем упо­рядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответствует некоторому бинарному дереву.

Опишем алгоритм преобразования упорядоченною леса Т = (T₁, T₂, .., T_n) в бинарное дерево В (Т).

Шаг 1. Если n = 0, В(Т) = Æ.

Шаг 2. Если п > 0, то корнем бинарного дерева В(Т) явля­ется корень упорядоченного дерева Т₁, левое поддерево дерева В(Т) - бинарное дерево В(Т₁₁, Т₁₂, …, Т_1m), где Т₁= ((a₁),T₁₁, T_12, ..., T_1m), правое поддерево дерева В(Т) - бинарное дерево В(Т₂, ..., Т_n).