Представление двоичного дерева
Двоичные деревья — это фундаментальная структура данных, широко используемая в информатике. Они особенно полезны при создании эффективных алгоритмов для таких задач, как поиск, сортировка и обход данных.
Двоичные деревья состоят из узлов, и каждый узел может иметь не более двух потомков — левого и правого. Каждый из этих потомков, в свою очередь, может иметь собственных левых и правых потомков, и так продолжается до тех пор, пока в дереве не останется узлов.
Верхний узел двоичного дерева называется корнем (root), а самые нижние элементы — листьями (leaves).
Благодаря этой простой идее можно эффективно представлять множество разных типов данных, и такие деревья легко реализовывать в различных языках программирования:
class Node: # Объект Node, который хранит данные для каждого узла
def __init__(self, value): # Значение, хранящееся в каждом узле (может быть любым)
self.left = None # Изначально и left, и right равны None
self.right = None
self.value = value # Хранит значение в объекте
# Ручное создание всех узлов
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# После этого мы можем рекурсивно обойти всё двоичное дерево
# Давайте вычислим сумму всех узлов
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Возвращаем сумму левого и правого поддеревьев, а также текущего узла
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Выводит 36В этом примере мы обходим все узлы, начиная с
root. Если текущий узел равен None, это означает, что мы достигли конца поддерева по данному пути и можем вернуть 0 как сумму. В противном случае вычисляем сумму левого и правого поддеревьев, а также текущего узла и складываем их вместе.Задание: Создать двоичное дерево вручную
На изображении показано двоичное дерево, которое вам предстоит создать вручную.
Напишите код, который будет создавать это двоичное дерево. Вам не нужно ничего выводить — эта часть делается автоматически.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB