Python - Pohon Pencarian

Binary Search Tree (BST) adalah pohon di mana semua node mengikuti properti yang disebutkan di bawah ini - Sub-pohon kiri dari sebuah node memiliki kunci kurang dari atau sama dengan kunci simpul induknya. Sub-pohon kanan dari sebuah node memiliki kunci yang lebih besar daripada kunci node induknya. Jadi, BST membagi semua sub-pohonnya menjadi dua segmen; sub-pohon kiri dan sub-pohon kanan dan dapat didefinisikan sebagai -

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

Cari nilai di B-tree

Mencari nilai di pohon melibatkan membandingkan nilai yang masuk dengan nilai yang keluar dari node. Di sini juga kami melintasi node dari kiri ke kanan dan terakhir dengan induk. Jika nilai yang dicari tidak cocok dengan nilai exitign manapun, maka kita mengembalikan pesan tidak ditemukan jika tidak pesan yang ditemukan dikembalikan.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

7 Not Found
14 is found