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

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

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

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

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

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

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

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

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

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

Непустое упорядоченное дерево 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.

рис. 4.41

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

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

рис. 4.42

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

Например, в виде упорядоченного дерева представляется любой терм. На рис. 4.43 изображено упорядоченное дерево, соответствующее терму .

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

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

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

1. Если

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

рис. 4.43

На рис. 4.44б представлено бинарное дерево, соответствующее упорядоченному лесу (T₁,T₂), изображенному на рис. 4.44а.

J

I

G

F

E

H

C

D

B

A

J

I

F

E

G

D

H

C

B

A

a б

рис. 4.44