unit Tree;

Если ты это читаешь, то с меня мороженное)

interface

uses Node, SysUtils;

type
    TTree = class
        RootNode: TNode;
        procedure Add(Value: Integer); // объявляем процедуру добавления
        procedure Delete(Value: Integer); // объявляем процедуру удаления
        // объявляем рекурсивную функцию удаления
        function DeleteRecursive(Current: TNode; Value: Integer): TNode;
        // объявляем рекурсивную процедуру добавления
        procedure AddRecursive(Current: TNode; Value: Integer);
        // процедура для полной очистки дерева
        procedure Clear();
        // функция для получения наименьшего элемента в правом поддереве
        function GetSmallest(Root: TNode): Integer;
    end;

implementation

procedure TTree.Clear();
begin
    // чтобы полностью очистить дерево достаточно присвоить корню nil
    RootNode := nil;
end;




// реализация процедур/функций дерева
function TTree.GetSmallest(Root: TNode): Integer;
begin
    if (Root.Left = nil) then
        // если нижняя левая нода равна nil, то возвращаем значение текущейноды
        Result := Root.Value
    else
        // иначе рекурсивно вызываем эту функцию для левой ноды
        Result := GetSmallest(Root.Left);

end;


procedure TTree.Add(Value: Integer);
begin
    // если корень равен nil, то присваиваем его новую ноду со значением  Value
    if RootNode = nil then
        RootNode := TNode.Create(Value)
    else
        // иначе вызываем рекурсивную процедуру добавления
        AddRecursive(RootNode, Value)
end;

procedure TTree.Delete(Value: Integer);
begin
    // вызываем рерурсивную процедуру удаления
    RootNode := DeleteRecursive(RootNode, Value);
end;

function TTree.DeleteRecursive(Current: TNode; Value: Integer): TNode;
var
    Smallest: Integer;
begin

    // в переменной Value у нас значение, которое надо удалить
    // если оно равно значение текущей ноды, то удаляем текущую ноду
    if (Value = Current.Value) then
    begin
        if (Current.Left = nil) and (Current.Right = nil) then
        begin
            Current := nil;
            Result := Current;
        end
        else if ((Current.Right = nil) and (Current.Left <> nil)) then
            // если существует только левый потомок, то возвращаем его
            Result := Current.Left

        else if ((Current.Left = nil) and (Current.Right <> nil)) then
            // если существует только правый, то вернём его
            Result := Current.Right
        else
        begin
            // если два прошлых ифа не сработали, то это значит, что у текущей ноды два потомка
            // по правилу удаления получаем минимальный элемент из правого поддерева
            Smallest := GetSmallest(Current.Right);
            // и присваиваем его текущей ноде
            Current.Value := Smallest;
            // после чего надо удалить тот минимальный элемент
            Current.Right := DeleteRecursive(Current.Right, Smallest);
            Result := Current;
        end;
    end
    else if (Value < Current.Value) then
    begin
        // если искомое значение меньше значения текущей ноды,
        // то будем смотреть левого потомка
        Current.Left := DeleteRecursive(Current.Left, Value);
        Result := Current;
    end
    else
    begin
        // остается только случай, когда искомое значение больше значения текущей ноды
        // в таком случае смотрим левого потомка
        Current.Right := DeleteRecursive(Current.Right, Value);
        Result := Current;
    end;

end;

procedure TTree.AddRecursive(Current: TNode; Value: Integer);
begin
    // если значение, которое мы хотим добавить меньше значения текущей ноды
    // то идём в правое поддерево
    if (Current.Value < Value) then
    begin

        if (Current.Right = nil) then
            // если правой ноды не существует, то создаем её и записываем туда значение,
            // которое хотели добавить
            Current.Right := TNode.Create(Value)
        else
            // правая нода существует, рекурсивно вызываем добавление, передавая туда правую ноду
            AddRecursive(Current.Right, Value);
    end
    // если значение, которое мы хотим добавить больше значения текущей ноды
    // то идём в левое поддерево
    else if (Current.Value > Value) then
    begin
        if (Current.Left = nil) then
            // если левой ноды не существует, то создаем её и записываем туда значение,
            // которое хотели добавить
            Current.Left := TNode.Create(Value)
        else
            // левая нода существует, рекурсивно вызываем добавление, передавая туда правую ноду
            AddRecursive(Current.Left, Value);

    end;

end;

end.