Обхождане на двоично дърво

Разходка по дървото в дълбочина

За разлика от линейните структури като единично свързан списък и масив, които имат канонично, директно обхождане, дърветата могат да бъдат обхождани по няколко начина, в зависимост от конкретната задача. Започвайки от корена, можете да приложите необходимото действие (наричано по-долу "посещение") както към самия възел, така и към неговия ляв или десен клон. Редът, в който се прилагат операциите, ще определи решението.

Най-опростените и ясни алгоритми са рекурсивни. Когато се сведе до итеративен алгоритъм, тъй като дървото приема няколко пътища за обръщане, някои от възлите ще трябва да бъдат "отложени" за по-нататъшна обработка, за което ще се използва стек или опашка.

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

Рекурсивното решение напълно съответства на описанието на алгоритъма

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

Като функция за посещение можете да предадете например такава функция

Помислете сега за резултата от всеки от ходовете.

inOrderTraversal показва първо най-левия възел, след това средния, след това десния. Ако имаше дърво вляво, тогава алгоритъмът се прилага рекурсивно към него. Ако обработваме двоично дърво за търсене, тогава най-левият елемент ще бъде най-малкият елемент, най-десният и най-последният за обработка ще бъде най-големият елемент. Симетричното обръщане ще покаже дървото във възходящ ред. За да сортирате дървото в обратен ред, първо трябва да обработите правилния клон, т.е. функцията

ще отпечата дървото в обратен ред.

postOrderTraversal показва възли отляво надясно, отдолу нагоре. Това има редица приложения, засега ще разгледаме само едно - изтриване на дърво. Обхождането на дърво започва отдолу, с възли, които нямат родители. Те могат да бъдат премахнати безболезнено, тъй като извикванията root-> left и root-> right се случват преди обектът да бъде изтрит.

Позволете ми да ви напомня, че ако искаме да променим указател, трябва да предадем указател на указател.

Итеративното изпълнение на обхождане с дълбочина първо изисква стек. Това е необходимо, за да се "отложи" обработката на някои възли (например тези, които имат необработени наследници, или всички оставени улови и т.н.).

Ще приложим стека с помощта на масив, който ще промени размера си при препълване. Нека ви напомня, че изпълнението на стека изисква две функции - push, която поставя стойност в горната част на стека и pop, която изскача стойността от горната част на стека и я връща. Освен това ще използваме функцията peek, която връща стойност отгоре, но не я премахва.

След като подготвим изпълнението на стека, ще напишем заобиколни решения.

Обхождане първо по широчина

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

Нека бъдем в корена на дървото. След това трябва да посетите всички наследници на корена. По този начин първо трябва да вкарате възела в контейнера, след това неговите потомци, докато възелът трябва първо да бъде обработен първо. Тоест, елементът, който е въведен първи, трябва да бъде обработен първо. Това е опашка и в този пример ще използваме готово изпълнение на опашка, използвайки двойно свързан списък.

C изпълнение

Заменете опашката със стек

Сега функцията заобикаля възлите като Post-Order, само назад.

Прекосяване на безкрайни дървета

Има ситуации, когато е необходимо да се обработи безкрайно дърво. Дървото може да се генерира, когато имаме достъп до него (например, обикаляме сайт, чиито страници се генерират от сървъра по време на достъп), или размерът му просто не е известен (и евентуално голям).

Ако дървото расте безкрайно в дълбочина, тогава то може да бъде обработено с широко преминаване. Тоест, известно е, че ако слезем по клона, тогава няма да стигнем до края, но на това ниво дървото има краен размер.

Ако дървото расте безкрайно по ширина, но в същото време има крайна дълбочина (т.е. възелът има не двама наследници, а от безкрайно много), тогава можете да използвате първо търсене по дълбочина.

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