Деревья_лес_бинарное_дерево

3.2. Спецификация дерева, леса, бинарного дерева

Рассмотрим функциональную спецификацию структуры данных дерева c узлами типа α: Tree of α = Tree (α). При этом лес деревьев Forest (α) определим как L_list (Tree (α)) через уже известную структуру линейного списка L_list с базовыми функциями Cons, Head, Tail, Null (см. 1.6). Базовые операции с деревом задаются набором функций:

1) Root: Tree  α;

2) Listing: Tree  Forest;

3) ConsTree: α  Forest  Tree

и аксиомами (u: α; f: Forest (α); t: Tree (α)):

А1) Root (ConsTree (u, f)) = u;

А2) Listing (ConsTree (u, f)) = f;

А3) ConsTree (Root (t), Listing (t)) = t.

Здесь функции Root и Listing  селекторы: Root выделяет корень дерева, а Listing выделяет лес поддеревьев корня данного дерева. Конструктор ConsTree порождает дерево из заданных узла и леса деревьев.

Тот факт, что структура данных Forest явно определена через L_list (Tree), позволяет реализовать структуру дерева (леса) на базе другой структуры данных, а именно на базе иерархических списков. Достаточно рассматривать при этом описанное в 3.1 скобочное представление дерева как S-выражение специальной структуры. Возможно и другое удобное представление дерева (леса), основанное на некотором соответствии леса и бинарного дерева, описанном далее в 3.3.

Рассмотрим функциональную спецификацию структуры данных бинарного дерева с узлами типа α: BinaryTree (α)  BT (α). Здесь важно различать ситуации обработки пустого и непустого бинарных деревьев, поскольку некоторые операции определяются только на непустых бинарных деревьях. Далее считаем, что значение типа BT есть либо  (пустое бинарное дерево), либо значение типа NonNullBT. Тогда базовые операции типа BT (α) задаются набором функций:

1) Root: NonNullBT  α;

2) Left: NonNullBT  BT;

3) Right: NonNullBT  BT;

4) ConsBT: α  BT  BT  NonNullBT;

5) Null: BT  Boolean;

и набором аксиом (_u: α, _b: NonNullBT (α), _b1, b2: BT (α)):

A1) Null () = true;

A1′) Null (b) = false;

A2) Null (ConsBT (u, b1, b2)) = false;

A3) Root (ConsBT (u, b1, b2)) = u;

A4) Left (ConsBT (u, b1, b2)) = b1;

A5) Right (ConsBT (u, b1, b2)) = b2;

A6) ConsBT (Root (b), Left (b), Right (b)) = b.

Здесь функции Root, Left и Right  селекторы: Root выделяет корень бинарного дерева, а Left и Right  его левое и правое поддеревья соответственно. Конструктор ConsBT порождает бинарное дерево из заданных узла и двух бинарных деревьев. Предикат Null  индикатор, различающий пустое и непустое бинарные деревья.

3.3. Естественное соответствие бинарного дерева и леса

Бинарные деревья особенно полезны, в том числе потому, что существует естественное взаимно-однозначное соответствие между лесами и бинарными деревьями, и многие операции над лесом (деревом) могут быть реализованы как соответствующие операции над бинарным деревом, представляющим этот лес (дерево).

Опишем такое представление леса бинарным деревом (и далее будем называть его естественным). Пусть лес F типа Forest задан как список деревьев T_i типа Tree (для i 1..m):

Тогда Head (F)  первое дерево Т₁ леса F, а Tail (F)  лес остальных деревьев (Т₂ . Т_m). Если далее в дереве Head (F) выделить корень Root (Head (F)) и лес поддеревьев Listing (Head (F)),то исходный лес F представляется как совокупность трех частей:

1) корня первого дерева  Root (Head (F)),

2) леса поддеревьев первого дерева  Listing (Head (F)),

3) леса остальных деревьев  Tail (F).

Из этих трех частей рекурсивно порождается бинарное дерево B (F), представляющее лес F:

B (F)  if Null (F) then 

else ConsBT (Root (Head (F)),

B (Listing (Head (F))),

Согласно этому определению корнем бинарного дерева B (F) является корень первого дерева Т₁ в лесу F, левым поддеревом бинарного дерева B (F) является бинарное дерево, представляющее лес поддеревьев первого дерева Т₁, а правым поддеревом бинарного дерева B (F) является бинарное дерево, представляющее лес остальных (кроме первого) деревьев исходного леса F.

Это формальное определение имеет следующую наглядную интерпретацию. Рассмотрим, для примера, лес из двух деревьев, представленный на рис. 3.5.

Error: Reference source not found

Рис. 3.5. Лес из двух деревьев

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

Error: Reference source not found

Рис. 3.6. Преобразованный лес

Повернув затем изображение леса (рис. 3.6) на 45 о , получаем бинарное дерево, изображенное на рис. 3.7.

Error: Reference source not foundРис. 3.7. Бинарное дерево, соответствующее лесу на рис. 3.5

Легко видеть, что, выполняя эти действия в обратном порядке, получим единственный лес, соответствующий данному бинарному дереву. Это обратное преобразование формально описывается следующим образом (здесь F  лес типа Forest, а B  бинарное дерево типа BT):

F (B)  if Null (B) then Nil

else Cons (ConsTree (Root (B), F (Left (B))),

F (Right (B))).

Согласно этому определению первое дерево T₁ леса F образуется из корня бинарного дерева B и леса поддеревьев, полученного из левого поддерева бинарного дерева B. Остальные деревья (Т₂ . Т_m) леса F = (Т₁ Т₂ . Т_m) составляют лес, полученный из правого поддерева бинарного дерева B.

Источник

3. Деревья

Полезной нелинейной структурой данных является дерево (или лес).

3.1. Определения дерева, леса, бинарного дерева. Скобочное представление

Дадим формальное определение дерева, следуя [10].

Дерево – конечное множество Т, состоящее из одного или более узлов, таких, что

а) имеется один специально обозначенный узел, называемый корнем данного дерева;

б) остальные узлы (исключая корень) содержатся в m  0 попарно не пересекающихся множествах Т₁, Т₂, . Т_m, каждое из которых, в свою очередь, является деревом. Деревья Т₁, Т₂, . Т_m называются поддеревьями данного дерева.

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

Каждый узел дерева является корнем некоторого поддерева. В том случае, когда множество поддеревьев такого корня пусто, этот узел называется концевым узлом, или листом. Уровень узла определяется рекурсивно следующим образом: 1) корень имеет уровень 1; 2) другие узлы имеют уровень, на единицу больший их уровня в содержащем их поддереве этого корня. Используя для уровня узла а дерева T обозначение уровень (a, T), можно записать это определение в виде

где T_i – поддерево корня дерева T, такое, что a  T_i.

Говорят, что каждый корень является отцом корней своих поддеревьев и что последние являются сыновьями своего отца и братьями между собой. Говорят также, что узел n – предок узла m (а узел m – потомок узла n), если n – либо отец m, либо отец некоторого предка m.

Если в определении дерева существен порядок перечисления поддеревьев Т₁, Т₂, . Т_m, то дерево называют упорядоченным и говорят о «первом» (Т₁), «втором» (Т₂) и т. д. поддеревьях данного корня. Далее будем считать, что все рассматриваемые деревья являются упорядоченными, если явно не оговорено противное. Отметим также, что в терминологии теории графов определенное ранее упорядоченное дерево более полно называлось бы «конечным ориентированным (корневым) упорядоченным деревом».

