Python: Агрегация в двоичном дереве

Python: Введение в ООП 2 сообщения
Обновлено: 31 марта, 12:36
44
Студента
79%
Завершения

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

src/solution.py

Реализуйте следующие методы в классе solution.Node:

  • __len__() — возвращает количество узлов в дереве (используется в len()).
  • __repr__() — возвращает строковое представление дерева (используется для отображения в REPL).
  • total() — возвращает сумму всех ключей дерева.
  • minimum() — возвращает минимальный ключ дерева.
  • maximum() — возвращает максимальный ключ дерева.
  • to_list() — возвращает плоский список, содержащий все ключи.
  • every(fn) — проверяет, удовлетворяют ли все ключи дерева условию, заданному в передаваемой функции.
  • some(fn) — проверяет, удовлетворяет ли какой-либо ключ дерева условию, заданному в передаваемой функции.

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

from solution import Node
tree = Node(
    9,
    Node(
        4,
        Node(8),
        Node(
            6,
            Node(3),
            Node(7),
        ),
    ),
    Node(
        17,
        right=Node(
            22,
            Node(20),
        ),
    ),
)
len(tree)  # 9
tree.total()  # 96
tree.to_list()  # [9, 4, 8, 6, 3, 7, 17, 22, 20]
tree.every(lambda key: key <= 22)  # True
tree.some(lambda key: key > 22)  # False
tree.minimum()  # 3
tree.maximum()  # 22
tree2 = Node(3, Node(1), Node(2))
tree2  # выводится repr(tree2)
# Node(3, Node(1, None, None), Node(2, None, None))

Подсказки

  • Двоичное дерево.
  • Для реализации каждого из методов потребуется выполнить обход всех узлов дерева.

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов