Древовидные структуры встречаются в разных областях: генеалогическое древо, файловая система и т.д. В этом уроке мы познакомимся с деревом разметки HTML, которое постоянно встречается в веб-разработке.
<html>
<body>
<h1>Сообщество</h1>
<p>Общение между пользователями Хекслета</p>
<hr>
<input>
<div class='hexlet-community'>
<div class='text-xs-center'></div>
<div class='fa fa-spinner'></div>
</div>
</body>
</html>
Корнем является тег html. Важно отметить, что некоторые теги не могут иметь вложенные теги внутри себя, например, hr и input.
Попробуем описать это дерево в такой структуре, с которой было бы удобно работать. Первым шагом необходимо описать для каждого тега свойства, которыми он обладает. Как минимум можно выделить такие свойства: имя, тип, класс, дети. В реальности таких свойств бывает гораздо больше, но сейчас нам достаточно этих. Теперь опишем дерево html в этой структуре:
const htmlTree = {
name: 'html',
type: 'tag-internal',
children: [
{
name: 'body',
type: 'tag-internal',
children: [
{
name: 'h1',
type: 'tag-internal',
children: [
{
type: 'text',
content: 'Сообщество',
},
],
},
{
name: 'p',
type: 'tag-internal',
children: [
{
type: 'text',
content: 'Общение между пользователями Хекслета',
},
],
},
{
name: 'hr',
type: 'tag-leaf',
},
{
name: 'input',
type: 'tag-leaf',
},
{
name: 'div',
type: 'tag-internal',
className: 'hexlet-community',
children: [
{
name: 'div',
type: 'tag-internal',
className: 'text-xs-center',
children: [],
},
{
name: 'div',
type: 'tag-internal',
className: 'fa fa-spinner',
children: [],
},
],
},
],
},
],
};
Главным свойством в каждом узле является тип узла. В нашем дереве есть теги и текст. Текст может быть вложен в тег, то есть может быть потомком. Поэтому текст является листовым узлом. Также у нас есть некоторые теги, которые являются листовыми узлами. Поэтому для тегов выделено два типа: tag-internal
— внутренние узлы, это теги, которые могут иметь детей; tag-leaf
— листовые узлы, это теги, которые не могут иметь детей. Итак, для описания нашего дерева html достаточно определить три типа узлов:
tag-internal
- теги, которые могут иметь детей, внутренний узелtag-leaf
- теги, которые не могут иметь детей, листовой узелtext
- простой текст, листовой узел
Теперь мы можем работать с нашим деревом. Например, отфильтруем все пустые теги. Для этого прежде всего надо определить, как фильтровать каждый тип. Каждый тип фильтруется по-своему:
tag-internal
- если нет детей или все дети пустые, значит и родитель пустойtag-leaf
- не может иметь детей, такой тег всегда выводитсяtext
- текстовый узел не может содержать детей, вместо этого он может содержать текстовый контент, поэтому фильтруем по пустому контенту
Функция фильтрации будет выглядеть следующим образом:
const filterEmpty = (tree) => {
const filtered = tree.children
.map((node) => {
// Перед фильтрацией отфильтровываем всех потомков
if (node.type === 'tag-internal') {
// Тут самый важный момент. Рекурсивно вызываем функцию фильтрации.
// Дальнейшая работа не завершится, пока функция фильтрации не отфильтрует вложенные пустые узлы.
return filterEmpty(node);
}
return node;
})
.filter((node) => {
const { type } = node;
// Каждый тип фильтруется по-своему, удобно для этого использовать switch
switch (type) {
case 'tag-internal': {
// К этому моменту в текущем узле отфильтрованы потомки (остались только те, которые имеют своих детей)
const { children } = node;
// Проверяем текущий узел, если он не пустой, возвращаем true (узел остается)
return children.length > 0;
}
case 'tag-leaf':
// Листовые узлы всегда выводятся
return true;
case 'text': {
const { content } = node;
// Для текстовых узлов просто проверяем существование контента,
return !!content; // Для однозначности приводим значение к булевому типу
}
}
});
return { ...tree, children: filtered };
};
Фильтр в качестве параметра принимает узел с типом tag-internal
и обрабатывает вложенные в него элементы. Вначале проходимся по всем потомкам и у всех, с типом tag-internal
, фильтруем также вложенные элементы с помощью нашей же функции (рекурсия). Далее вызывается метод filter()
, в нём каждый тип уже фильтруется по той логике, которую мы определили.
После фильтрации получим такое дерево:
{
name: 'html',
type: 'tag-internal',
children: [
{
name: 'body',
type: 'tag-internal',
children: [
{
name: 'h1',
type: 'tag-internal',
children: [
{
name: '',
type: 'text',
content: 'Сообщество',
},
],
},
{
name: 'p',
type: 'tag-internal',
children: [
{
name: '',
type: 'text',
content: 'Общение между пользователями Хекслета',
},
],
},
{
name: 'hr',
type: 'tag-leaf',
},
{
name: 'input',
type: 'tag-leaf',
},
],
},
],
};
Это дерево не содержит элемент div
с классом hexlet-community
, даже несмотря на то, что оно содержало другие элементы. Это произошло потому, что перед фильтрацией родителя были отфильтрованы его пустые потомки. Теперь можно собрать дерево в строку:
// Для удобства определим отдельную функцию для формирования вывода класса
const buildClass = (node) => node.className ? ` class=${node.className}` : '';
// Основная функция для сборки страницы
const buildHtml = (node) => {
const { type, name } = node;
// Каждый тип формируется по-своему, как и в фильтрации используем switch
switch (type) {
case 'tag-internal': {
// Этот тип может иметь детей, формируем вывод детей
const childrenView = node.children.map(buildHtml).join('');
// Собираем всё, вместе с родительским узлом
return `<${name}${buildClass(node)}>${childrenView}</${name}>`;
}
case 'tag-leaf':
// Листовые узлы формируются просто
return `<${name}${buildClass(node)}>`;
case 'text':
// В текстовых узлах выводится сам контент
return node.content;
}
};
// Получаем отфильтрованное дерево
const filteredTree = filterEmpty(htmlTree);
// Формируем результат
const html = buildHtml(filteredTree);
console.log(html); // => <html><body><h1>Сообщество</h1><p>Общение между пользователями Хекслета</p><hr><input></body></html>
Если расставить отступы и каждый тег на новой строке, то на выходе получаем html без пустых тегов:
<html>
<body>
<h1>Сообщество</h1>
<p>Общение между пользователями Хекслета</p>
<hr>
<input>
</body>
</html>
https://replit.com/@hexlet/js-trees-html
Код для обработки деревьев выглядит довольно лаконичным. Это - следствие удобной структуры для представления дерева html. Выделив в этом дереве несколько типов узлов, остаётся только описать логику для каждого типа. Любой внутренний узел является таким же деревом, поэтому обрабатывается рекурсивно этой же функцией. Правильное представление структуры значительно упрощает обработку дерева.
Дополнительные материалы
- Знакомство с HTML
- Для чего два восклицательных знака перед выражением?
- Figma plugin API: diving into advanced algorithms & data structures
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.