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

Бинарное дерево -это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый- корнем дерева,и , возможно , другие элементы. Эти элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Такие подмножества называются левыми правым поддеревьямиисходного дерева. Каждый элемент бинарного дерева называется узлом.Будем предполагать, что каждый узел двоичного дерева имеет идентифицирующий его ключ. На рис.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).