June 4th, 2021

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

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

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

Я постараюсь реализовать на JavaScript обход дерева в глубину без рекурсии. На развилках при выборе пути приоритет будем отдавать правой (с позиции читателя, наблюдателя) ветви (ссылке).

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


На этой иллюстрации сверху изображено дерево, рядом с которым нарисованы разноцветные линии (линии заглублений) со стрелками, показывающие порядок обхода дерева в глубину выбранным нами выше способом. Внизу эти же линии со стрелками и соответствующие им узлы выстроены в линию в том порядке, в котором производится обход узлов дерева. Каждая линия (из разноцветных) начинается в развилке дерева (кроме первой, которая начинается со ссылки на корневой узел) и заканчивается концевым узлом (листом дерева).

В предыдущем посте я писал, что для обхода дерева в глубину в качестве «памяти» используют стек. Посмотрим, как при обходе дерева в глубину меняется содержимое стека. В стеке будем сохранять ссылки на узлы из развилок дерева. Ссылку на узел я буду обозначать так: {n}. К примеру, обозначение ссылки на корневой узел дерева будет таким: {1}.

Запомним ссылку на наше дерево, которая является ссылкой на корень этого дерева:

стек: {1}

Начнем обход дерева. Извлечем ссылку из памяти, перейдем в узел по ссылке. Мы оказались в узле 1. Далее путь разветвляется. Мы пойдем по правой ветке, то есть по ссылке {2}, а левую ветку, то есть ссылку {5} запомним в «памяти»:

стек: {5}

Мы оказались в узле 2. Тут путь разветвляется. Мы пойдем по правой ветке, то есть по ссылке {3}, а левую ветку, то есть ссылку {4} запомним в «памяти»:

стек: {5}, {4}

Мы оказались в узле 3. Это один из концевых узлов дерева (лист дерева), глубже здесь пройти уже нельзя. Проход красной линии (см. иллюстрацию выше) закончен. Для того, чтобы продолжить обход дерева, вернемся к последней развилке. Для этого извлечем последнюю ссылку из стека. Это ссылка {4}. Перейдем в узел по этой ссылке.

стек: {5}

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

И так далее.

Давайте посмотрим ход изменения состояния стека с самого начала и до самого конца обхода дерева с иллюстрации выше. Теперь каждое состояние стека изобразим вертикально, чтобы всё было компактно (состояния тут идут слева направо: первое состояние, второе состояние и так далее):
              {4}         {7}       {9}
.. {1} .. {5} {5} {5} .. {10} {10} {10} {10} ..
Состояние стека, в котором он пуст, тут изображено двоеточием. Всего тут изображено 12 различных состояний стека во время обхода нашего дерева.

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

Каким должно быть условие окончания внешнего цикла? Во внешнем цикле должна происходить работа с «памятью» (стеком). По идее, внешний цикл должен закончиться, когда стек опустеет. Но как мы видим выше, в нашем примере стек пустел четырежды. В первый раз стек был пуст до начала обхода дерева, поэтому это состояние не будем учитывать. Во второй, третий и четвертый разы стек становился пуст после успешного извлечения из него информации о последней развилке (ссылке). Но у нас в руках уже была только что извлеченная ссылка для продолжения обхода дерева. Вот после обработки узла 10, если бы мы попытались продолжить обход дерева и попытались бы извлечь из «памяти» еще какую-либо информацию о развилках дерева, стек (естественно) оказался бы пуст, а это и стало бы сигналом к окончанию цикла.

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

Возьмем для тестирования будущей функции обхода дерева реализацию на JavaScript нашего дерева, написанную в одном из моих предыдущих постов:
let tree = {
    data: 1,
    refs: [{
        data: 5,
        refs: [{ data: 10 }, {
            data: 7,
            refs: [{ data: 9 }, { data: 8 }]
        }, { data: 6 }]
    }, {
        data: 2,
        refs: [{ data: 4 }, { data: 3 }]
    }]
};
Только в данном случае ссылки, находящиеся в начале массива ссылок refs, мы будем считать левыми, а ссылки, находящиеся в конце массива refs — правыми.

Пишем на JavaScript функцию обхода дерева в глубину без рекурсии:
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];
        }
    }
}

Запуск обхода дерева:
traversal(tree);

В консоли из инструментов разработчика (в браузере) в результате должно быть выведено 10 строк, на каждой строке — данные (в данном случае — целое число) отдельного узла дерева. В данном случае — числа 1, 2, 3, ..., 10.

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

Начало:
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 в упомянутом выше стеке вызовов. То есть всю грязную работу делает движок, а программист наслаждается жизнью.