Menyisipkan node ke dalam binary search tree
Dalam video, Anda mempelajari apa itu binary search tree (BST) dan cara mengimplementasikan operasi utamanya.
Pada latihan ini, Anda akan mengimplementasikan sebuah fungsi untuk menyisipkan node ke dalam BST.
Untuk menguji kode Anda, Anda dapat menggunakan pohon berikut:
Node berisi judul buku, membentuk BST berdasarkan urutan alfabet.
Pohon ini telah dimuat sebelumnya dalam variabel bst:
bst = CreateTree()
Anda dapat memeriksa apakah node telah disisipkan dengan benar menggunakan kode ini:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Latihan ini adalah bagian dari kursus
Struktur Data dan Algoritma di Python
Petunjuk latihan
- Periksa apakah BST kosong.
- Periksa apakah data yang akan disisipkan lebih kecil daripada data node saat ini.
- Periksa apakah data yang akan disisipkan lebih besar daripada data node saat ini.
Latihan interaktif praktis
Cobalah latihan ini dengan menyelesaikan kode contoh berikut.
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"))