ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Обход дерева в глубину с рекурсией

Начало:
1. Учебник по JavaScript: структуры данных
2. Учебник по JavaScript, структура данных «дерево»
3. Что такое обход дерева
4. Обход дерева в глубину без рекурсии

При первом знакомстве с понятием рекурсии (вики) при изучении программирования она может показаться сложной и неизвестно зачем придуманной (по крайней мере, у меня так было).

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

Почему дерево — это рекурсивно определяемая структура данных? Потому что эта структура данных повторяет саму себя в своих частях. Об этом можно почитать в подразделе 6.1 «Рекурсия и стек» учебника по JavaScript.

У рекурсивного способа реализации алгоритма обхода дерева в глубину, однако, есть недостаток. При слишком больших деревьях этот способ может вызвать переполнение стека вызовов (вики). Поэтому, к примеру, для обработки небольших менюшек древовидной структуры удобнее использовать обход дерева с рекурсией, а вот, к примеру, для обработки некоего большого HTML-документа (или XML-документа), а точнее, элементов его DOM-дерева (про это понятие можно почитать в подразделе 1.2 «DOM-дерево» второй части упомянутого выше учебника), возможно, будет целесообразнее использовать обход дерева без рекурсии, чтобы не нарваться на переполнение стека вызовов.

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

Рассмотрим при обходе дерева посещение любого одного узла. При рекурсии сначала следует определить условие завершения работы функции. Этим условием будем считать установление факта, что данный узел является листом дерева. Если узел не является листом дерева, то следует последовательно (в цикле) перейти (в нашем случае, как мы договорились в предыдущем посте, с приоритетом справа налево) по веткам на следующий, нижний, уровень дерева и запустить для каждой из этих веток (ссылок) эту же функцию (это и есть рекурсия).

Пишем код на языке JavaScript:
function traversal(tree) {
    // ...обработка данных узла...
    console.log(tree.data); // просто выводим в консоль
    
    // если это лист, завершить функцию
    if ( !tree.refs ) return;
    
    // последовательно справа налево обходим ветви, ведущие из текущего узла
    for (let i = tree.refs.length - 1; i >= 0; i--) {
        traversal( tree.refs[i] ); // рекурсия
    }
}

Для проверки работы этой функции можно взять тестовое дерево из предыдущего поста. Запуск функции там тоже был показан, а результат работы скрипта должен быть таким же, как в прошлом посте.

А теперь сравните с вариантом реализации обхода дерева без рекурсии, продемонстрированном в прошлом посте:
function traversal(tree) {
    let cur_ref;         // текущая ссылка
    let memory = [tree]; // память (стек)
                         // в начале память содержит ссылку на корень заданного дерева

    // внешний цикл, перебирающий линии заглублений
    // закончить цикл, если не получается извлечь ссылку из памяти (стека)
    while ( cur_ref = memory.pop() ) {

        // внутренний цикл обхода каждой линии заглубления дерева до листа
        while ( true ) {
            // ...обработка данных узла...
            console.log(cur_ref.data); // просто выводим в консоль

            // если это лист, выйти из цикла
            if ( !cur_ref.refs ) break;

            // помещаем ветви, ведущие налево, в память (стек)
            for (let i = 0; i < cur_ref.refs.length - 1; i++) {
                memory.push( cur_ref.refs[i] );
            }
            // переходим по ветви, ведущей направо
            cur_ref = cur_ref.refs[cur_ref.refs.length - 1];
        }
    }
}

Результат налицо. Понятно, какой вариант проще написать.

В случае с рекурсией запоминание ветвей на развилках дерева и разных промежуточных данных выполняет движок JavaScript в упомянутом выше стеке вызовов. То есть всю грязную работу делает движок, а программист наслаждается жизнью.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments