การแทรก node เข้าไปใน Binary Search Tree
ในวิดีโอ คุณได้เรียนรู้ว่า Binary Search Tree (BST) คืออะไร และวิธีการใช้งานฟังก์ชันหลักต่าง ๆ ของมัน
ในแบบฝึกหัดนี้ จะได้ลองเขียนฟังก์ชันสำหรับแทรก node เข้าไปใน BST
เพื่อทดสอบโค้ด สามารถใช้ tree ต่อไปนี้:

แต่ละ node เก็บชื่อหนังสือ และ BST นี้เรียงลำดับตามตัวอักษร
Tree นี้ถูกโหลดไว้ล่วงหน้าในตัวแปร bst แล้ว:
bst = CreateTree()
สามารถตรวจสอบว่า node ถูกแทรกอย่างถูกต้องด้วยโค้ดนี้:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
โครงสร้างข้อมูลและอัลกอริทึมใน Python
คำแนะนำการฝึกหัด
- ตรวจสอบว่า BST ว่างเปล่าหรือไม่
- ตรวจสอบว่าข้อมูลที่จะแทรกมีค่าน้อยกว่าข้อมูลใน node ปัจจุบันหรือไม่
- ตรวจสอบว่าข้อมูลที่จะแทรกมีค่ามากกว่าข้อมูลใน node ปัจจุบันหรือไม่
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
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"))