На практике принято использовать фиктивный узел, аналогичный фиктивному заглавному узлу односвязного списка, чтобы каждый реальный узел дерева, включая корневой, имел родительский узел. Корневой узел может быть как левым, так и правым дочерним узлом фиктивного узла, но для определенности примем, что он является левым.
Если мы всерьез намереваемся использовать бинарное дерево, необходимо рассмотреть, как выполняется добавление в дерево элементов (т.е. узлов), удаление элементов из дерева и посещение всех элементов дерева. Последняя операция позволит выполнять поиск конкретного элемента. Поскольку выполнение последних двух операций невозможно без рассмотрения первой, начнем с рассмотрения вставки узла в бинарное дерево.
Чтобы иметь возможность вставить узел в бинарное дерево, необходимо выбрать родительский узел, к которому можно присоединить новый узел в качестве дочернего, и более того, этот узел не может уже иметь два дочерних узла. Мы должны также знать, каким дочерним узлом - левым или правым - должен стать новый узел.
При заданном родительском узле и указании дочерних узлов слева направо код для вставки узла очень прост. Мы создаем узел, устанавливаем в качестве значения его поля данных элемент, который добавляем в дерево, и определяем обе его дочерние связи как nil. Затем, во многом подобно вставке узла в двусвязный список, мы устанавливаем соответствующий дочерний указатель родительского узла так, чтобы он указывал на новый дочерний узел, а )родительский указатель дочернего узла - на родительский узел.
Листинг 8.2. Вставка в бинарное дерево
function TtdBinaryTree.InsertAt(aParentNode : PtdBinTreeNode;
aChildType : TtdChildType; aItem : pointer): PtdBinTreeNode;
begin
{если родительский узел является нулевым, считаем, что выполняется вставка корневого узла}
if (aParentNode = nil) then begin
aParentNode := FHead;
aChildType :=ctLeft;
end;
{выполнить проверку mos о, установлена ли уже дочерняя связь}
if (aParentNode^.btChild[aChildType]<> nil) then
btError(tdeBinTreeHasChild, 'InsertAt');
{распределить новый узел и вставить в качестве требуемого дочернего узла родительского узла}
Result := BTNodeManager.AllocNode;
Result^.btParent := aParentNode;
Result^.btChild[ctLeft] :=nil;
Result^.btChild[ctRight] := nil;
Result^.btData := aItem;
Result^.btExtra := 0;
aParentNode^.btChild[aChildType] := Result;
inc(FCount);
end;
Обратите внимание, что приведенный в листинге 8.2 код вначале проверяет, является ли добавляемый узел корневым. Если да, то переданный родительский узел равен nil. В этом случае метод инициализирует родительский узел значением внутреннего заглавного узла.
Кроме этой проверки метод InsertAt убеждается, что дочерняя связь, которую предполагается использовать для нового узла, действительно не используется. В противном случае это будет грубой ошибкой.
Обратите внимание, что класс бинарного дерева (составной частью которого является этот метод) использует диспетчер узлов для распределения и освобождения узлов. Поскольку все узлы имеют одинаковый размер, в этом, как было сказано в главе 3, заложен глубокий смысл.
А как выполняется удаление узлов? Эта задача несколько сложнее, поскольку узел может иметь один или два дочерних узла. Первое правило удаления может быть сформулировано следующим образом: листовой узел (т.е. не имеющий дочерних узлов) может быть удален без каких-либо нежелательных последствий. При этом мы выясняем, каким дочерним узлом родительского узла является лист, и устанавливаем соответствующую дочернюю связь равной nil. После этого узел может быть освобожден.
Второе правило удаления из бинарного дерева применяется в отношении случая, когда удаляемый узел имеет один дочерний узел. Эта задача также достаточно проста: мы просто перемещаем дочерний узел вверх по дереву, чтобы он стал тем же дочерним узлом родительского узла, каким является удаляемый узел.
Третье правило применяется к случаю, когда удаляемый узел имеет два дочерних узла. Как и можно было предположить, это правило звучит просто: узел не может быть удален. Попытка сделать это является ошибкой. Позже мы рассмотрим вариант бинарного дерева - дерево бинарного поиска, - который содержит достаточный объем дополнительной внедренной в дерево информации, чтобы можно было обойти это ограничение.
Листинг 8.3. Удаление из бинарного дерева
procedure TtdBinaryTree.Delete(aNode : PtdBinTreeNode);
var
OurChildsType : TtdChildType;
OurType : TtdChildType;
begin
if (aNode = nil) then
Exit;
{выяснить, имеется ли единственный дочерний узел, и то, каким узлом он является; при наличии двух дочерних узлов сгенерировать ошибку}
if (aNode^.btChild[ctLeft] <> nil) then begin
if (aNode^.btChild[ctRight] <> nil) then
btError(tdeBinTree2Children, 'Delete');
OurChildsType :=ctLeft;
end
else
OurChildsType :=ctRight;
{выяснить, является ли дочерний узел левым или правым дочерним узлом данного родительского узла}