Схема проходження дерева

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

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

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

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

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

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

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

template <class T>

void Postorder (TreeNode <T> * 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), вона впорядковує елементи за допомогою оператора відношення "<". Щоб порівняти вузли дерева, ми маємо на увазі, що частина або все поле даних визначено в якості ключа і оператор "<" порівнює ключі, коли розміщує елемент на дереві. Бінарне дерево пошуку будується за наступним правилом:

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

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

Наприклад, пошук числа 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, яке зберігається у вузлі.

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

На перший погляд напрошується рішення вибрати сина вузла 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;

Не нашли, что искали? Воспользуйтесь поиском: