ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

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:
function createTree(container, tree) {
    if ( !container || !tree ) return;
    if ( Object.entries(tree).length == 0 ) return;
    
    let memory = [];            // память (стек) (в начале пуста)
    let cur_ent = [null, tree]; // текущая ссылка (в начале равна ссылке на корень дерева)
    let lastNodeVisited;        // последний обработанный узел на данный момент
    
    // цикл перебора узлов
    //     закончить цикл, как только память (стек) опустеет
    //     и текущая ссылка перестанет указывать на узел дерева
    while ( memory.length > 0 || cur_ent ) {
        
        // если текущая ссылка указывает на узел дерева, заглубляемся до листа
        // (итерация заглубления)
        if ( cur_ent ) {
                                    // обернуть данные в HTML-элемент li
            let li = document.createElement("li");
            if (cur_ent[0]) {
                li.append(cur_ent[0]);
                cur_ent[0] = li;
            }                       // создать HTML-элемент ul
            cur_ent.push( document.createElement("ul") );
            memory.push( cur_ent ); // поместить ссылку в память (стек)
                                    // перейти к левому потомку
            if ( Object.entries(cur_ent[1]).length > 0 ) {
                cur_ent = Object.entries(cur_ent[1])[0]; // потомок есть
            } else { cur_ent = null; }                   // потомка нет

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

                // если существует ветка правее, переходим по ней
                if ( i < Object.entries(peekNode[1]).length - 1 ) {
                    cur_ent = Object.entries(peekNode[1])[i + 1]; }
                // иначе (у узла на предыдущей итерации все потомки обработаны)
                else {
                                                    // ...обработка данных узла...
                                                    // помещаем текущий ul в текущий li
                    if (peekNode[0]) peekNode[0].append( peekNode[2] );
                                                    // помещаем li в вышестоящий ul
                    if (peekNode[0] && (memory.length - 2) >= 0) {
                        memory[memory.length - 2][2].append( peekNode[0] );
                    }
                    lastNodeVisited = memory.pop(); // убираем узел из памяти и запоминаем его
                }

            // если узел на предыдущей итерации был листом
            } else {
                                                // ...обработка данных узла...
                                                // помещаем li в вышестоящий ul
                if (peekNode[0] && (memory.length - 2) >= 0) {
                    memory[memory.length - 2][2].append( peekNode[0] );
                }
                lastNodeVisited = memory.pop(); // убираем узел из памяти и запоминаем его
            }
        }
    }
    
    // добавляем самый верхний ul в заданный контейнер
    container.append( lastNodeVisited[2] );
}

Я потестировал этот код на разных входящих данных. Всё работает.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments