June 16th, 2021

HTML-дерево из объекта, итеративный способ

Начало: HTML-дерево из объекта, рекурсивный способ.

Продолжаю решать задачу «Создайте дерево из объекта» к подразделу 1.7 «Изменение документа» второй части учебника по JavaScript.

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

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

Скелет этого решения выглядит так (и этот скелет, в принципе, останется неизменным вплоть до окончательного решения):
function traversal(tree) {

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

        // если текущая ссылка указывает на узел дерева, заглубляемся до листа
        // (итерация заглубления)
            // поместить ссылку в память (стек)
            // перейти к правому потомку
            
        // если текущая ссылка не указывает на узел дерева (узел на предыдущей
        // итерации заглубления был листом или возвращаемся вверх)

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

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

Третья сверху группа комментариев представляет собой обработку данных листа дерева.

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

Во второй и третьей группах комментариев происходит извлечение узлов дерева из памяти (стека) с помощью инструкции memory.pop() в порядке обратного обхода дерева.

Далее я стал изменять этот код.

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

В нашей же задаче узлом дерева является свойство объекта, то есть пара «ключ: значение», в которой «ключ» — это данные объекта, а «значение» — это ссылка на массив потомков. В случае листа «значение» является ссылкой на пустой массив потомков (то есть длина этого массива равна нулю). За корень дерева в нашей задаче я принял пару [null, tree], в которой «ключ» отсутствует (null), а «значение» равно переданному в нашу функцию параметру tree.

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

В-третьих, я поменял название нашей функции с traversal на createTree и добавил еще один входной параметр container (HTML-элемент, в который требуется вставить сконструированное HTML-дерево). Также я добавил несколько проверок входных параметров, вот кусок кода:
function createTree(container, tree) {
    if ( !container || !tree ) return;
    if ( Object.entries(tree).length == 0 ) return;
// ...
Еще я поменял название переменной cur_ref (текущая ссылка, ссылка на текущий узел) на cur_ent. По смыслу это та же самая текущая ссылка или ссылка на текущий узел, но так как массив ссылок на потомков мы будем теперь получать с помощью инструкции Object.entries(tree), то узел у нас будет, очевидно, по-английски именоваться «entry», следовательно, ссылка на текущий узел — «current entry» или cur_ent.

После этого я стал добавлять работу с HTML-элементами.

Каждый узел нашего дерева на данный момент является, как уже было сказано выше, парой значений или массивом из двух значений [данные, массив потомков]. После долгих раздумий и экспериментов я решил хранить HTML-элементы, относящиеся к конкретному узлу дерева, в этом же узле. HTML-элемент li связан с данными узла, а HTML-элемент ul связан с массивом потомков.

В-четвертых, при заглублении (см. первую группу комментариев в скелете решения в начале поста) я стал превращать каждый узел дерева из массива двух значений [данные, массив потомков] в массив трех значений [<li>данные</li>, массив потомков, <ul></ul>]. То есть я создаю HTML-элементы с помощью инструкции document.createElement(), после чего HTML-элемент ul помещаю в массив узла третьим элементом массива, а первый элемент массива (данные узла) делаю содержимым HTML-элемента li и уже HTML-элемент li с данными узла помещаю первым элементом массива.

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

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

В результате описанных манипуляций требуемое HTML-дерево в итоге должно сформироваться в HTML-элементе ul узла-корня дерева.

После выхода из цикла while у нас будет опустевшая память (стек) и пустая ссылка на текущий узел. Откуда же тогда взять итоговое сформированное HTML-дерево для вставки в заданный конейнер container? Но у нас ведь есть еще переменная lastNodeVisited (последний обработанный узел на данный момент)! Так как при обратном обходе дерева в глубину последним всегда обрабатывается корневой узел дерева, то после окончания цикла while переменная lastNodeVisited будет содержать корневой узел дерева. Берем из массива этого узла третий элемент [2] (это и будет искомый HTML-элемент ul) и добавляем его в заданный контейнер container:
container.append( lastNodeVisited[2] );

Вот, собственно, и всё.

Окончательный вариант кода на языке JavaScript:
Collapse )
Я потестировал этот код на разных входящих данных. Всё работает.