New (P);
P ^. Key: = X;
P ^. Left: = nil;
P ^. Right: = nil;
end;
procedure InLeft (var P: PItem; X: TInfo);// додавання вузла зліва
var R: PItem;
begin
New (R);
R ^. Key: = X;
R ^. Left: = nil;
R ^. Right: = nil;
P ^. Left: = R;
end;
procedure InRight (var P: PItem; X: TInfo);// додати вузол праворуч
var R: PItem;
begin
New (R);
R ^. Key: = X;
R ^. Left: = nil;
R ^. Right: = nil;
P ^. Right: = R;
end;
procedure Tree_Add (P: PItem; X: TInfo);
var OK: Boolean;
begin
OK: = false;
while not OK do begin
if X> P ^. Key then// подивитися направо
if P ^. Right <> nil// правий сайт не nil
then P: = P ^. Right// обхід праворуч
else begin// правий вузол - лист і треба додати до нього елемент
InRight (P, X);// і кінець
OK: = true;
end
else// подивитися ліворуч
if P ^. Left <> nil// лівий сайт не nil
then P: = P ^. Left// обхід зліва
else begin// лівий вузол-лист і треба додати до нього елемент
InLeft (P, X);// і кінець
OK: = true
end;
end;// циклу while
end;
begin
if Root = nil
then IniTree (Root, Key)
else Tree_Add (Root, Key);
end;
// --------------------------------------------- ----------------
procedure TTree.Del (Key: TInfo);
procedure Delete (var P: PItem; X: TInfo);
var Q: PItem;
procedure Del (var R: PItem);
// Процедура видаляє вузол має двох нащадків, замінюючи його на самий правий
// Вузол лівого піддерева
begin
if R ^. Right <> nil then// обійти дерево праворуч
Del (R ^. Right)
else begin
// Дійшли до самого правого вузла
// Замінити цим вузлом видаляється
В
Q ^. Key: = R ^. Key;
Q: = R;
R: = R ^. Left;
end;
end;// Del
begin// Delete
if P <> nil then// шукати видаляється вузол
if X
Delete (P ^. Left, X)
else
if X> P ^. Key then
Delete (P ^. Right, X)// шукати в правому поддереве
else begin
// Вузол знайдений, треба його видалити
// Зберегти посилання на віддалений вузол
Q: = P;
if Q ^. Right = nil then
// Праворуч nil
// І посилання на вузол треба замінити посиланням на цього нащадка
P: = Q ^. Left
else
if Q ^. Left = nil then
// Ліворуч nil
// І посилання на вузол треба замінити посиланням на цього нащадка
P: = P ^. Right
else// вузол має двох нащадків
Del (Q ^. Left);
Dispose (Q);
end
else...
