ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Обход дерева в глубину, обратный обход (от листьев)

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

Продолжаю обзор статей об обходе дерева из википедии:

https://ru.wikipedia.org/wiki/Обход_дерева (русскоязычная)
https://en.wikipedia.org/wiki/Tree_traversal (англоязычная)

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


Алгоритмы обхода дерева в глубину NLR, LNR и LRN

Про значение трехбуквенных названий алгоритмов обхода дерева в глубину было подробно рассказано в предыдущем посте.

Штриховой линией, начало которой отмечено маленьким черным квадратиком, а конец — стрелкой, обозначается цикл обхода узлов дерева. На каждой из этих трех иллюстраций обход узлов дерева производится с приоритетом обхода потомков слева направо, поэтому штриховая линия от корневого узла F сначала идёт против часовой стрелки.

Жирная черная точка на окружности каждого узла обозначает операцию обработки данных этого узла (латинская буква N в названии каждого алгоритма). На первой иллюстрации все эти точки изображены на левой стороне окружности каждого узла. На второй иллюстрации все эти точки изображены на нижней части окружности каждого узла. На третьей иллюстрации все эти точки изображены на правой стороне окружности каждого узла. Таким образом обозначается порядок выполнения операции N (обработка данных узла) относительно выполнения операций L (переход к левому потомку) и R (переход к правому потомку).

Как это понимать? Например, рассмотрим обход дерева (алгоритм NLR) на первой слева иллюстрации. Сначала штриховая линия проходит мимо жирной черной точки корневого узла F, то есть происходит обработка данных корневого узла F. Затем штриховая линия проходит по левой ветке от корневого узла F, то есть выполняется операция перехода к левому потомку узла F, этим потомком оказывается узел B. Штриховая линия проходит мимо жирной черной точки узла B, то есть выполняется операция обработки данных узла B. Далее штриховая линия отправляется к левому потомку узла B, которым оказывается узел A. И так далее.

Предположим, операция N (обработка данных узла, обозначенная на иллюстрациях жирной черной точкой на окружностях узлов) будет состоять в выводе данных узла на экран. Тогда узлы будут выведены на экран в следующем порядке (порядок вывода будет разным у каждого из алгоритмов обхода дерева в глубину):
NLR: F, B, A, D, C, E, G, I, H
LNR: A, B, C, D, E, F, G, H, I
LRN: A, C, E, D, B, H, I, G, F

* * *

В англоязычной версии статьи (см. ссылку выше) из википедии про обход дерева эти три иллюстрации объединены в одну иллюстрацию, на которой операции N (обработка данных узла) обозначены на окружностях узлов жирными точками трех разных цветов: красным (для алгоритма NLR), зеленым (для алгоритма LNR) и синим (для алгоритма LRN).

Если при обходе вышеприведенного бинарного (двоичного) дерева выполнять операцию N (обработка данных узла) трижды для каждого узла (перед переходом к потомкам, между переходом к левому потомку и переходом к правому потомку, после переходов к потомкам), то получим такой результат (обработкой данных узла будем считать простой вывод данных узла на экран):
NLNRN: F, B, A, A, A, B, D, C, C, C, D, E, E, E, D, B, F, G, G, I, H, H, H, I, I, G, F

* * *

Если принять при обходе узлов приоритет обхода потомков справа налево (в википедии эти алгоритмы не проиллюстрированы), то штриховая линия будет на иллюстрациях проходить так же, только у нее поменяются начало и конец (сначала штриховая линия будет выходить из корневого узла F по часовой стрелке). Жирную черную точку, обозначающую операцию N (обработка данных узла), при этом на первой иллюстрации (алгоритм NRL) надо будет изображать на правой стороне окружности каждого узла, для алгоритма RNL — на нижней части окружности каждого узла, а для алгоритма RLN — на левой стороне окружности каждого узла.

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

Прямой, центрированный, обратный обходы (с приоритетом обхода потомков слева направо):
NLR: F, B, A, D, C, E, G, I, H
LNR: A, B, C, D, E, F, G, H, I
LRN: A, C, E, D, B, H, I, G, F
Прямой, центрированный, обратный обходы (с приоритетом обхода потомков справа налево):
NRL: F, G, I, H, B, D, E, C, A
RNL: I, H, G, F, E, D, C, B, A
RLN: H, I, G, E, C, D, A, B, F

* * *

