AlgorithmO #18 — Обхождане на двоични дървета

(Първо публикувано на 29.01.2017)

Днес ще се позанимаваме с нещо малко по-различно — обхождане на двоични дървета.

Няма да се спирам върху обяснения на това какво е двоично дърво — в книгата на Светлин Наков е обяснено прекрасно. Там е обяснена цялата терминология, която може да срещнете в този пост.

Тъй като последните няколко поста бяха за алгоритми от категорията “разделяй и владей”, може да се учудите, но и този спада към тях. Причината е, че двоичното дървото като структура включва корен, ляво поддърво и дясно поддърво (т.е. частта “разделяй” е в самата й дефиниция). Това подсказва, че обработката на такива дървета ще използва именно подхода “разделяй и владей”.

Нека да видим за какво иде реч. 😀

Трудно беше да избера картинка за този пост, но тази е непобедима… :)

ОПИСАНИЕ:

“Обхождане” означава да преминем през всеки един елемент на дадена структура. В структури като стек, опашка, свързан списък и т.н. има само един логически път, по който можем да направим това обхождане.

За двоичните дървета, обаче, това не е така. Тях можем да ги обходим по 3 начина:

1. КЛД (Корен-Ляво-Дясно или Preorder)
   - първо обхождаме корена, след това лявото поддърво и накрая дясното поддърво

2. ЛКД (Ляво-Корен-Дясно или Inorder)
   - първо обхождаме лявото поддърво, след това корена и накрая дясното поддърво
   - ако дървото е двоично дърво за търсене, елементите накрая ще са във възходящ ред

3. ЛДК (Ляво-Дясно-Корен или Postorder)
   - първо обхождаме дясното поддърво, след това корена и накрая дясното поддърво

АЛГОРИТЪМ:

КЛД Обхождане

1. Посети корена
2. Рекурсивно обходи лявото поддърво
3. Рекурсивно обходи дясното поддърво

ЛКД Обхождане

1. Рекурсивно обходи лявото поддърво
2. Посети корена
3. Рекурсивно обходи дясното поддърво

ЛДК Обхождане

1. Рекурсивно обходи лявото поддърво
2. Рекурсивно обходи дясното поддърво
3. Посети корена

ЗАБЕЛЕЖКА: Като казваме “рекурсивно обходи едното поддърво”, това означава, че навлизаме едно ниво по-дълбоко в дървото и прилагаме съответния алгоритъм върху това поддърво. Продължаваме така докато не стигнем до най-ниското възможно ниво и след това се връщаме обратно от рекурсията.

ПРИМЕР:

Има вероятност на този етап да сте леко объркани (“Що за алгоритъм е това!?”).

Няма проблем, един пример бързо ще изясни нещата. 😅

Нека имаме следното двоично дърво (безсрамно откраднато от книгата на Наков…):

Първо забележете, че дървото не е подредено (т.е. не е “двоично дърво за търсене”) — тоест не е задължително отляво всички елементи да са по-малки от корена, а вдясно всички да са по-големи от него. Това е просто едно старомодно двоично дърво.

И така, нека се опитаме да обходим дървото по 3-те възможни начина.

1. КЛД Обхождане

За да е прегледно, ще запазваме посетените върхове в едно множество (означено с V). Ще приключим алгоритъма когато всички върхове са посетени.

В по-минималистичен вид, дървото ще изглежда така 😁:

С удебелен шрифт ще маркираме корена на дървото, с червен цвят — лявото поддърво, а със зелен — дясното поддърво.

И така, първата стъпка на алгоритъма гласи, че трябва да посетим корена.

Това значи, че добавяме 14 към множеството ни с посетени върхове:

V = { 14 }

Следващата стъпка гласи, че “рекурсивно” ще обходим лявото поддърво. Какво значи това? Това означава, че вземаме лявото поддърво и си представяме, че имаме едно изцяло ново двоично дърво, което изглежда така:

Тъй като в момента правим КЛД обхождане, това означава, че отново вземаме корена и го добавяме към множеството ни с посетени върхове:

V = { 14, 19 }

И така, отново преминаваме към лявото поддърво, което този път ще има само 1 връх — 23.

Добавяме го към множеството с посетени върхове:

V = { 14, 19, 23 }

Тъй като не можем да навлезем по-дълбоко (защото не съществуват поддървета), сега се връщаме към предишното поддърво:

Вече сме посетили корена и лявото поддърво на това дърво — остава да преминем към дясното поддърво (правим Корен-Ляво-Дясно обхождане). Сега разглеждаме следното поддърво:

Схванахте идеята — прилагаме КЛД обхождане. Тъй като това е последното ниво — просто добавяме последователно към множеството — корена (6), левия наследник (10), десния наследник (21):

V = { 14, 19, 23, 6, 10, 21 }

Тъй като това беше последното ниво на поддървото, се връщаме назад:

Тук сме посетили всички върхове, така че се връщаме с още едно ниво назад:

Оказва се, че вече сме обходили изцяло първоначалния корен и първоначалното ляво поддърво. Това означава, че само ни остава да обходим дясното поддърво:

Обхождаме по КЛД и нямаме повече нива, затова просто добавяме последователно корена (15) и след това левия наследник (3) към V:

V = { 14, 19, 23, 6, 10, 21, 15, 3 }

Това е редът, който ще се получи при КЛД обхождане. 😉

2. ЛКД Обхождане

Логиката ще е същата, просто разменяме реда.

Започваме с дървото:

Отново ще добавяме посетените върхове към множество V. Този път обхождането е в ред ЛКД, затова първо трябва рекурсивно да навлезем възможно най-дълбоко в лявото поддърво (т.е. прилагаме ЛКД обхождане на всяко ляво поддърво докато не стигнем връх, който няма ляво поддърво).

Виждаме, че лявото поддърво е означено с червен цвят, затова навлизаме в него:

Отново имаме ляво поддърво, затова навлизаме и в него. Оказва се, че то има само един връх:

Тъй като тук имаме само един връх, няма да обхождаме лявото поддърво (защото такова не съществува). В такъв случай обхождаме корена (23) и го добавяме към V:

V = { 23 }

Остава да обходим дясното поддърво, но такова не съществува, затова се връщаме едно ниво назад:

Тъй като тук вече сме посетили върховете от лявото поддърво, следва да посетим корена (19) и да го добавим към V:

V = { 23, 19 }

Както сами се досещате, остава да обходим дясното поддърво:

Тъй като това е най-дълбокото ниво (нямаме поддървета, произлизащи от наследниците на 6), добавяме последователно — левия наследник (10), корена (6) и десния наследник (21) към V (защото правим ЛКД обхождане):

V = { 23, 19, 10, 6, 21 }

Както казахме, това бе най-дълбокото ниво на поддървото, затова се връщаме с едно ниво назад:

На това ниво сме обходили всеки връх, затова се връщаме още едно ниво назад:

Оказва се, че вече сме обходили лявото поддърво изцяло, затова следва да посетим корена (14) и да го добавим към V:

V = { 23, 19, 10, 6, 21, 14 }

Най-накрая остава да обходим дясното поддърво:

Обхождаме по ЛКД и тъй като нямаме по-дълбоко ниво от това, просто добавяме последователно левия наследник (3) и след това корена (15) към V:

V = { 23, 19, 10, 6, 21, 14, 3, 15 }

Това е редът, който ще се получи при ЛКД обхождане. 😉

3. ЛДК обхождане

Нека да покажем как ще стане и третият вид обхождане.

Започваме със следното дърво:

Тъй като обхождаме в реда “ляво поддърво, дясно поддърво, корен”, започваме с лявото поддърво (отбелязано с червено):

Прилагаме ЛДК обхождане и на това дърво, затова навлизаме към лявото поддърво:

Тук нямаме нито ляво, нито дясно поддърво, а само корен. Липсва ни “ЛД”, но имаме “К, така че добавяме “К” (23) към V 😀:

V = { 23 }

Остава да се върнем назад, тъй като няма къде да навлезем по-дълбоко:

Обходихме лявото поддърво, така че следва да обходим дясното:

Това всъщност е най-дълбокото възможно ниво, затова просто добавяме последователно към V — левия наследник (10), десния наследник (21) и корена (6):

V = { 23, 10, 21, 6 }

Връщаме се назад:

Остава ни само да посетим корена (19):

V = { 23, 10, 21, 6, 19 }

… и да се върнем едно ниво назад:

Продължаваме с дясното поддърво, тъй като правим ЛДК обхождане:

ъй като това е най-дълбокото възможно ниво, последователно добавяме към V — левия наследник (3) и корена (15), понеже липсва десен наследник:

V = { 23, 10, 21, 6, 19, 3, 15 }

Остава да се върнем едно ниво назад:

… и да посетим корена (14):

V = { 23, 10, 21, 6, 19, 3, 15, 14 }

Това е редът, който ще се получи при ЛДК обхождане. 😉

ИМПЛЕМЕНТАЦИЯ (Java):

Следващата имплементация е за двоично дърво за търсене (Binary Search Tree), т.е. горното дърво ще е подредено и реда на обхождане няма да е същият, но принципът се запазва:

—

Това е за днес! Ако видите някоя грешка — напишете коментар или ме намерете във FB!