Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Обходы дерева как рекурсивной структуры данных



Чтобы обработать каким-либо образом множество узлов дерева, его нужно обойти. Каждый узел дерева является корнем поддерева, а его сыновья — тоже корнями поддеревьев. Поэтому алгоритм обхода, запускаясь для узла, должен обработать информацию в узле и запустить такой же алгоритм для каждого из непустых поддеревьев. Существуют три способа сделать это, отличающиеся лишь порядком шагов.

1. Прямой обход:

— обработать узел;

— посетить в прямом порядке каждого сына.

2. Обратный обход:

— посетить в обратном порядке каждого сына;

— обработать узел.

3. Внутренний, или симметричный обход:

— посетить во внутреннем порядке левого сына:

— обработать узел.

— посетить во внутреннем порядке правого сына (остальных сыновей).

Минимальная обработка узла может состоять в присвоении соответствующему в нём полю номера в порядке посещения (разметка) или в выдаче номеров на экран, если они уже имеются, или в формировании последовательности из номеров посещённых узлов. Очевидно, что не существует иных способов отличить один порядок обхода узлов от другого.

При разметке дерева в прямом порядке номер любого узла — наименьший, а при обратном — наибольший в соответствующем поддереве, а диапазон использованных номеров равен мощности поддерева. При разметке внутренним способом номер узла больше любого номера в левом поддереве и меньше любого номера в правом.





Дата публикования: 2015-02-20; Прочитано: 251 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...