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

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

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.

1

3

2

6

8

7

5

4

9

рис. 4.41

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

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

1

2

4

5

3

6

8

9

7

рис. 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а.

A

I

B

F

D

G

J

H

E

C

E

D

A

C

B

J

I

G

F

H

a б

рис. 4.44