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

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

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

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

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

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

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

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

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

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

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

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