ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Category:

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

Начало:
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.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments