Ім'я файлу: ß½á⌐ñδ_ïѬµ_3.doc
Розширення: doc
Розмір: 989кб.
Дата: 07.06.2020
скачати
Пов'язані файли:
коронавірус.ru.uk.docx

Реалізація класу Node 1

Клас Node містить як відкриті, так і закриті дані-члени. Відкриті дані-члени призначаються для того, щоб користувач і класи колекцій могли мати прямий доступ до їх значення. Поле next є закритим, і доступом до цього поля покажчика управляють функції-члени. Тільки методам InsertAfter і DeleteAfter дозволяється змінювати значення поля next. Якщо зробити це поле відкритим, користувач отримає можливість порушувати зв'язок і знищувати зв'язаний список. Клас Node містить функцію-член NextNode, яка дозволяє клієнту проходити по зв'язаному списку.
// Конструктор, ініціалізація даних і вказівника

template

Node::Node(const T& item, Node* ptrnext) :

data(item), next(ptrnext)

{}

Метод NextNode надає клієнтові доступ до поля вказівника next. Цей метод повертає значення next і використовується для проходження по списку.
// Повернути закритий член next

template 2

Node *Node::NextNode(void) const

{

return next;

}
Створення вузла
Ми реалізуємо створення вузла з використанням заснованої на шаблоні функції GetNode, яка приймає початкові дані-значення і покажчик та динамічно створює новий вузол. Якщо виділення пам'яті відбувається невдало, програма завершується, інакше, функція повертає вказівник на новий вузол.
// Виділення вузла з даними-членом item і вказівником nextPtr

template

Node *GetNode(const T& item, Node *nextPtr - NULL)

{

Node *newNode;

// Виділення пам'яті при передачі item і NextPtr конструктору.

// Завершення програми, якщо виділення пам'яті

// виконалося невдало 3

newNode ш new Node(item, nextPtr);

if (newNode == NULL)

{

cerr << "Помилка виділення пам'яті!" « endl;

exit(1);

}

return newNode;

}
Перед початком вставки елементу у список його голова визначає початок списку. Після вставки новий вузол займе положення на початку списку, а попередній початок списку займе другу позицію. Отже, полю вказівника нового вузла присвоюється поточне значення голови, а голові присвоюється адресу нового вузла. Призначення виконується з використанням GetNode для створення нового вузла.
head = GetNode(item,head);

4


Функція InsertFront приймає поточну голову списку, яка є вказівником, визначаючим список, а також приймає нове значення даних. Вона вставляє значення даних у вузол на початку списку. Так як голова буде змінюватися цією операцією, вона передається як контрольний параметр.
// Вставка елемента в початок списку

template

void InsertFront(Node* & head, T item)

{

// Створення нового вузла, щоб він вказував на

// Первісну голову списку 5

// Зміна голови списку

head = GetNode (item, head);

}
Функції InsertAfter і DeleteAfter є основними операціями створення списків. У кожному разі процес включає тільки зміни вказівника.
// вставити вказівник р після поточного вузла

template

void Node::InsertAfter(Node *p)

{

// p вказує на наступний за поточним вузол,

// a поточний вузол - на р..

p->next = next;

next = р;

}
// видалити вузол, наступний за поточним, і повернути його адресу

template

Node *Node::DeleteAfter(void)

{ 6

// зберегти адресу вузла, що видаляється

Node * tempPtr = next;

// Якщо немає наступного вузла, повернути NULL

if (next =« NULL)

return NULL;

// Поточний вузол вказує на вузол, наступний за tempPtr.

next = tempPtr-> next;

// Повернути вказівник на непов'язаний вузол

return tempPtr;

}
Об’єднання (конкатенація) списків.
Якщо операція об’єднання списків, тоді:

.

Властивості операції.

Нехай – списки.

1. .

2. .

Реалізація операції. 7

Модифікація операції (вставка у середину списку)

.

Супроводжується двома діями:

1) ;

2) .
Циклічні списки.

Схема структури циклічного списку:



Звернемо увагу на те, що звичайному списку його голова позначається як head, а у циклічному – header.

Зауважимо, що для стандартного пов'язаного списку і

циклічного зв'язаного списку тести, 8

що визначають, чи є список порожнім, різні.

Стандартний зв'язаний список: head == NULL

Циклічний зв'язаний список: header-> next == header

