Алгоритми обробки дерев 22

Проходження дерев

Рекурсивні методи проходження дерев

Рекурсивне визначення бінарного дерева визначає цю структуру як корінь з двома піддеревами, які ідентифікуються полями лівого і правого вказівників в кореневому вузлі. Сила рекурсії проявляється разом з методами проходження. Кожен алгоритм проходження дерева виконує в вузлі три дії: заходить у вузол, рекурсивно спускається по лівому піддереву і по правому піддереву. Спустившись до піддерева, алгоритм визначає, що він знаходиться у вузлі, і може виконати ті ж три дії. Спуск припиняється після досягнення порожнього дерева (Вказівник == NULL). Різні алгоритми рекурсивного проходження відрізняються порядком, в якому вони виконують свої дії у вузлі. Ми розглянемо симетричний і зворотний методи, в яких спочатку здійснюється спуск по лівому піддереву, а потім по правому. Інші методи залишаємо вам в якості вправ.

Симетричний метод проходження дерева 23

Симетричний метод проходження починає свої дії у вузлі спуском по його лівому піддереву. Потім виконується друга дія – обробка даних у вузлі. Третя дія - рекурсивне проходження правого піддерева. У процесі рекурсивного спуску дії алгоритму повторюються в кожному новому вузлі.

Не нашли, что искали? Воспользуйтесь поиском: