Условия задачи:
В программе реализована структура BinaryTreeNode, а также функция walk_tree, которая обходит бинарное дерево по уровням, при этом записывая в логи номер посещаемого узла и номера его потомков.
Напишите функцию restore_tree, которая принимает на вход путь до файла с логами в виде строки, а возвращает корень восстановленного бинарного дерева.
Гарантируется, что все значения, хранящиеся в бинарном дереве, уникальны.
root = BinaryTreeNode(1)
root.left = node2 = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
node2.left = BinaryTreeNode(4)
node2.right = BinaryTreeNode(5)
Советы и рекомендации
- Создайте словарь {node_value: node_object}. Это позволит быстро получить нужный узел по его значению.
- Существует два основных алгоритма обхода графа: поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Обращаю внимание: у нас операции с БИНАРНЫМ ДЕРЕВОМ, а советы и рекомендации по поводу графов!!! Видимо это сделано специально для студентов - чтобы жизнь сказкой не казалась! Я читал читал и понял - что не о том читаю... Или я вообще ничего не понял...
Сказать что эта задача меня испугала - это ничего не сказать. Я много раз встречал слово "графы" и ветвления и узлы. Но я совершенно ничего не понимаю в этом. Это такая подлянка задавать задачу о том, о чем большинство студентов понятия не имеют. Ну что ж... Можно долго ныть о несправедливости этого мира но решение этой задачи никто не отменит! Да и я глядишь разберусь!
Ну ладно, поехали!
Ладно, для начала пришлось попытаться понять - что же за зверь такой, бинарное дерево. Пожалуй, в роликах доходчиво объяснено:
После этого появилось хоть какое-то понимание. А ещё, я нашёл некое решение, которое на поверку оказалось совсем не решением, но этот код можно взять за основу, подправить и у нас получится выполнить условия задачи:
Продолжаем работу над пониманием всего тут происходящего! И самый верный вариант понимания того что же конкретно нужно сделать в задаче - понять, что делает код, при построении бинарного дерева.
Я основательно покопался в телеграмм-чате курса и нашел то что меня натолкнуло на решение задачи, плюс код выше, я таки создал дерево и записал его в переменную, вот что было написано в чате:
Алексей Раку, [21.08.2023 16:03]
Привет, я просто читаю файл лога построчно. Первая строка корень, создаю узел дерева, сохраняю его в переменную. Иду ниже если встречаю “DEBUG” то смотрю в какую строну, какому узлу создавать дочерний узел и создаю. и так далее, когда дошел до конца, дерево готово, возвращаю сохраненный на первом шаге корень.
Долго думал как это все правильно сделать и получилось вот такое решение:
Вроде бы всё работает и если обратиться к дереву по его ключу, то например можно узнать кто потомки допустим у узла 545237:
Функция должна вернуть только корень восстанавливаемого дерева, который сохранен в самом начале программы.