Представление бинарного дерева в прямоугольной памяти.

При представлении дерева в прямоугольной памяти одно из полей R_Son или L_Son удаляется, т.к. необходимость в нем отпадает. Потомок может размещаться рядом, т.е. в непосредственной близости. Чтобы узнать, есть ли потомок, вводится булево поле L или R. Пусть, например, отсутствует левый потомок. Введем следующие переменные:

i

a

b d

c e

f g h

ndex = 0..max;

t ype Element = record

R _Son: index;

D ata: BaseType;

L: boolean;

end;

var Tree = array [index] of Element;

Порядок называется прямым, если отсутствует левое поддерево. Если же отсутствует правое поддерево, то такой порядок называется фамильным.

R_Son Data L

a

b

c

f

g

d

e

h

T

F

T

F

F

1

2

3

4

5

6

7

8

Применение бинарных деревьев.

1. Любое алгебраическое выражение, которое содержит переменные, числа, знаки операций и скобки можно представить в виде бинарного дерева (исходя из бинарности этих операций). При этом знак операции помещается в корне, первый операнд – в левом поддереве, а второй операнд – в правом. Скобки при этом опускаются. В результате все числа и переменные окажутся в листьях, а знаки операций – во внутренних узлах.

ассмотрим пример: 3  (x – 2) + 4.

+

4 *

3 _

X 2

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

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

2. Классическая программа из класса интеллектуальных: построение деревьев решений. В этом случае не листовые (внутренние) узлы содержат предикаты – вопросы, ответы на которые могут принимать значения “да” или “нет”. На уровне листьев находятся объекты (альтернативы, с помощью которых распознаются программы). Пользователь получает вопросы, начиная с корня, и, в зависимости от ответа, спускается либо на левое поддерево, либо на правое. Таким образом, он выходит на тот объект, который соответствует совокупности ответов на вопрос.

3. Применение практических задач.

Сд типа граф.

Граф – двойка G = (X, U), где X – множество элементов (вершин, узлов), а U представляет собой бинарное отношение на множестве X (U  XX). Если |X| = n (конечно), то граф является конечным. Элементы U называют либо дугами, либо ребрами.

X1

X2

X = {X1, X2, X3, X4}

XX = {(X1,X1), …,(X4,X4)}

U = {(X1,X2), (X1,X3), (X2,X3), (X2,X4)}  U  XX = X²

X3

X4

Если (X_i, X_j) – упорядоченная пара, то такой граф называется ориентированным (орграфом), а элементы U называются дугами. Если (X_i, X_j) = (X_j, X_i), то граф – неориентированный (неорграф), а элементы U называются ребрами.

F: U  R – если задана такая функция, то граф является взвешенным, где R – множество вещественных чисел, т.е. отображение дуги на число.

Вообще:  U  X  X.

Компонентами орграфа являются: дуга, путь, контур. Путь – такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей. Контур – конечный путь, у которого начальная вершина совпадает с конечной. Контур единичной длины называют петлей.

К

X2

X3

омпонентами неорграфа являются, соответственно: ребро, цепь, цикл. Цепь – непрерывная последовательность ребер между парой вершин неориентированного графа. Неориентированный граф называют связным, если любые две его вершины можно соединить цепью. Если же граф – несвязный, то его можно разбить на подграфы. Например:

X6

G = G₁ U G₂

G:

X1

X4

X5

G₁

G₂

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