เริ่มต้นใช้งานเริ่มต้นใช้งานได้ฟรี

การแทรก node เข้าไปใน Binary Search Tree

ในวิดีโอ คุณได้เรียนรู้ว่า Binary Search Tree (BST) คืออะไร และวิธีการใช้งานฟังก์ชันหลักต่าง ๆ ของมัน

ในแบบฝึกหัดนี้ จะได้ลองเขียนฟังก์ชันสำหรับแทรก node เข้าไปใน BST

เพื่อทดสอบโค้ด สามารถใช้ tree ต่อไปนี้:

Graphical representation of a binary search 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"))
แก้ไขและรันโค้ด