Схема порожнього списку наступна:



При додаванні вузлів до списку останній вузол вказує на заголовний вузол.
Двозв'язані списки

Вузол у двозв'язному списку містить два вказівники для створення потужної і гнучкої структури обробки списків.

Слід звернути увагу на те, що зв’язки полів вказівників мають обопільні посилання «у право і у ліво», як це показано на наступному малюнку:

9


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

У двозв'язному списку вузол може видалити сам себе зі списку, змінюючи два вказівники. На наступному малюнку

показані відповідні цьому зміни: 10


Введення додатних вказівників (ключів) у вузлові структури даних дозволяють конструювати різноманітні об’єкти даних (дерева, графи тощо).
Графи.

Граф упорядкована сукупність вершин і пар вершин , який можна позначити як: . Де , – декартовий добуток множини самої на себе. Якщо пари упорядковані, то граф зветься орієнтований або –

орграф, в протилежному випадку не орієнтованим. 11

Граф може представлятися графічно або аналітично.

Нехай , тоді графічне представлення є .

Характеристики графу

  1. Шлях графу послідовність зв’язаних вершин , – початок шляху, – кінець шляху.

  2. Довжина шляху (глибина графу на шляху ) – кількість вершин шляху – 1.

  3. Петля графу .

  4. Контур графу – шлях, у якому початкова і кінцева вершини однакові.

  5. Шлях повний, якщо його не можна доповнити ні одною вершиною графа.

  6. Степінь вершини графу – кількість вхідних і вихідних дуг вершини .

Часткові випадки графів. 12

Дерево – граф, який має одну спільну вершину для всіх повних шляхів і не містить петель та контурів. Спільна вершина є корінь дерева. Заключна вершина повного шляху є листом дерева.

Ліс – Дверевовидний граф з декількома корінями і спільними вершинами.
ні дерева і їх різновиди.

Бінарні дерева .

2 – 3 дерева .

Збалансовані дерева. Дерево є збалансованим, якщо для всіх повних шляхів справедливе або для деяких шляхів .

В – дерева. Дерева, вузли яких містять комбінації даних та ключів і зв'язок між вузлами здійснюється через ключі на дані суміжних вузлів.

Приклад вузла В – дерева:

Структури даних – дерева 13

Вузол дерева містить поле даних і два поля з вказівниками. Поля вказівників називаються лівим вказівником (left) і правим вказівником (right), оскільки вони вказують на ліве і праве піддерево, відповідно. Значення NULL є ознакою порожнього вказівника або піддерева, коли обидва вказівники мають значення NULL.

Вироджене дерево еквівалентне зв'язаному списку.

Дерева з великою щільністю дуже важливі в якості структур даних, оскільки вони містять пропорційно більше елементів поблизу кореня, тобто з більш короткими шляхами від кореня. Щільне дерево дозволяє зберігати великі колекції даних і здійснювати ефективний доступ до елементів.

14


Швидкий пошук - головне, що обумовлює використання дерев для зберігання даних.

Повні бінарні дерева дають цікаві математичні факти. На нульовому рівні є 20 вузлів, на першому – 21, на другому – 22 і т.д. На перших к-1 рівнях мається 2 вузлів.

На к-му рівні кількість додаткових вузлів коливається від 1 до 2к. У повному дереві число вузлів дорівнює

1 + 2 + 4 + ... + 2 + 2 = 2 – 1.
Проектування класу TreeNode 15

У цьому пунктіі розробляється клас TreeNode, в якому оголошуються об'єкти-вузли бінарного дерева. Вузол складається з поля даних, яке є відкритим (public) елементом, тобто до якого користувач може звертатися безпосередньо. Це дозволяє програмістові читати або оновлювати дані під час проходження дерева, а також допускає повернення посилання на дані. Остання особливість використовується більш складними структурами даних, такими як словники. Два поля з вказівниками є закритими елементами, доступ до яких здійснюється за допомогою функцій Left () і Right ().

Специфікація класу TreeNode
ОБ’ЯВЛЕННЯ

// BinSTree залежить від TreeNode

template

class BinSTree;
// Оголошення об'єкта для вузла бінарного дерева

template

class TreeNode 16
{

private:

// вказівники лівого і правого дочірніх вузлів

TreeNode * left;

TreeNode * right;

public:

// Відкритий елемент, що допускає оновлення

Т data;

// Конструктор

TreeNode (const T & item, TreeNode * lptr = NULL,

TreeNode * rptr = NULL);
// Методи доступу до полів вказівників

TreeNode * Left (void) const;

TreeNode * Right (void) const;

// Зробити клас BinSTree дружнім, оскільки він необхідний

// Доступ до полів left і right

friend class BinSTree ; 17

};

ОПИС

Конструктор ініціалізує поля даних і вказівників. За допомогою порожнього вказівника NULL вузли ініціалізуються як листя. Маючи вказівник Р об'єкта TreeNode як параметр, конструктор приєднує Р як лівого або правого сина нового вузла. Методи доступу Left і Right повертають відповідний вказівник.

Клас BinSTree оголошується дружнім класу TreeNode і може модифіковати вказівники. Інші клієнти повинні використовувати конструктор для створення вказівників і методи Left і Right для проходження дерева.

ПРИКЛАД

// вказівники цілочисельних вузлів дерева

TreeNode * root, * lchild, * rchild;

TreeNode * p;

// Створити листя, що містить 20 і 30 в якості даних

lchild - new TreeNode (20);

rchild »new TreeNode (30);

// Створити корінь, що містить число 10 і двох синів

root * new TreeNode (10, lchild, rchild); 18


root-> data = 50; // привласнити кореню 50
Реалізація класу TreeNode Клас TreeNode ініціалізує поля об'єкту. Для ініціалізації поля даних конструктор має параметр item. вказівники призначають вузлу лівого і правого сина (піддерево). за відсутності сина використовується значення NULL.
// Конструктор ініціалізує поля даних і вказівників

// Значення NULL відповідає порожньому піддереву

template

TreeNode :: TreeNode (const T & item, TreeNode * lptr,

TreeNode * rptr): data (item), left (lptr), right (rptr) 19

{}
Методи Left і Right повертають значення полів лівого і правого вказівників. Завдяки цьому програміст має доступ до лівого і правого синів вузла.
Побудова бінарного дерева

Бінарне дерево складається з колекції об'єктів TreeNode, пов'язаних за допомогою своїх полів з вказівниками. Об'єкт TreeNode створюється динамічно за допомогою функції new.

Виклик функції new обов'язково повинен включати значення даних. Якщо, як параметр, передається також вказівник об'єкта TreeNode, тоді він використовується новоствореним вузлом для приєднання вузла сина.

TreeNode * p; // оголошення вказівника

// на цілочисельний вузол дерева

р = new TreeNode (item); // лівий і правий вказівники дорівнюють NULL
20



Визначимо функцію GetTreeNode, що приймє дані і нуль або більше вказівників об'єкта TreeNode, для створення та ініціалізації вузла бінарного дерева. При недостатній кількості доступної пам'яті програма припиняється відразу після видачі повідомлення про помилку.
// Створити об'єкт TreeNode з вказівними полями lptr і rptr.

// За замовчуванням вказівники містять NULL.

template

TreeNode * GetTreeNode (T item, TreeNode * lptr <
TreeNode * rptr - NULL)

{

TreeNode * p;

// Викликати new для створення нового вузла

// Передати туди параметри lptr і rptr

р = new TreeNode (item, lptr, rptr); 21

// Якщо пам'яті недостатньо, завершити програму повідомленням про помилку

if (p == NULL)

{

cerr <<" Помилка при виділенні пам'яті! \ п ";

exit (l);

}

// Повернути вказівник на виділену системою пам'ять

return p;

}

Функція FreeTreeNode приймає вказівник на об'єкт TreeNode і звільняє займану вузлом пам'ять, викликаючи функцію C + + delete.
// Звільнити динамічну пам'ять, займану даним вузлом

template

void FreeTreeNode (TreeNode * p)

{

delete p;

}

Алгоритми обробки дерев 22
Проходження дерев
Рекурсивні методи проходження дерев
Рекурсивне визначення бінарного дерева визначає цю структуру як корінь з двома піддеревами, які ідентифікуються полями лівого і правого вказівників в кореневому вузлі. Сила рекурсії проявляється разом з методами проходження. Кожен алгоритм проходження дерева виконує в вузлі три дії: заходить у вузол, рекурсивно спускається по лівому піддереву і по правому піддереву. Спустившись до піддерева, алгоритм визначає, що він знаходиться у вузлі, і може виконати ті ж три дії. Спуск припиняється після досягнення порожнього дерева (Вказівник == NULL). Різні алгоритми рекурсивного проходження відрізняються порядком, в якому вони виконують свої дії у вузлі. Ми розглянемо симетричний і зворотний методи, в яких спочатку здійснюється спуск по лівому піддереву, а потім по правому. Інші методи залишаємо вам в якості вправ.


  1. Симетричний метод проходження дерева 23


