Python - Cây tìm kiếm

Cây tìm kiếm nhị phân (BST) là cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập dưới đây - Cây con bên trái của một nút có khóa nhỏ hơn hoặc bằng khóa của nút cha của nó. Cây con bên phải của một nút có khóa lớn hơn khóa của nút cha của nó. Như vậy, BST chia tất cả các cây con của nó thành hai đoạn; cây con bên trái và cây con bên phải và có thể được định nghĩa là -

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

Tìm kiếm giá trị trong cây B

Tìm kiếm giá trị trong cây liên quan đến việc so sánh giá trị đến với các nút thoát giá trị. Ở đây, chúng tôi cũng duyệt các nút từ trái sang phải và cuối cùng là nút cha. Nếu giá trị được tìm kiếm không khớp với bất kỳ giá trị exitign nào, thì chúng tôi trả về thông báo không tìm thấy nếu không thông báo tìm thấy được trả về.

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))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

7 Not Found
14 is found