Структуры даних: бінарну упорядкований незбалансоване дерево

Казанский Державний Технічний Університет їм. А. М. Туполева.

Курсова робота з програмування на тему.

Структури даних: бінарну упорядкований незбалансоване дерево.

Виконав: Зверев І. М.

Перевірив: Рахматуллин А. И.

Казань.

План работы:

1) Постановка задачи.

2) Опис программы.

3) Код програми мовами Pascal і С++.

1. Постановка задачи.

Потрібна написати програму, реалізуючу основні операції роботи з деревом. До того ж, неодмінною умовою є використання структури даних клас для описи дерева і методів роботи з ним.

2. Опис программы.

Опис ведеться для коду на Pascalе, відмінності для З++ зазначатимуться ниже.

У конкурсній програмі основний елемент є клас TTree. Його методи — це основні процедури роботи з деревом:

Create — конструктор класу — процедура, створює дерево,.

Add — метод додавання елемента у дерево,.

Del — метод видалення елемента із дерева,.

View — метод виведення елементів дерева на экран,.

Exist — метод перевірки існування елемента з певним ключем, по суті пошук элемента,.

Destroy — деструктор класу — процедура, удаляющая дерево.

Розглянемо алгоритми роботи процедур.

Create — створення дерева. Привласнює полю Root (корінь) значення nil — покажчика, яке нікуди не указывает.

Add — додавання елемента у дерево. Для побудови дерева використовуємо наступний алгоритм. Перший елемент поміщаємо в корінь (инициализируем дерево). Далі чинимо так. Якщо добавляемый в дерево елемент має ключ більший, ніж ключ вузла, то, якщо вузол не лист, обходимо його справа. Якщо добавляемый елемент має ключ не більшу ніж ключ вузла, то, якщо вузол не лист, обходимо його зліва. Якщо сягнули аркуша, то додаємо елемент відповідно справа чи слева.

Del — видалення елемента із дерева.

Видалення вузла досить просто якщо він листом чи має одного нащадка. Наприклад, якщо потрібно видалити вузол з ключем М треба просто замінити праву заслання вузла До на покажчик на L. Складність залежить від видаленні вузла з цими двома нащадками, оскільки ми можемо вказати одним покажчиком на два направления.

[pic].

[pic]Например, якщо просто видалити вузол з ключем N, то лівий покажчик вузла з ключем Т повинен вказувати одночасно на До і R що ні можливо. І тут удаляемый вузол потрібно замінити в інший вузол з дерева. Постає питання, яким вузлом його замінити? Цей вузол повинен мати двома властивостями: по-перше, він має мати трохи більше одного нащадка; по-друге, задля збереження упорядкованості ключів, він має мати ключ або менший, ніж будь-який ключ лівого поддерева удаляемого вузла, або не більший, ніж будь-який ключ правого поддерева удаляемого вузла. Таким властивостями мають два вузла, найбільш правий вузол лівого поддерева удаляемого вузла і лівий вузол його правого поддерева. Будь-яким з цих вузлів вони можуть замінити удаляемый вузол. Наприклад, малюнку це вузли М і Р.

[pic]Необходимо розрізняти три случая:

1. Вузла з ключем, рівним x, нет.

2. Вузол з ключем, рівним x, має більше потомка.

3. Вузол з ключем, рівним x, має двох потомков.

Допоміжна рекурсивна процедура del викликається лише у разі, коли удаляемый вузол має двох нащадків. Вона «спускається вздовж» самої правої галузі лівого поддерева удаляемого вузла q^ (при виклик процедури їй передається як параметра покажчик на ліве поддерево) і далі, заміняє істотну інформацію (у разі ключ data) в q^ відповідним значенням самого правого вузла r^ цього лівого поддерева, після що від r^ можна освободиться.

View — печатку дерева, обходячи його справа-наліво. Чим більше елемент від кореня, тим більше їй передуватиме прогалин, т. про. шляхом нескладного алгоритму виходить цілком зручно читане дерево.

Exist — перевірка існування елемента з заданим ключем. Шукаємо елемент, рухаючись від кореня і переходячи на ліве чи праве поддерево кожного вузла залежно з його ключа.

Destroy — видалення дерева. Оминаючи дерево зліва-направо, видаляє елементи. Спочатку видаляються нащадки вузла, потім узел.

Відмінності між описами кодів програмах говорять різними мовами належать до основному до конструкторам і деструкторам. У .pas програмах вони визначаються директивами і викликається явно як методи класу з програми, а .cpp конструктор викликається під час створення елемента класу тут і деструктор автоматично на виході з програми (навіщо об'єкт класу розміщається в пам’яті динамически).

3. Код программы.

|program PTree; |#include | | | | |{$APPTYPE CONSOLE} |#pragma hdrstop | | | | |type |typedef int TInfo; | |TInfo = Byte; |typedef struct Item* PItem; | |PItem = ^Item; |struct Item { | |Item = record |TInfo Key; | |Key: TInfo; |PItem Left, Right; | |Left, Right: PItem; |}; | |end; |class TTree { | |TTree = class |private: | |private |PItem Root; | |Root: PItem; |public: | |public |TTree (); | |constructor Create; |void Add (TInfo Key); | |procedure Add (Key: TInfo); |void Del (TInfo Key); | |procedure Del (Key: TInfo); |void View (); | |procedure View; |void Exist (TInfo Key); | |procedure Exist (Key: TInfo); |~TTree (); | |destructor Destroy; override; |}; | |end; | | |//—————————————————|//—————————————————| |—————————————- |—————————————- | |constructor TTree. Create; |TTree:TTree () | |begin |{ | |Root := nil; |Root = NULL; | |end; |} | |//—————————————————|//—————————————————| |—————————————- |—————————————- | |procedure TTree. Add (Key: TInfo); |static void IniTree (PItem& P, TInfo | | |X) //створення деревокореня | |procedure IniTree (var P: PItem; X: |{ | |TInfo); //створення деревокореня |P = new Item; | |begin |P->Key =X; | |New (P); |P->Left = NULL; | |P^.Key :=X; |P->Right = NULL; | |P^.Left := nil; |} | |P^.Right := nil; | | |end; |static void Iendleft (PItem& P, | | |TInfo X) //додавання вузла зліва | |procedure InLeft (var P: PItem; X: |{ | |TInfo); //додавання вузла зліва |PItem R; | |var R: PItem; | | |begin |R = new Item; | |New®; |R->Key = X; | |R^.Key := X; |R->Left = NULL; | |R^.Left := nil; |R->Right = NULL; | |R^.Right := nil; |P->Left = R; | |P^.Left := R; |} | |end; | | | |static void InRight (PItem& P, TInfo| |procedure InRight (var P: PItem; X :|X) //додати вузол справа | |TInfo); //додати вузол справа |{ | |var R: PItem; |PItem R; | |begin | | |New®; |R = new Item; | |R^.Key := X; |R->Key = X; | |R^.Left := nil; |R->Left = NULL; | |R^.Right := nil; |R->Right = NULL; | |P^.Right := R; |P->Right = R; | |end; |} | | | | |procedure Tree_Add (P: PItem; X: |static void Tree_Add (PItem P, TInfo| |TInfo); |X) | |var OK: Boolean; |{ | |begin |int OK; | |OK := false; |OK = false; | |while not OK do begin |while (! OK) { | |if X > P^.Key then //подивитися |if (X > P->Key) //подивитися | |направо |направо | |if P^.Right nil //правий вузол не |if (P->Right ≠ NULL) //правий вузол | |nil |не NULL | |then P := P^.Right //обхід справа |P = P->Right; //обхід справа | |else begin //правий вузол — листок і |else { //правий вузол — листок і треба | |треба додати до нього елемент |додати до нього елемент | |InRight (P, X); //і поклала край |InRight (P, X); //і поклала край | |OK := true; |OK = true; | |end |} | |else //подивитися наліво |else //подивитися наліво | |if P^.Left nil //лівий вузол не |if (P->Left ≠ NULL) //лівий вузол не| |nil |NULL | |then P := P^.Left //обхід зліва |P = P->Left; //обхід зліва | |else begin //лівий вузоллисток і надо|else { //лівий вузоллисток і треба | |додати до нього елемент |додати до нього елемент | |InLeft (P, X); //і поклала край |Iendleft (P, X); //і поклала край | |OK := true |OK = true; | |end; |} | |end; //циклу while |} //циклу while | |end; |} | | | | |begin |void TTree: Add (TInfo Key) | |if Root = nil | | |then IniTree (Root, Key) |{ | |else Tree_Add (Root, Key); |if (Root == NULL) | |end; |IniTree (Root, Key); | |//—————————————————|else Tree_Add (Root, Key); | |—————————————- |} | |procedure TTree. Del (Key: TInfo); |//—————————————————| | |—————————————-static | |procedure Delete (var P: PItem; X: |void delete_ (PItem& P, TInfo X); | |TInfo); | | |var Q: PItem; |static void Del (PItem& R, PItem& Q) | | |//процедура видаляє вузол має | |procedure Del (var R: PItem); |двох нащадків, замінюючи його за самий | |//процедура видаляє вузол має |правий | |двох нащадків, замінюючи його за самий |//вузол лівого поддерева | |правий |{ | |//вузол лівого поддерева |if (R->Right ≠ NULL) //обійти | |begin |дерево справа | |if R^.Right nil then //обійти |Del (R->Right, Q); | |дерево справа |else { | |Del (R^.Right) |//сягнули самого правого вузла | |else begin |//замінити цим вузлом удаляемый | |//сягнули самого правого вузла |Q->Key = R->Key; | |//замінити цим вузлом удаляемый |Q = R; | | |R = R->Left; | |Q^.Key := R^.Key; |} | |Q := R; |} //Del | |R := R^.Left; | | |end; |static void delete_ (PItem& P, TInfo| |end; //Del |X) | | |{ | |begin //Delete |PItem Q; | |if P nil then //шукати удаляемый |//Delete | |вузол |if (P ≠ NULL) //шукати удаляемый | |if X < P^.Key then |вузол | |Delete (P^.Left, X) |if (X < P->Key) | |else |delete_(P->Left, X); | |if X > P^.Key then |else | |Delete (P^.Right, X) //шукати в |if (X > P->Key) | |правом поддереве |delete_(P->Right, X); //шукати в | |else begin |правом поддереве | |//вузол знайдено, треба її видалити | | |//зберегти посилання віддалений узел|else { | | |//вузол знайдено, треба її видалити | |Q := P; |//зберегти посилання віддалений вузол| |if Q^.Right = nil then | | |//справа nil |Q = P; | |//і посилання вузол треба замінити |if (Q->Right == NULL) | |посиланням на цього нащадка |//справа NULL | |P := Q^.Left |//і посилання вузол треба замінити | |else |посиланням на цього нащадка | |if Q^.Left = nil then |P = Q->Left; | |//зліва nil |else | |//і посилання вузол треба замінити |if (Q->Left == NULL) | |посиланням на цього нащадка |//зліва NULL | |P := P^.Right |//і посилання вузол треба замінити | |else //вузол має двох нащадків |посиланням на цього нащадка | |Del (Q^.Left); |P = P->Right; | |Dispose (Q); |else //вузол має двох нащадків | |end |Del (Q->Left, Q); | |else |delete Q; | |WriteLn («Такого елемента у дереві |} | |немає «); |else | |end; |cout Key) | |end; |Search (P-> Left, X); | | |else | |begin |cout Left); | |end; |if (P->Right ≠ NULL) | | |Node_Dispose (P->Right); | |begin |delete P; | |Node_Dispose (Root); |} | |end; |} | |//—————————————————| | |—————————————- |TTree:~TTree () | |procedure InputKey (S: String; var | | |Key: TInfo); |{ | |begin |Node_Dispose (Root); | |WriteLn (S); |} | |ReadLn (Key); |//—————————————————| |end; |—————————————- | | |void inputKey (string P. S, TInfo& Key) | |var |{ | |Tree: TTree; |cout Key; | |Key: TInfo; |} | |begin | | |Tree := TTree. Create; |TTree *Tree = new TTree; | |repeat |int N; | |WriteLn («1-Добавить елемент в |TInfo Key; | |дерево »); |int main (int argc, const char* | |WriteLn («2-Удалить елемент »); |argv[]) | |WriteLn («3-Вывести вузли дерева »); |{ | |WriteLn («4-Проверить існування |do { | |вузла »); |cout.