Симетричний метод проходження починає свої дії у вузлі спуском по його лівому піддереву. Потім виконується друга дія – обробка даних у вузлі. Третя дія - рекурсивне проходження правого піддерева. У процесі рекурсивного спуску дії алгоритму повторюються в кожному новому вузлі.
Схема проходження дерева

Отже, порядок операцій при симетричному методі наступний:

1. Проходження лівого піддерева.

2. Відвідування вузла.

3. Проходження правого піддерева і т.д..
Ми називаємо таке проходження LNR (left, node, right). Для дерева Tree_0 у функції MakeCharTree "відвідування" означає печатка значення з поля даних вузла.
Приклад дерева та його проходження
Розглянемо трьох-рівневе дерево Тгее_0.

24


При симетричному методі проходження дерева Тгее_0 виконуються наступні операції.


Дія

Друк

Зауваження

Спуститися від А до В:

Відвідати В;

В


Лівий син вузла дорівнює NULL

Спуститися від В до D:


D


- листовий вузол

Відвідати D;

D

Кінець лівого піддерева вузла А

Відвідати корінь А:

А




Спуститися від А до С:







Спуститися від С до Е:

Е

- листовий вузол

Відвідати Е;

Е




Відвідати С;

С

Готово!


Вузли дерева відвідуються в порядку В D А Е С, Рекурсивна функція спочатку спускається по лівому дереву [t-> Left ()], а потім відвідує вузол. Другий крок рекурсії спускається по правому дереву [t-> Right ()].
Текст програми цього проходження.

// Симетричне рекурсивне проходження вузлів дерева

template

void Inorder (TreeNode * t, void visit (T & item))

{
26

// Рекурсивне проходження завершується на порожньому піддереву

if (t! - NULL)

{

Inorder (t-> Left (), visit); // спуститися по лівому піддереву

visit (t-> data); // відвідати вузол

Inorder (t-> Right (), visit); // спуститися по правому піддереву

}

}

Приклад результату проходження дерева.

Результат симетричного проходження дерева Тгее_2 здійснюється наступними операторами:

// Функція visit роздруковує поле даних

void PrintChar (char & elem)

{

cout <
}

TreeNode * root;

MakeCharTree (root, 2);

// Сформувати дерево Tree_2 з коренем root 27

// Роздрукувати заголовок і здійснити проходження, використовуючи

// Функцію PrintChar для обробки вузла

cout <"Симетричне проходження:";

Inorder (root, PrintChar);
2. Зворотний метод проходження дерева.

При зворотному проходженні відвідування вузла відкладається до тих пір, поки не будуть рекурсивно пройдені обидва його піддерева. Порядок операцій дає так зване LRN (left, right, node) сканування.
Схема проходження дерева

1. Проходження лівого піддерева.

2. Проходження правого піддерева.

3. Відвідування вузла.

При зворотному проходженні дерева Тгее_0 вузли відвідуються в порядку D В Е С А.
28


Дія

Друк

Зауваження

Спуститися від А до В:




Лівий син вузла В дорівнює NULL

Спуститися від В до D:




D - листовий вузол

Відвідати D;

D

Усі сини вузла В пройдені

Відвідати В;

В

Ліве піддерево вузла А пройдено

Спуститися від А до С:







Спуститися від С до Е:




Е - листовий вузол

Відвідати Е;

Е

Лівий син вузла З

Відвідати С;

С

Правий син вузла А

Відвідати корінь А:

А

Готово!


Наступна функція сканує дані дерева знизу вгору.

29

Ми спускаємося вниз по лівому дереву [t-> Left ()], а потім вниз по правому [t-> Right ()]. Останньою операцією є відвідування вузла знизу вгору.
// Зворотне рекурсивне проходження вузлів дерева

template

void Postorder (TreeNode * t, void visit (T & item))

