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

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

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

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

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

Казань

2003

План роботи:

1) Постановка завдання

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

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

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

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

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

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

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

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

Add - метод додавання елемента в дерево,

Del - метод видалення елемента з дерева,

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

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

Destroy - деструктор класу - процедура, що видаляє дерево.

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

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

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

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

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

Наприклад, якщо просто видалити вузол з ключем N, то лівийпокажчик вузла з ключем Т повинен вказувати одночасно на К і R що неможливо. У цьому випадку видаляється вузол потрібно замінити на інший вузол здерева. Виникає питання, яким же вузлом його замінити? Цей вузол повиненволодіти двома властивостями: по-перше, він повинен мати не більше одногонащадка, по-друге, для збереження впорядкованості ключів, він повинен матиключ або не менший, ніж будь-який ключ лівого піддереві видаленого вузла, абоне більший, ніж будь-який ключ правого піддереві видаленого вузла. Такимвластивостями володіють два вузли, самий правий вузол лівого піддереві видаляєтьсявузла і самий лівий вузол його правого піддереві. Будь-яким з цих вузлів їм можназамінити видаляється вузол. Наприклад, на малюнку це вузли М і Р.

Необхідно розрізняти три випадки:

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

2. Вузол з ключем, рівним х, має не більше одного нащадка.

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

Допоміжна рекурсивна процедура 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; | |
|//----------------------------------|//---------- ------------------------|< br>|--------------------------- |--------------------- ------ |
| constructor TTree.Create; | TTree:: TTree () |
| begin | (|
| Root: = nil; | Root = NULL; |
| end; |) |
|//----------------------------------|//---------- ------------------------|< br>|--------------------------- |--------------------- ------ |
| 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); | 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); | 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); |//----------------------------------|< br>| |--------------------------- 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

| Delete (P ^. Left, X) | if (X 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); |//----------------------------------|< br>| end; |--------------------------- |
| | Void inputKey (string 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