Меня тут заинтересовали алгоритмы обратного обхода дерева в глубину. Выше показано два таких алгоритма для бинарных (двоичных) деревьев: LRN и RLN. Мне они интересны тем, что в их случае выполнение операций N (обработка данных узла) для узлов начинается не с корневого узла и по нисходящей, а, наоборот, от концевых узлов (листьев) дерева и по восходящей к корневому узлу.

Для чего может понадобиться обратный обход? Предположим, есть данные, сохраненные в древовидной структуре данных. Требуется написать скрипт на языке JavaScript, который выводит эти данные на HTML-страницу с помощью элементов ul и li. Разрешается использовать только метод append (вставка заданного элемента в конец указанного элемента) для добавления готовых элементов на HTML-страницу.

Простой HTML-пример для дерева из трех узлов (корень и два листа):
<ul>
  <li>Корень
    <ul>
      <li>Левый потомок</li>
      <li>Правый потомок</li>
    </ul>
  </li>
</ul>
В браузере это выглядит так:
  • Корень
    • Левый потомок
    • Правый потомок

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

* * *

Реализации обратного обхода дерева в глубину из статей википедии (ссылки в начале поста):

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

2) Обход бинарного (двоичного) дерева в глубину, итеративный алгоритм, LRN (обратный обход с приоритетом обхода потомков слева направо), реализация на псевдокоде, цитата (часть комментариев вставлена мной):
iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left            // заглубление
    else
      peekNode ← s.peek()
      // если правый потомок существует и обход пришёл из левого потомка, двигаемся вправо
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right     // переход по неисследованной ветке
      else
        visit(peekNode)
        lastNodeVisited ← s.pop() // возвращение на уровень вверх

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

Во-вторых, на каждой итерации цикла while (цикл перебора узлов), как видно по веткам if и else, может произойти одно из трех событий — заглубление, переход по неисследованной ветке, возвращение на уровень вверх.

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

Мои реализации обратного обхода дерева в глубину:

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

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

    // цикл перебора узлов
    //     закончить цикл, как только память (стек) опустеет
    //     и текущая ссылка перестанет указывать на узел дерева
    while ( memory.length > 0 || cur_ref ) {

        // если текущая ссылка указывает на узел дерева, заглубляемся до листа (итерация заглубления)
        if ( cur_ref ) {
            memory.push( cur_ref ); // поместить ссылку в память (стек)
                                    // перейти к правому потомку
            if ( cur_ref.refs ) { cur_ref = cur_ref.refs[cur_ref.refs.length - 1]; // потомок есть
            } else { cur_ref = null; }                                             // потомка нет

        // если текущая ссылка не указывает на узел дерева (узел на предыдущей
        // итерации заглубления был листом или возвращаемся вверх)
        } else {
            let peekNode = memory[memory.length - 1]; // ссылка на узел в вершине стека
            
            // если узел на предыдущей итерации не был листом (возвращаемся вверх)
            if ( peekNode.refs ) {
                // ищем ветку, откуда вернулись
                let i;
                for (i = peekNode.refs.length - 1; i >= 0; i--) {
                    if ( peekNode.refs[i] == lastNodeVisited ) break;
                }
                
                // если существует ветка левее, переходим по ней
                if ( i > 0 ) { cur_ref = peekNode.refs[i - 1]; }
                else {
                    // иначе (у узла на предыдущей итерации все потомки обработаны)
                    console.log(peekNode.data);     // ...обработка данных узла... (вывод в консоль)
                    lastNodeVisited = memory.pop(); // убираем узел из памяти (стека) и запоминаем его
                }
            
            // если узел на предыдущей итерации был листом
            } else {
                console.log(peekNode.data);     // ...обработка данных узла... (вывод в консоль)
                lastNodeVisited = memory.pop(); // убираем узел из памяти (стека) и запоминаем его
            }
        }
    }
}

Дерево из десяти узлов для тестирования этого скрипта, заданное на языке JavaScript, можно взять в одном из предыдущих постов.

Вот оно на рисунке:

В консоль должны быть выведены для этого дерева следующие последовательности данных (чисел) узлов при прямом обходе в глубину с приоритетом обхода потомков справа налево (NRL) и при обратном обходе в глубину с приоритетом обхода потомков справа налево (RLN):
NRL: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
RLN: 3, 4, 2, 6, 8, 9, 7, 10, 5, 1
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments