Для обработки дерева с потоками необходимо иметь возможность добавлять
и удалять узлы дерева, сохраняя при этом верные связи.
Предположим, вы хотите добавить нового левого потомка узла А. Так как это
место не занято, то на месте указателя на левого потомка узла А находится ссылка,
которая указывает на предшественника узла А. Поскольку новый узел будет ле-
вым потомком узла А, он станет предшественником узла А. Узел А станет новым
потомком нового узла. Узел, который был предшественником узла А, теперь ста-
новится предшественником нового узла. На рис. 6.23 показано дерево с
после добавления нового узла X в качестве левого потомка узла Н.
Рис. 6.23. Дерево с потоками после добавления узла X
Если отслеживать индекс первого и последнего узлов дерева, то потребуется
проверить, не является ли новый узел первым узлом дерева. Если поток предше-
ственника нового узла имеет значение nil, то это новый первый узел дерева.
Учитывая все вышеизложенное, можно легко написать процедуру для добав-
ления нового левого потомка узла. Вставка правого потомка выполняется таким
же образом.
procedure AddLeftChild(parent, child : PThreadedNode);
begin
// Предшественник родительского узла
// становится предшественником нового узла.
child^.LeftChild := parent^.LeftChiId;
PThreadedNode);
child^.HasLeftChild := False;
// Вставка узла.
parent^.LeftChild := child;
parent^.HasLeftChild := True;
// Родительский узел является потомком нового узла.
child^.RightChild := parent;
child^.HasRightChild := False;
// He является ли новый узел первым узлом дерева?
if (child^.LeftChild = nil) then
FirstNode := child;
end;
Прежде чем удалить узел из связанного дерева, вы должны удалить его по-
томков. Если узел не имеет дочерних, ликвидировать его очень легко.
Предположим, что удаляемый узел - левый дочерний узел. Его левый указа-
тель - ссылка на его предшественника. Когда данный узел удален, этот предшествен-
ник становится предшественником родительского узла. Чтобы удалить узел, просто
замените левый указатель на дочерний узел указателем потомка удаленного узла.
Указатель на правого потомка удаляемого узла - ссылка, указывающая на сле-
дующий узел в дереве. Поскольку этот узел - левый потомок родительского узла
и у него нет дочерних, эта ссылка указывает на родительский узел, следовательно,
ее можно просто опустить. На рис. 6.24 показано дерево с рис. 6.23 после удаления
узла F. Способ удаления правого наследника аналогичен.
Рис. 6.24. Дерево с потоками после удаления узла F
procedure RemoveLeftChild(parent : PThreadedNode);
var
target : PThreadedNode;
begin
target := parent^.LeftChild;
parent^.LeftChild := target^.LeftChild;
end;
|
Главная
Каталог файлов
