home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมตรวจสอบว่ามีหนึ่งค่าใน BST หรือไม่ใน Python

สมมติว่าเรามีแผนผังการค้นหาแบบไบนารีและอินพุตอื่นที่เรียกว่า val เราต้องตรวจสอบว่ามี val อยู่ในทรีหรือไม่

ดังนั้นหากอินพุตเป็นแบบ

โปรแกรมตรวจสอบว่ามีหนึ่งค่าใน BST หรือไม่ใน Python

val =7 จากนั้นผลลัพธ์จะเป็น True เนื่องจากมี 7 อยู่ในทรี

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

  • กำหนดฟังก์ชัน Solve() สิ่งนี้จะหยั่งราก val

  • ถ้ารูทเป็นโมฆะ

    • คืนค่าเท็จ

  • ถ้าข้อมูลของ root เหมือนกับ val แล้ว

    • คืนค่า True

  • ถ้า data ของ root

    • คืนค่าการแก้ (ด้านซ้ายของรูท, val)

  • คืนค่าการแก้ (ทางขวาของรูท, val)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น−

ตัวอย่าง

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, val):
      if not root:
         return False
      if root.data == val:
         return True
      if root.data > val:
         return self.solve(root.left, val)
      return self.solve(root.right, val)
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root, 7))

อินพุต

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
7

ผลลัพธ์

True