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

Python: Введение в ООП
15
Студентов
66%
Завершения
Обновлено: 24 февр., 18:34

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

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))
>>>

Подсказки

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

Для полного доступа к испытанию нужна профессиональная подписка

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

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов