Python: Поиск в двоичном дереве

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

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

Подсказки

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

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

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