Агрегация в двоичном дереве Испытание курса: Python: Введение в ООП

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

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

Подсказки

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