Пример обхода дерева с помощью рекурсии
Procedure obhod(p:tree);
Begin
if p<>nil then
begin
obhod(p^.left);
writeln(p^.inf);
obhod(p^.right);
end;
end;
3. Вставка узла в двоичное дерево поиска не представляет сложности. Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.
Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.
Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя.
Сложнее всего случай, когда у удаляемого узла есть оба потомка.
Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу. Рассмотрите этот случай на рисунке, должно стать понятней.
В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.
Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.
Рассмотрим реализацию алгоритма удаления.
Пример программы удаления узла из дерева
procedure del ( var root : tree ; key : integer );
var
p : tree ; {удаляемый узел}
parent : tree ; {предок удаляемого узла}
y : tree ; {узел, заменяющий удаляемый}
function spusk(p:tree):tree;
var
y : tree ; {узел, заменяющий удаляемый}
pred:tree; { предок узла “y”}
begin
y:=p^.right;
if y^.left=nil then y^.left:=p^.left {1}
else {2}
begin
repeat
pred:=y; y:=y^.left;
until y^.left=nil;
y^.left:=p^.left; {3}
pred^.left:=y^.right; {4}
y^.right:=p^.right; {5}
end;
spusk:=y;
end;
begin
if not find(root, key, p, parent) then {6}
begin writeln(‘ такого элемента нет ’); exit; end;
if p^.left=nil then y:=p^.right {7}
else
if p^.right=nil then y:=p^.left {8}
else y:=spusk(p); {9}
if p=root then root:=y {10}
else {11}
if key<parent^.inf then
parent^.left:=y
else parent^.right:=y;
dispose(p); {12}
end.
В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .
В операторах {7}-{9} определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева ({7}).
Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева ({8}).
В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву ({9}).
В этой функции первым делом проверяется особый случай, описанный выше ({1}). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл ({2}), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).
В операторе {3} к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла ({5}), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый ({4}), поскольку этот узел перейдет на новое место.
Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень ({10}), иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла ({11}).
После того как узел удален из дерева, освобождается занимаемая им память ({12}).