Динамические структуры данных: двоичные деревья
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
совсем (если степень узла равна 0).
Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева.
{Turbo Pascal}
function Delete(Tree: U; x: BT) : U;
var P, v : U;
begin
if (Tree=nil)
then writeln(такого элемента в дереве нет!)
else if x < Tree^.inf then Tree^.L := Delete(Tree^.L, x) {случай 1}
else
if x > Tree^.inf
then Tree^.R := Delete(Tree^.R, x) {случай 1}
else
begin {случай 1}
P := Tree;
if Tree^.R=nil
then Tree:=Tree^.L
else if Tree^.L=nil
then Tree:=Tree^.R
else begin
v := Tree^.L;
while v^.R^.R <> nil do v:= v^.R;
Tree^.inf := v^.R^.inf;
P := v^.R;
v^.R :=v^.R^.L;
end;
dispose(P);
end;
Delete := Tree
end;
{C++}
BinTree * Delete(BinTree *Tree, BT x)
{ BinTree* P, *v;
if (!Tree) cout << "такого элемента в дереве нет!" << endl;
else if (x L, x);
else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);
else {P = Tree;
if (!Tree->R) Tree = Tree->L; // случай 1
else if (!Tree->L) Tree = Tree->R; // случай 1
else { v = Tree->L;
while (v->R->R) v = v->R; // случай 2
Tree->inf = v->R->inf;
P = v->R; v->R = v->R->L;
}
free(P);
}
return Tree;
}
Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение.
Список литературы
Для подготовки данной работы были использованы материалы с сайта