Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


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

Поиск:
Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел. т.е. узел стоящий после данного при выбранном порядке обхода.
Существует несколько принципиально разных способов обхода дерева:
Обход в прямом порядке

Каждый узел посещается до того, как посещены его потомки.

Для корня дерева рекурсивно вызывается следующая процедура:

Код

Посетить узел
Обойти левое поддерево
Обойти правое поддерево


Примеры использования обхода:

    * решение задачи методом деления на части
    * разузлование сверху
    * стратегия "разделяй и властвуй" (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).

Симметричный обход

Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Код

Обойти левое поддерево
Посетить узел
Обойти правое поддерево


Обход в обратном порядке

Узлы посещаются 'снизу вверх'.

Для корня дерева рекурсивно вызывается следующая процедура:

Код

Обойти левое поддерево
Обойти правое поддерево
Посетить узел


Примеры использования обхода:

    * анализ игр с полной информацией
    * разузлование снизу
    * динамическое программирование

Обход в ширину

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.

Для реализации используется структура queue - очередь с методами

    * enqueue - поставить в очередь
    * dequeue - взять из очереди
    * empty - возвращает TRUE, если очередь пуста, иначе - FALSE

Код

q.enqueue(root);        // корень в очередь
while (! q.empty) {
  x = q.dequeue();
  visit x;              // посетить x
  if (! x.left.empty)   // x.left - левое поддерево
    q.enqueue(x.left);
  if (! x.right.empty)  // x.right - правое поддерево
    q.enqueue(x.right);
}



Рекурсивные обходы можно, очевидно, организовать и с помощью стека, 'развернув' рекурсию.
Сайт: ishodniki.ru






Просмотров: 4591

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную