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

src/solution.py

Двоичное дерево поиска состоит из узлов, каждый из которых содержит значение ключа и два поддерева (левое и правое), которые в свою очередь также являются двоичными деревьями. Правильное дерево не содержит повторяющихся ключей, и для каждого узла гарантируется, что в левом поддереве все значения меньше текущего, а в правом — больше.

Двоичное дерево поиска

Реализуйте класс, который реализует представление узла. При инициализации объекта класс принимает на вход три параметра:

  • key — значение ключа (число),
  • left — левое поддерево (тоже узел, по умолчанию None),
  • right — правое поддерево (по умолчанию None).

Каждый экземпляр класса должен содержать атрибуты:

  • key
  • left
  • right

Также класс должен реализовывать метод search(key), который выполняет поиск узла в правильно построенном двоичном дереве по ключу и возвращает узел. Если узел не найден, возвращается None.

Примеры

>>> from solution import Node
>>> node5 = Node(5)
>>> node22 = Node(22, right=Node(20))
>>> tree = Node(
...     9,
...     Node(
...         4,
...         Node(3),
...         Node(
...             6,
...             node5,
...             Node(7),
...         ),
...     ),
...     Node(
...         17,
...         right=node22,
...     ),
... )
>>> tree.search(6).key
6
>>> tree.search(6).left.key
5
>>> tree.search(6).right.key
7
>>> tree.search(5) is node5
True
>>> tree.left.left.key
3
>>>

Подсказки

Успешных завершений: 72%

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

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

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

Последние код-ревью

Автор Дата обновления Версий
user-60f6c2532e340d4e 31 авг., 17:51 1
vitaliipaprotskyi 23 авг., 06:38 1
user-110df8b01617705f 08 авг., 06:20 1
agmrv 03 авг., 06:50 1
kseniya_pr 12 июня, 18:12 1