{

// Рекурсивне проходження завершується на порожньому поддереве

if (t! * NULL)

{

Postorder (t-> Left (), visit); // спуститися по лівому піддереву

Postorder (t-> Right (), visit); // спуститися по правому піддереву

visit (t-> data); // відвідати вузол

}

}

3. Прямий метод проходження дерев (прохід у глибину) 30

Прямий метод проходження визначається відвідуванням вузла в першу чергу і подальшим проходженням спочатку лівого, а потім правого його піддерев (NLR).

Для символьного дерева Тгее_2 має місце наступний порядок


відвідування вузлів.

Прямий: ABDGCEHIF

Симетричний: DGBAHEICF 31

Зворотний: GDBHIEFCA
Бінарні дерева пошуку

Звичайне бінарне дерево може містити велику колекцію даних і все ж забезпечувати швидкий пошук, додавання або видалення елементів. Наприклад, для лінійних структур складність алгоритму пошуку дорівнює , що неефективно для великих колекцій. У загальному випадку деревовидні структури забезпечують значно більшу продуктивність, так як шлях до будь-яких даних не перевищує глибини дерева. Ефективність пошуку максимізується при збаласованому бінарному дереві та становить .

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

Ця структура, і зветься бінарним деревом пошуку (binary search tree), вона впорядковує елементи за допомогою оператора відношення "<". Щоб порівняти вузли дерева, ми маємо на увазі, що частина або все поле даних визначено в якості ключа і оператор "<" порівнює ключі, коли розміщує елемент на дереві. Бінарне дерево пошуку будується за наступним правилом:

32

Для кожного вузла значення даних в лівому піддереві менше, ніж у цьому вузлі, а в правому піддереві - більше або дорівнює.

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

Наприклад, пошук числа 37 вимагає чотирьох порівнянь, починаючи з кореня.


Поточний вузол Дія 33
Корінь = 50 Порівняти ключ = 37 і 50

оскільки 37 <50, перейти в ліве піддерево

Вузол = 30 Порівняти ключ = 37 і 30

оскільки 37> = 30, перейти в праве піддерево

Вузол = 35 Порівняти ключ = 37 і 35

оскільки 37> = 35, перейти в праве піддерево

Вузол = 37 Порівняти ключ = 37 і 37. Елемент знайдений.
Операції на бінарному дереві пошуку.

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

Розглянемо, наприклад, включення вузла 8 в дерево BinSTree_1. Почавши з кореневого вузла 25, визначаємо, що вузол 8 повинен бути в лівому поддереве вузла 25 (8 <25). У вузлі 10 визначаємо, що місце вузла 8 повинно бути в лівому поддереві

вузла 10, яке в даний момент є порожнім. 34

Тому 8 включається в дерево в якості лівого сина вузла 10.
Д о кожного вставленого в дерево вузла існує конкретний шлях. Той же шлях може використовуватися для пошуку елемента. Пошуковий алгоритм бере ключ і шукає його в лівому або в правом піддереві кожного вузла, що становить шлях. Наприклад, пошук елемента 30 на дереві BinSTree__l починається в кореневому вузлі 25 і переходить в праве піддерево (30> 25), а потім в ліве піддерево. (30 <37). Пошук припиняється на третьому порівнянні, коли ключ збігається з числом 30, яке зберігається у вузлі.
35



У зв'язаному списку операція видалення від'єднує вузол і з'єднує його попередника з наступним вузлом. На бінарному дереві пошуку подібна операція набагато складніше, тому що вузол може порушити впорядкування елементів дерева. Розглянемо завдання видалення кореня 25 з BinSTree_l. У результаті з'являються два роз'єднаних піддерева, яким потрібен новий корінь.
36

Н а перший погляд напрошується рішення вибрати сина вузла 25 -скажимо, 37 - і замінити його батька. Однак це просте рішення є невдалим, тому що вузли виявляються не з того боку кореня. Оскільки дане дерево відносно невелике, ми можемо встановити, що 15 або 30 є допустимою заміною кореневого вузла.

Операція Delete (видалення). Операція Delete видаляє з дерева вузол з заданим ключем. Спочатку встановлюється місце цього вузла на дереві і визначається вказівник на його батька. Видалення вузла з дерева вимагає ряду перевірок, щоб визначити, куди приєднувати синів видаляється вузла. Піддерева повинні бути заново приєднані таким чином, щоб збереглася структура бінарногодерева пошуку.

