Понятие бинарные деревья. Операции над бинарными деревьями

Бинарное дерево -это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый- корнем дерева, и, возможно, другие элементы. Эти элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Такие подмножества называются левым и правым поддеревьями исходного дерева. Каждый элемент бинарного дерева называется узлом. Будем предполагать, что каждый узел двоичного дерева имеет идентифицирующий его ключ. На рис.7 приведен пример бинарного дерева, у которого 9 узлов, A - корень дерева, B - корень левого поддерева, C - корень правого поддерева. Каждый узел двоичного дерева может иметь 0, 1 или 2 поддерева. Так на Рис.6 левое поддерево с корнем C исходного бинарного дерева пусто.

Рис.6. Бинарное дерево

Если X - корень бинарного дерева и Y - корень его левого или правого поддерева, то говорят, что X - отец Y, а Y - левый или правый сын X. В примере на рис.6 A - отец для B и C, B - левый сын A, E - отец G, G - его левый сын. Узел, не имеющий сыновей, называется листом. В нашем примере листья: D, G, H, I. Два узла являются братьями, если они сыновья одного отца (B,C - братья). Глубина бинарного дерева определяется длиной самого длинного пути от корня к листу дерева (на рис.6 глубина дерева равна 3). Каждый узел бинарного дерева содержит информационное поле, а также два указателя (на левое и правое поддерево). Очевидно, что для доступа к узлам бинарного дерева необходимо задать указатель на его корень.
Рассмотрим некоторые операции, которые могут быть полезны при использовании бинарного дерева. Пусть P - указатель на узел бинарного дерева Nd. Введем следующие обозначения:

Info (P) - содержимое узла Nd;
Left (P) - указатель на левого сына Nd;
Right(P) - указатель на правого сына Nd.
P = NewD (X) - создание нового бинарного дерева, состоящего из одного узла с информационным полем X; P - указатель на этот узел;
SetLeft (P,X) - создание нового левого сына для узла с указателем P;
SetRight(P,X) - создание нового правого сына для узла с указателем P.

Узел бинарного дерева представляется в программе в виде записи с соответствующими полями, например:

type
Node = ^BDer;
BDer = record
Info: integer; {информационное поле}
Left, Right: Node; {указатели на левое и правое поддеревья}
end;

Пример содержит тексты функции, реализующей операцию NewD (X), и процедур, определяющих операции SetLeft(P,X) и SetRight(P,X).

Дата добавления: 2014-01-04