June 6th, 2021

Обход дерева в глубину, алгоритмы NLR из википедии

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

Когда неделю назад я начинал писать эти посты, то, конечно, сначала прочёл соответствующие статьи в википедии, посвящённые обходу дерева:

https://ru.wikipedia.org/wiki/Обход_дерева
https://en.wikipedia.org/wiki/Tree_traversal

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

Немного теории про обозначения

В этих статьях авторы используют для некоторых алгоритмов обхода дерева в глубину специальные обозначения: латинские буквы N, L и R. Латинской буквой N обозначается операция обработки данных одного (любого) узла дерева. Под этой буквой подразумевается английское слово «node» (по-русски «узел»). Латинские буквы L и R, соответственно, являются сокращениями английских слов «left» (по-русски «левый») и «right» (по-русский «правый»). Буквами L и R у бинарных (двоичных) деревьев обозначаются для одного (любого) узла дерева, соответственно, операция перехода к левому потомку узла и операция перехода к правому потомку узла.

Один узел дерева тут берётся потому, что дерево — это рекурсивно определяемая структура данных, поэтому рассматривать более одного узла не требуется, об этом уже было рассказано подробно в предыдущих постах.

Таким образом, этими тремя латинскими буквами можно обозначить шесть разных алгоритмов обхода бинарного (двоичного) дерева в глубину:

NLR, LNR, LRN
NRL, RNL, RLN

Такое название говорит о порядке выполнения операций в одном (любом) узле дерева при обходе дерева в глубину.

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

То есть местоположение буквы N в тройке букв названия алгоритма говорит о том, когда будут обработаны данные одного (любого) из узлов дерева:

NLR, NRL — до операций перехода к потомкам (по-английски «pre-order», по-русски «прямой обход»);
LNR, RNL — между операциями перехода к потомкам (по-английски «in-order», по-русски «центрированный обход»);
LRN, RLN — после операций перехода к потомкам (по-английски «post-order», по-русски «обратный обход»).

В отношении букв L и R имеет значение их местоположение относительно друг друга, оно говорит о приоритете обхода потомков одного (любого) узла дерева:

NLR, LNR, LRN — потомки узла обходятся слева направо;
NRL, RNL, RLN — потомки узла обходятся справа налево.

В английском языке к названиям алгоритмов обхода дерева в глубину с приоритетом обхода потомков узла справа налево добавляется слово «reverse»:

NLR, LNR, LRN — pre-order, in-order, post-order;
NRL, RNL, RLN — reverse pre-order, reverse in-order, reverse post-order.

Кстати, я не стал бы для слова «reverse» в данном контексте брать в качестве перевода на русский слово «обратный», потому что в случае «reverse post-order» получится «обратный обратный обход», что будет неправильно. Правильным переводом на русский в данном случае, думаю, будет «обратный обход с приоритетом обхода потомков справа налево».

В принципе, эти трехбуквенные названия некоторых алгоритмов обхода дерева в глубину можно перенести с бинарных (двоичных) деревьев на общий случай, когда у любого узла дерева может быть больше двух потомков. При этом смысл буквы N в названии перечисленных выше алгоритмов не изменится, а вот буквы L и R теперь будут обозначать не конкретно двух потомков одного (любого) узла бинарного (двоичного) дерева, а просто — порядок обхода потомков — слева направо (LR) или справа налево (RL). При этом под алгоритмом LNR и под алгоритмом RNL (под каждым из них) теперь будет подразумеваться целое множество алгоритмов, потому что промежутков между ветками к потомкам узла станет несколько.

Реализации алгоритмов, которые я написал ранее

В предыдущих постах я написал две реализации обхода дерева в глубину на языке JavaScript: без рекурсии, с рекурсией.

Алгоритм обхода дерева в глубину с помощью рекурсии часто называют рекурсивным, а алгоритм обхода дерева в глубину без рекурсии — итеративным (по-английски «iterative»), то есть с помощью итераций, с помощью цикла.

Реализации алгоритмов NLR из википедии

В упомянутых выше статьях википедии в разделе «Имплементация» (по-английски «Implementations») приведено несколько реализаций на псевдокоде (вики) алгоритмов обхода дерева. Шесть первых из них — это алгоритмы обхода дерева в глубину. Из них первая пара — это алгоритмы NLR (рекурсивный и итеративный), затем — пара алгоритмов LNR (рекурсивный и итеративный) и пара алгоритмов LRN (рекурсивный и итеративный).

Вот пара реализаций алгоритмов NLR оттуда:

1) Обход бинарного (двоичного) дерева в глубину, рекурсивный алгоритм, NLR (прямой обход с приоритетом обхода потомков слева направо), реализация на псевдокоде, цитата:
preorder(node)
    if (node == null)
        return
    visit(node)
    preorder(node.left)
    preorder(node.right)

2) Обход бинарного (двоичного) дерева в глубину, итеративный алгоритм, NLR (прямой обход с приоритетом обхода потомков слева направо), реализация на псевдокоде, цитата:
iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    //правый потомок заносится первым, так что левый потомок обрабатывается первым
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

Упрощение моей реализации

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

Кроме этого, я писал реализации с приоритетом обхода потомков справа налево, а в википедии в процитированных реализациях — слева направо. То есть моя пара реализаций (рекурсивная и итеративная) соответствует алгоритмам NRL, а не NLR.

С учетом этих двух отличий я с помощью реализации из википедии смог упростить и улучшить свою реализацию (в частности, вместо двух циклов while теперь один):

Обход дерева (не только двоичного) в глубину, итеративный алгоритм, NRL (прямой обход с приоритетом обхода потомков справа налево), реализация на языке JavaScript:
function traversal(tree) {
    if ( !tree ) return; // проверка ссылки на корень дерева
    let memory = [tree]; // память (стек)
                         // в начале память содержит ссылку на корень заданного дерева
    // цикл перебора узлов
    // закончить цикл, если не получается извлечь ссылку на узел из памяти (стека)
    while ( memory.length > 0 ) {
        let cur_ref = memory.pop(); // извлечь ссылку на узел из памяти (стека)
        
        // ...обработка данных узла...
        console.log(cur_ref.data); // просто выводим в консоль

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

Мой рекурсивный вариант реализации этого алгоритма переделывать не понадобилось (там сложно ошибиться :).