Вставка узла в двоичное дерево поиска
В видеоуроке вы познакомились с двоичными деревьями поиска (BST) и научились реализовывать их основные операции.
В этом упражнении вы реализуете функцию для вставки узла в BST.
Для проверки кода можно использовать следующее дерево:
Узлы содержат названия книг, а дерево построено на основе алфавитного порядка.
Это дерево предварительно загружено в переменную bst:
bst = CreateTree()
Проверить корректность вставки узла можно с помощью следующего кода:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Это упражнение является частью курса
Структуры данных и алгоритмы на Python
Инструкции к упражнению
- Проверьте, является ли двоичное дерево поиска пустым.
- Проверьте, меньше ли вставляемое значение данных, чем данные текущего узла.
- Проверьте, больше ли вставляемое значение данных, чем данные текущего узла.
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
new_node = TreeNode(data)
# Check if the BST is empty
if ____ == None:
self.root = new_node
return
else:
current_node = self.root
while True:
# Check if the data to insert is smaller than the current node's data
if ____ < ____:
if current_node.left_child == None:
current_node.left_child = new_node
return
else:
current_node = current_node.left_child
# Check if the data to insert is greater than the current node's data
elif ____ > ____:
if current_node.right_child == None:
current_node.right_child = new_node
return
else:
current_node = current_node.right_child
bst = CreateTree()
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))