Как фильтровать дерево, сохраняя родительские узлы?

Основная концепция

Фильтрация дерева с сохранением родительских узлов — это задача, которая часто возникает при работе с иерархическими данными, такими как файловые системы, меню навигации или организационные структуры. Цель состоит в том, чтобы отфильтровать узлы по определенному критерию, но при этом сохранить все родительские узлы, ведущие к отфильтрованным элементам. Это необходимо для того, чтобы пользователь видел полный путь к найденным данным и мог понять их контекст.

Как это работает

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

Пример реализации на JavaScript

function filterTree(tree, predicate) {
  return tree.reduce((acc, node) => {
    const children = node.children ? filterTree(node.children, predicate) : [];
    if (predicate(node) || children.length > 0) {
      acc.push({ ...node, children });
    }
    return acc;
  }, []);
}

// Пример использования
const tree = [
  { id: 1, name: 'Documents', children: [
    { id: 2, name: 'Work', children: [
      { id: 3, name: 'Report.pdf' },
      { id: 4, name: 'Notes.txt' }
    ]},
    { id: 5, name: 'Photos', children: [
      { id: 6, name: 'Vacation.jpg' }
    ]}
  ]}
];

const filtered = filterTree(tree, node => node.name.includes('Report'));
console.log(filtered);
// Вывод: [{ id: 1, name: 'Documents', children: [{ id: 2, name: 'Work', children: [{ id: 3, name: 'Report.pdf' }] }] }]

Где применяется

• Поиск в файловых менеджерах
• Фильтрация категорий в интернет-магазинах
• Навигационные меню с поиском
• Организационные диаграммы

Вывод

Фильтрация дерева с сохранением родительских узлов — это мощный инструмент для работы с иерархическими данными. Она позволяет пользователям быстро находить нужную информацию, не теряя из виду её контекст. Этот подход особенно полезен в интерфейсах, где важна навигация по вложенным структурам, и его реализация требует понимания рекурсии и работы с деревьями.