 |
|
Другие алгоритмы.
Cтруктуры данных. Хранение информации.
ОБХОДЫ ДЕРЕВЬЕВ
- Обход дерева вглубь в прямом порядке ( от корней к листьям ).
- Обход дерева вглубь в обратном порядке - начиная с концевых вершин.
- Обход дерева вширь (сначала уровень 0, затем 1, и т.д.).
Пусть дерево G задано множеством вершин V ( корневая вершина v0 ), дуг - E и Г(v,-) - перечнем потомков вершины v из V. Во многих задачах требуется просмотреть и обработать процедурой USE все вершины V в точности по одному разу.
Имеется много различных способов реализовать такой обход, в различном порядке просматривая вершины дерева. Обходы вглубь основаны на продолжении начатого пути до конечных вершин, вширь - на последовательном просмотре вершин уровня 0 - корневой, 1 - смежных с ней, 2, 3 и т.д., см. рис.
Обход дерева вглубь в прямом порядке ( от корней к листьям ):
Обход порождает следующую последовательность: 0 - 1 - 4 - 5 - 2 - 6 - 7 - 8 - 3
Можно использовать следующую рекурсивную процедуру WALK:
|--------| |---------------------|
| | | |
->¦ USE(v) ¦->¦FOR w из Г(v,-) DO ¦----->
| | | |
|--------| |---------------------|
|
V ¦
|
|----+-----| ¦
| | |
¦ WALK(w) ¦->-
| |
|----------|
|
уровень:
0 | 0=v0
| /|\
| / | \
| / | \
1 | 1 2 3
| /| |\
| / | | \
2 |4 5 6 7
| \
| \
3 | 8
рис.1.
|
Запуск процедуры обращением WALK(v0), процедура USE(v) реализует обработку вершины v.
Hерекурсивный вариант реализации обхода дерева вглубь в прямом порядке потребует использования первоначально пустого стека STACK
--------------| |-------------------------|
| | | |
->¦ v0 => STACK ¦->¦WHILE STACK # ПУСТО DO ¦---->
| | | |
--------------| |-------------------------|
V ¦
|-----------------| ¦
| |
¦ v<=STACK ¦ ¦
| |
¦ USE(v) ¦->-
| |
¦ Г(v,-) => STACK ¦
------------------- |-----------------------|
| |
|----------------| ¦ FOR w из Г(v,-) DO ¦->
| | | |
Оператор ¦Г(v,-) => STACK ¦ означает |------+----------------|
| |
|----------------| |----v-------| ¦
| | |
(запись в стек всего содержимого Г(v,-) ) ¦ w => STACK+>---
| |
|------------|
Примеры использования обхода:- решение задачи методом деления на части
- разузлование сверху
- стратегия "разделяй и властвуй" (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).
Обход дерева вглубь в обратном порядке - начиная с концевых вершин.
4 - 5 - 1 - 6 - 8 - 7 - 2 - 3 - 0 потребует другой организации рекурсивной процедуры BACK(v)
да --------------------->------------------¬
------+------¬ ----------------------¬ ---V---¬ ---------¬
->¦Г(v,-) ПУСТО ¦->¦ FOR w из Г(v,-) DO ¦->¦USE(v) ¦-->¦v<=STACK ¦-->
-------------нет ------+---------------- -------- ----------
-----v-----¬ ¦
¦ BACK(w) ¦->-
------------
Обращение для запуска BACK(v0). Hерекурсивная версия этого обхода
реализуется аналогичным образом с использованием стека.
Примеры использования обхода:- анализ игр с полной информацией,
- разузлование снизу,
- динамическое программирование.
Обход дерева вширь (сначала уровень 0, затем 1, и т.д.)
в нашем случае: 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8потребует использования уже не стека, а очереди QUEUE
---------¬ --------------------------¬
--->¦v=>QUEUE ¦-->¦WHILE QUEUE # ПУСТО DO ¦-------->
---------- ----------+----------------
---------v--------¬ ¦
¦ w<=QUEUE ¦ ¦
¦ USE(w) ¦>--
¦ Г(w,-) => QUEUE ¦
-------------------
Вверх по странице, к оглавлению и навигации.