Алгоритм пошуку заміни вузла повинен розглядати чотири випадки, в залежностиі від числа синів. Зауважимо, що якщо вказівник на батька дорівнює NULL, то віддаляється корінь.

С итуація А: Вузол D не має синів, тобто є листом. Оновити батьківський вузол так, щоб його піддерево виявилося порожнім.

Оновлення відбувається шляхом установки RNodePtr в NULL. Коли ми приєднуємо NULL-вузол, батько вказує на NULL.

RNodePtr = NULL; 38

• • •

PNodePtr-> left = RNodePtr;

Ситуація В: Вузол D має лівого сина, але не має правого сина. Приєднати ліве піддерево вузла D до його батька.

Оновлення відбувається шляхом установки RNodePtr на лівого сина вузла D і наступного приєднання вузла R до батькові.

RNodePtr = DNodePtr-> left;

PNodePtr-> right = RnodePtr;



39

Ситуація С: Вузол D має правого сина, але не має лівого сина. Приєднати праве піддерево вузла D до його батька.



Як і в ситуації С, оновлення може бути вчинено шляхом установки RNodePtr на правого сина вузла D і наступного приєднання вузла R до батька.

RNodePtr = DNodePtr-> right;

...

PNodePtr-> left = RnodePtr; 40

Ситуація D: Видалення вузла з двома синами.
В узол з двома синами має у своїх піддеревах елементи, які менше, більше або рівні його власним ключовому значенням. Алгоритм повинен вибрати той вузол, який збереже правильний порядок елементів. Розглянемо наступний приклад.

Видаливши вузол 30, ми створили два "осиротілих" піддерева, які повинні бути знову приєднані до дерева. Для цього потрібно стратегія вибору замінює вузла із решти вузлів. Результуюче дерево має задовольняти визначенню бінарного дерева пошуку.

Виберемо у якості замінюючого самий правий вузол лівого піддерева. Це - максимальний з вузлів, менших ніж видаляється. Від'єднайте цей вузол R від дерева, приєднайте його ліве піддерево до його батьків, а потім поставте R на місце видаляється вузла. У демонстраційному дереві заміняє є вузол 28. Ми приєднуємо його лівого сина (26) до його батькові чи матері (25) і замінюємо віддалений вузол (30) заміняє (28).

Для відшукання самого правого вузла лівого піддерева використовується наступний простий алгоритм.

Крок 1: Оскільки замінює вузол R менше, ніж видаляється вузол D, перейти до лівого піддерева вузла D. Спуститися до вузла 25.

Крок 2: Оскільки R є максимальним вузлом лівого піддерева, знайти його значення, спустившись вниз по правому піддереву. Під час спуску стежте за попереднім вузлом PofRNodePtr. У нашому прикладі зійдіть до вузла 28. PofRNodePtr вказує на вузол 25.

Спуск вниз по правому піддереву передбачає два випадки. Якщо праве піддерево порожнє, то поточної точкою є замінюючий вузол R і PofRNodePtr вказує на видаляється вузол D. Ми приєднуємо праве піддерево вузла D в якості правого піддерева вузла R, а батька Р приєднуємо до R.
RNodePtr-> right = DNodePtr-> right;

PNodePtr-> left = RNodePtr;

Якщо праве піддерево непорожнє, прохід завершується листовим вузлом або вузлом, які мають тільки ліве піддерево. У будь-якому випадку від'єднати вузол R від дерева і приєднати синів

вузла R до батьківського вузла PofRNodePtr. У кожному випадку правий син вузла PofRNodePtr перевстановлюється оператором

(**) PofRNodePtr-> right = PofRNodePtr-> left;

1. R є листом. Від'єднати його від дерева. Оскільки RNodePtr-> left

дорівнює NULL, оператор (**) встановлює правого сина вузла PofR-NodePtr в NULL.

2 . R має ліве піддерево. Оператор (**) приєднує це піддерево в якості правого сина вузла PofRNodePtr.




Алгоритм закінчується заміною видаляється вузла вузлом R. Спочатку сини вузла D приєднуються в якості синів вузла R. Потім вузол R заміщає вузол D як корінь поддерева, утвореного вузлом D.

RNodePtr-> left = DNodePtr-> left;

RNodePtr-> right <<= DNodePtr-> right;
46


скачати

© Усі права захищені
написати до нас