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

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

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).