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

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

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

Листинг 8.2. Вставка в бинарное дерево

function TtdBinaryTree. InsertAt (aParentNode : PtdBinTreeNode;
aChildType : TtdChildType;
altem : 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;
Result74. btParent : = aParentNode ; ResultA.btChild[ctLeft] :=nil;
ResultA.btChild[ctRight] : = nil;
ResultA.btData := altem;
ResultA.btExtra := 0;
aParentNodeA.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 (aNodeA.btChild[ctLeft]<>nil) then begin if (aNodeA.btChild[ctRight]<>nil) then
btError(tdeBinTree2Children, 1 Delete');
OurChildsType :=ctLeft;
end
else
OurChildsType :=ctRight; {выяснить, является ли дочерний узел левым или правым дочерним узлом данного родительского узла) OurType := GetChildType(aNode);

{установить дочернюю связь данного родительского узла равной данной дочерней связи) aNodeА.btParentА.btChild[OurType] : «=

aNodeA.btChild[OurChildsType]; if (aNodeA.btChild[OurChildsType]<>nil) then
aNodeA.btChild[OurChildsType]A.btParent := aNodeA.btParent; {освободить узел) if Assigned(FDispose) then
FDispose(aNodeA.btData);
BTNodeManager.FreeNode(aNode);
dec(FCount) ;
end;

В листинге 8.3 не учтен случай, когда удаляемый узел является нулевым. В любом случае в этой ситуации мало что можно сделать, а генерация исключения была бы излишней. Поэтому метод проверяет, чтобы удаляемый узел не имел двух дочерних узлов. Однако он не разделяет два других случая удаления (т.е. случаи отсутствия дочерних узлов и наличия только одного дочернего узла), а объединяет их в один случай, когда один дочерний узел замещает узел, даже если дочерний узел является нулевым. GetChildType - это небольшая функция, которая возвращает информацию о том, является ли ее параметр узла левым или правым дочерним узлом родительского узла.

Создание бинарного дерева || Оглавление || Перемещение по бинарному дереву


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Октябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс