ів, він повинен мати ключ або не менший, ніж будь-який ключ лівого піддерева видаляється вузла, або не більший, ніж будь-який ключ правого піддерева видаляється вузла. Таким властивостям володіють два вузли, самий правий вузол лівого піддерева видаляється вузла і самий лівий вузол його правого піддерева. Будь-яким з цих вузлів їм можна замінити видаляється вузол. Наприклад, на малюнку це вузли М і Р.
Необхідно розрізняти три випадки:
Вузла з ключем, рівним х, немає.
Вузол з ключем, рівним х, має не більше одного нащадка.
Вузол з ключем, рівним х, має двох нащадків
Допоміжна рекурсивна процедура del викликається тільки у випадку, коли видаляється вузол має двох нащадків. Вона "спускається вздовж" самої правої гілки лівого піддерева видаляється вузла q ^ (при виклику процедури їй передається як параметр покажчик на ліве піддерево) і, потім, замінює істотну інформацію (у нашому випадку ключ data) в q ^ відповідним значенням самого правого вузла r ^ цього лівого піддерева, після чого від r ^ можна звільнитися.
View - Друк дерева, обходячи його справа наліво. Чим далі елемент від кореня, тим більше йому буде передувати прогалин, т. о. шляхом нескладного алгоритму виходить цілком зручно читане дерево.
Exist - перевірка існування елемента із заданим ключем. Шукаємо елемент, рухаючись від кореня і переходячи на ліве або праве піддерево кожного вузла в Залежно від його ключа.
Destroy - видалення дерева. Обходячи дерево зліва направо, видаляє елементи. Спочатку видаляються нащадки вузла, потім сам вузол. br/>
Відмінності між описами кодів програмах на різних мовах відносяться в основному до Конструктори і деструкції. У. Pas програмах вони визначаються директивами і викликаються явно як методи класу з програми, а в. cpp конструктор викликається при створенні елемента класу і деструктор автоматично при виході з програми (для чого об'єкт класу розміщується в пам'яті динамічно).
3. Код програми
В
program PTree;
{$ APPTYPE CONSOLE}
type
TInfo = Byte;
PItem = ^ Item;
Item = record
Key: TInfo;
Left, Right: PItem;
end;
TTree = class
private
Root: PItem;
public
constructor Create;
procedure Add (Key: TInfo);
procedure Del (Key: TInfo);
procedure View;
procedure Exist (Key: TInfo);
destructor Destroy; override;
end;
// --------------------------------------------- ----------------
constructor TTree.Create;
begin
Root: = nil;
end;
// --------------------------------------------- ----------------
procedure TTree.Add (Key: TInfo);
procedure IniTree (var P: PItem; X: TInfo);// створення кореня дерева
begin
...