Лес – это множество (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Используя понятие леса, пункт б в определении дерева можно было бы сформулировать так: узлы дерева, за исключением корня, образуют лес.

Традиционно дерево изображают графически, например так, как на рис. 3.1.

Error: Reference source not foundРис. 3.1. Графическое изображение дерева

В графическом представлении для изображения структуры дерева используется двухмерность рисунка. При машинной обработке часто удобнее использовать текстовое представление дерева. Например, таким представлением может быть так называемый уступчатый список. Здесь «двухмерность» проявляется за счет того, что текст разбит на строки и фиксируется позиция символа узла в строке. На рис. 3.2, а, б представлено в виде уступчатого списка дерево, изображенное на рис. 3.1.

Другой вид текстового (и принципиально одномерного) представления дерева  это так называемая скобочная запись (ср. с записью иерархических списков в 1.7). Определим скобочное представление дерева и леса:

a ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ а b i b ▓▓▓▓▓▓▓▓▓▓▓▓▓▓

i ▓▓▓▓▓▓▓▓▓▓ j j ▓▓▓▓▓▓▓▓▓▓ c ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ c h h ▓▓▓▓▓▓▓▓▓▓ d ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ d e e ▓▓▓▓▓▓▓▓▓▓ f ▓▓▓▓▓▓▓▓▓▓ f k k ▓▓▓▓▓▓▓ g ▓▓▓▓▓▓▓▓▓▓ g

Рис. 3.2. Представление дерева: а – в виде уступчатого списка; б – в виде «упрощенного» уступчатого списка

В скобочном представлении дерево, изображенное на рис. 3.1, запишется как

(a (b (i) (j)) (c (h)) (d (e) (f (k)) (g))).

Наиболее важным типом деревьев являются бинарные деревья. Удобно дать следующее формальное определение. Бинарное дерево  конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых правым поддеревом и левым поддеревом. Так определенное бинарное дерево не является частным случаем дерева. Например, бинарные деревья, изображенные на рис. 3.3, различны между собой, так как в одном случае корень имеет пустое правое поддерево, а в другом случае правое поддерево непусто. Если же их рассматривать как деревья, то они идентичны.

Рис. 3.3. Бинарные деревья из двух узлов

Определим скобочное представление бинарного дерева (БД):

Здесь пустое дерево имеет специальное обозначение  .

Например, бинарное дерево, изображенное на рис. 3.4, имеет скобочное представление

(a (b (d Λ (h Λ Λ)) (e Λ Λ)) (c (f (i Λ Λ) (j Λ Λ)) (g Λ (k (l Λ Λ) Λ)))).

Error: Reference source not foundError: Reference source not foundРис. 3.4. Бинарное дерево

Можно упростить скобочную запись бинарного дерева, исключив «лишние» знаки  по правилам:

Тогда, например, скобочная запись бинарного дерева, изображенного на рис. 3.4, будет иметь вид

(a (b (d  (h) (e)) (c (f (i) (j)) (g  (k (l))))).

Источник

Алгоритмы и структуры данных

. Определения дерева, леса, бинарного дерева. Скобочное представление

В курсе «Дискретная математика»:

Дерево – связный граф, не содержащий циклов.

Определение (рекурсивное)

Дерево – конечное множество Т , состоящее из одного или более узлов , таких, что

а) имеется один специально обозначенный узел, называемый корнем данного дерева;

б) остальные узлы (исключая корень) содержатся в m 0 попарно не пересекающихся множествах

Т 1 , Т 2 , . Т m , каждое из которых, в свою очередь, является деревом. Деревья Т 1 , Т 2 , . Т m называются поддеревьями данного дерева.

Дерево T = (корень, T 1 , T 2 , …, T m )

узел, лист, отец, сын, брат, предок, потомок Уровень узла (рекурсивно):

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

если а не корень дерева Т

где T i – поддерево корня дерева T , такое, что

Если в определении дерева существен порядок перечисления поддеревьев Т 1 , Т 2 , . Т m ,

то дерево называют упорядоченным и говорят о «первом» ( Т 1 ), «втором» ( Т 2 ) и т. д. поддеревьях данного корня (старший брат и т.п.).

В терминологии теории графов это «конечное ориентированное (корневое) упорядоченное дерево».

Лес – это множество (обычно упорядоченное),

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

Тогда пункт б) определения дерева:

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

Дерево T = (корень, лес поддеревьев)

Источник