ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

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

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

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

Данные о структуре дерева в задаче заданы на языке JavaScript так:
let data = {
  "Рыбы": {
    "форель": {},
    "лосось": {}
  },
  "Деревья": {
    "Огромные": {
      "секвойя": {},
      "дуб": {}
    },
    "Цветковые": {
      "яблоня": {},
      "магнолия": {}
    }
  }
};

Для себя я нарисовал эту структуру так:

Требуется написать функцию createTree(container, data), которая с помощью HTML-элементов ul и li создаст из структуры дерева data HTML-дерево и вставит его в заданный контейнер container, который является неким HTML-элементом на HTML-странице скрипта.

Например, HTML-элемент (контейнер) на HTML-странице скрипта может выглядеть так:
<div id="tree"></div>

Тогда вызов нашей функции может быть выполнен так:
let container = document.getElementById("tree");
createTree(container, data);

В результате работы нашей функции на HTML-странице с точки зрения HTML-элементов должно появиться следующее:
<div id="tree">
  <ul>
    <li>Рыбы
      <ul>
        <li>форель</li>
        <li>лосось</li>
      </ul>
    </li>
    <li>Деревья
      <ul>
        <li>Огромные
          <ul>
            <li>секвойя</li>
            <li>дуб</li>
          </ul>
        </li>
        <li>Цветковые
          <ul>
            <li>яблоня</li>
            <li>магнолия</li>
          </ul>
        </li>
      </ul>
    </li>
  </ul>
</div>
Что в браузере должно выглядеть так:
  • Рыбы
    • форель
    • лосось
  • Деревья
    • Огромные
      • секвойя
      • дуб
    • Цветковые
      • яблоня
      • магнолия

Решение. Итак, сначала я решил просто написать обход заданного дерева рекурсивным способом с выводом данных узлов дерева в консоль браузера. Для этого требуется выбрать один из алгоритмов обхода дерева.

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

Я выбрал обход дерева в глубину, потому что пока ещё не изучал подробно другие методы. Так как для добавления HTML-элементов я планирую использовать метод append (добавление в конец), то выбираю алгоритм обхода дерева в глубину с приоритетом обхода потомков слева направо. При этом я выбираю обратный обход дерева в глубину (от листьев), причину этого я описывал в предыдущем посте. Таким образом, наш алгоритм — LRN (об этих трехбуквенных аббревиатурах я писал в предыдущих постах).

После нескольких экспериментов у меня получился такой код:
function traversal(data) {
    for (const [text, ref] of Object.entries(data)) {
        traversal(ref);
        console.log(text);
    }
}

В случае, если в эту функцию передан пустой объект, она ничего не выведет, потому что цикл for ни разу не отработает из-за того, что выражение Object.entries(data) вернет пустой массив.

Обработку данных узла console.log(text); пришлось внести внутрь цикла из-за необычной технической организации заданного дерева. Обычно узел дерева содержит одну ячейку данных и множество ссылок на узлы-потомки. В рассматриваемой же задаче ячеек с данными в каждом узле дерева столько же, сколько и ссылок на узлы-потомки. Причём каждая ссылка на узла-потомка связана с одной из ячеек с данными.

Кстати, этот код можно из реализации алгоритма LRN переделать в реализации алгоритмов NLR (переставляя местами обработку ссылки traversal(ref); и обработку ячейки данных console.log(text);, меняем обратный обход на прямой и наоборот), RLN и NRL (изменяя порядок элементов в массиве Object.entries(data) на противоположный с помощью Object.entries(data).reverse(), мы меняем приоритет обхода потомков — вместо слева направо получаем справа налево и наоборот).

Для алгоритмов LRN (обратный обход) и NLR (прямой обход) для заданного в задаче дерева данные узлов этого дерева будут выведены в консоль браузера в следующем порядке:
LRN: форель, лосось, Рыбы, секвойя, дуб, Огромные, яблоня, магнолия, Цветковые, Деревья
NLR: Рыбы, форель, лосось, Деревья, Огромные, секвойя, дуб, Цветковые, яблоня, магнолия

Меняем название функции на нужное и добавляем ей первым аргументом переменную, содержащую HTML-контейнер:
function createTree(container, data) {
    for (const [text, ref] of Object.entries(data)) {
        let container2;
        createTree(container2, ref);
        console.log(text);
    }
}

Этот код, по сути, описывает обработку данных узлов дерева, являющихся потомками одного и того же родителя, на каждом уровне. Проанализировав HTML-дерево, которое мы должны получить, я заметил, что такие узлы (являющиеся потомками одного и того же родителя) там каждый раз помещаются в один и тот же HTML-элемент ul, который затем сам помещается в заданный контейнер. Значит, в начале нашей функции мы должны создавать HTML-элемент ul, затем помещать в него содержимое потомков, а в конце — помещать сам HTML-элемент ul в заданный контейнер. Меняем код:
function createTree(container, data) {
    let ul = document.createElement("ul");   // создаём <ul>

    for (const [text, ref] of Object.entries(data)) {
        let container2;
        createTree(container2, ref);
        console.log(text);

        ul.append(container2);               // помещаем в <ul> потомков
    }

    if ( Object.entries(data).length > 0 ) {
        container.append(ul);                // помещаем сам <ul> в заданный контейнер
    }
}
Нужно отметить, что при помещении HTML-элемента ul в заданный контейнер требуется условие — мы не хотим выводить этот элемент, если в нем нет потомков (в случае пустого объекта {}).

Проанализировав HTML-дерево, которое мы должны получить, я заметил, что в HTML-элемент ul могут быть вставлены только HTML-элементы li. Исходя из этого и исходя из строки ul.append(container2); вышеописанного кода можно понять, что container2 — это HTML-элемент li. Меняем код:
function createTree(container, data) {
    let ul = document.createElement("ul");   // создаём <ul>

    for (const [text, ref] of Object.entries(data)) {
        let li = document.createElement("li");
        createTree(li, ref);
        // console.log(text);

        ul.append(li);                       // помещаем в <ul> потомков
    }

    if ( Object.entries(data).length > 0 ) {
        container.append(ul);                // помещаем сам <ul> в заданный контейнер
    }
}

Осталось понять, в каком месте функции добавлять в HTML-элемент li данные (текст) узла дерева (проанализировав HTML-дерево, которое требуется получить, можно заметить, что текст добавляется только в HTML-элементы li).

И тут есть интересная деталь. Если добавление потомков в HTML-элементы ul происходит в порядке обратного обхода (выражение ul.append(li); находится после выражения createTree(li, ref);), то вывод данных (текста) узлов дерева должен выполняться (судя по HTML-дереву, которое мы должны получить) в порядке прямого обхода, то есть вывод текста должен находиться до выражения createTree(li, ref);. Меняем код:
function createTree(container, data) {
    let ul = document.createElement("ul");   // создаём <ul>

    for (const [text, ref] of Object.entries(data)) {
        let li = document.createElement("li");

        li.append(text);                     // выводим текст узла (прямой обход)
        createTree(li, ref);
        ul.append(li);                       // помещаем в <ul> потомков (обратный обход)
    }

    if ( Object.entries(data).length > 0 ) {
        container.append(ul);                // помещаем сам <ul> в заданный контейнер
    }
}

Это и есть решение обсуждаемой задачи.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments