Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Прохождение бинарных деревьев






В ряде алгоритмов обработки деревьев используется так называемое прохождение дерева. Под прохождением бинарного дерева понимают определенный порядок обхода всех вершин дерева. Различают несколько методов прохождения.

Прямой порядок прохождения бинарного дерева (префиксный обход – preorder) можно определить следующим образом:

· попасть в корень

· пройти в прямом порядке левое поддерево

· пройти в прямом порядке правое поддерево

Рис.4.6. Прямой порядок прохождения бинарного дерева

 

Прохождение бинарного дерева в обратном порядке (постфиксный обход – postorder) можно определить в аналогичной форме:

· пройти в обратном порядке левое поддерево

· пройти в обратном порядке правое поддерево

· попасть в корень

Рис.4.7. Обратный порядок прохождения бинарного дерева

 

Определим еще один порядок прохождения бинарного дерева, называемый симметричным (инфиксный обход – inorder):

· пройти в симметричном порядке левое поддерево

· попасть в корень

· пройти в симметричном порядке правое поддерево

Рис.4.8. Симметричный порядок прохождения бинарного дерева


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал