Код на салфетке

Что выведет этот код? №33

🔥1

414 views08:03

Вчерашняя задача была не простой, на первый взгляд. Бинарные деревья сложно даются многим, а данную задачу решило 29% из всего 14ти ответивших.

Код задачи:

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    left: "Node" = None
    right: "Node" = None


def sod(root, depth=0):
    if root is None:
        return 0
    return depth + sod(root.left, depth + 1) + sod(root.right, depth + 1)


root_node = Node(
    value=1, 
    left=Node(value=2, left=Node(4), right=Node(5)), 
    right=Node(value=3, left=Node(6), right=Node(7))
)

print(sod(root_node))

Разбор задачи
Пойдём сверху вниз. Сперва создаём датакаласс Node, описывающий узел бинарного дерева. Применение датакласса описано в посте "[AIOgram3 5.1. Создание структуры](https://pressanybutton.ru/post/telegram-bot-na-aiogram3/aiogram3-51-sozdanie-struktury/)".
В классе прописываем три поля:
1. value - числовое значение хранящееся в узле.
2. left - указание на дочерний узел в левой части дерева.
3. right - указание на дочерний узел в правой части дерева.
Обратите внимание, поля left и right являются объектами этого же класса Node и для указания типа данных используются двойные кавычки, поскольку мы не можем явно указать внутри класса, что он используется "сам в себе".

Далее идёт функция sod, принимающая аргументы:
- root - корневой узел.
- depth - глубина относительно начала дерева, по умолчанию 0.
Поскольку функция рекурсивная, необходимо в самом начале прописать условие выхода из рекурсии. Прописываем блок if, проверяющий, что переданный корень существует, если же вместо него пришёл None, возвращаем 0.
Если выхода из функции не произошло, то возвращаем сумму текущей глубины с глубинами дочерних узлов в рекурсивном вызове.

После класса и функции, создаём переменную root_node, в которой определяем экземпляр класса Node с рядом дочерних узлов.

В самом конце выводим результат вызова функции sod в терминал.

Правильный ответ: 10.

Что это за дерево такое?
Теперь разберёмся, какое дерево у нас получилось. Мы построили классическое бинарное дерево. В нашем случае, корневой узел содержит значение 1, его левый потомок - узел с значением 2, правый - 3, и так далее. Каждый узел может иметь до двух потомков: left и right. Графически дерево можно изобразить следующим образом:

Это идеальный пример полного бинарного дерева, где каждый узел, кроме листовых, имеет ровно два потомка. Такие структуры часто используются в алгоритмах поиска, сортировки, а также для хранения данных, которые требуют быстрого доступа.

Процесс вычисления суммы глубин.
Теперь вернёмся к функции sod. В процессе её выполнения мы фактически проходим по всем узлам дерева, начиная с корня. На каждом уровне прибавляем текущее значение глубины к результату рекурсивного вызова для левого и правого потомков.

Пройдемся по дереву:
1. Стартуем с корня (1). Глубина 0.
2. Переходим на левую ветку: узел 2, глубина 1.
3. Снова идём влево: узел 4, глубина 2. Узел не имеет потомков, возвращаем 2.
4. Возвращаемся к узлу 2, идём вправо: узел 5, глубина 2. Узел не имеет потомков, возвращаем 2.
5. Возвращаемся к узлу 1, обрабатываем правую ветку: узел 3, глубина 1.
6. Идём влево: узел 6, глубина 2. Узел не имеет потомков, возвращаем 2.
7. Возвращаемся к узлу 3, идём вправо: узел 7, глубина 2. Узел не имеет потомков, возвращаем 2.

Суммируем результат:
- Глубина 0 (узел 1): 0
- Глубина 1 (узлы 2 и 3): 1 + 1 = 2
- Глубина 2 (узлы 4, 5, 6, 7): 2 + 2 + 2 + 2 = 8

Общая сумма глубин = 0 + 2 + 8 = 10.

Вот и весь процесс. В итоге мы получили ответ 10, который и является суммой всех глубин узлов в этом бинарном дереве.

Заключение
Таким образом, задача оказалась не такой сложной, как показалось на первый взгляд, особенно если разбить её на части. Основной вызов здесь – правильно понять, как работает рекурсия и как она взаимодействует с каждым узлом в дереве.

244🔥3

401 viewsedited 08:04