Python - ต้นไม้ค้นหา

Binary Search Tree (BST) คือต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง - แผนผังย่อยด้านซ้ายของโหนดมีคีย์น้อยกว่าหรือเท่ากับคีย์ของโหนดแม่ แผนผังย่อยด้านขวาของโหนดมีคีย์ที่มากกว่าคีย์ของโหนดแม่ ดังนั้น BST จึงแบ่งต้นไม้ย่อยทั้งหมดออกเป็นสองส่วน แผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวาและสามารถกำหนดเป็น -

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

ค้นหาค่าใน B-tree

การค้นหาค่าในต้นไม้เกี่ยวข้องกับการเปรียบเทียบค่าขาเข้ากับค่าที่ออกจากโหนด นอกจากนี้เรายังสำรวจโหนดจากซ้ายไปขวาและสุดท้ายด้วยพาเรนต์ หากค่าที่ค้นหาไม่ตรงกับค่า exitign ใด ๆ เราจะส่งคืนข้อความ not found มิฉะนั้นข้อความที่พบจะถูกส่งกลับ

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

# Insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

7 Not Found
14 is found