Проблема на этой неделе связана со структурой данных, которую мы рассмотрели ранее, - деревьями. Посетите предыдущую статью здесь, чтобы узнать больше о бинарных деревьях и самостоятельно реализовать их на JavaScript! Дерево состоит из взаимосвязанных узлов, основными отношениями которых являются родительские узлы и дочерние узлы. Двоичные деревья очень популярны в информатике, это случай, когда родительские узлы могут иметь не более 2 дочерних узлов. Но будут случаи, когда тройные или четвертичные деревья более уместны. Важно помнить, что дерево - это структура данных, имеющая отношения родитель-потомок.
Проблемы программирования и проблемы в реальной жизни обычно вращаются вокруг эффективного обхода этих деревьев. Если вы не знакомы с некоторыми распространенными методами обхода графов DFS (поиск в глубину) и BFS (поиск в ширину), я бы посоветовал вам использовать этот ресурс для обзора.
Инвертирование двоичного дерева
Это классическая проблема: «Учитывая корень, инвертировать соответствующее двоичное дерево и вернуть корень».
Желаемый результат можно увидеть на диаграмме ниже:
Для этого решения я буду создавать двоичное дерево, соединяя узлы. Затем я создам функцию «print», которая также проходит по нашему дереву и возвращает массив значений узлов. Наконец, я создам функцию инвертирования, которая будет нести логику инвертирования нашего дерева.
Решением нашей проблемы является наша обратная функция. Он использует рекурсивный подход DFS, проходя вниз по уровням дерева перед выполнением подкачки на обратном пути. Настройка этой проблемы заняла большинство строк в нашем коде, но теперь вы можете повторно использовать код, сохранив его в файле или реализовав свой собственный класс!
Когда приведенный выше фрагмент выполняется на вашем локальном компьютере, результат должен выглядеть примерно так:
Спасибо, что нашли время обсудить со мной эту проблему на этой неделе! В ближайшие недели я расскажу о многих других проблемах, связанных с обходом деревьев!
