Python - Arama Ağacı
İkili Arama Ağacı (BST), tüm düğümlerin aşağıda belirtilen özellikleri izlediği bir ağaçtır - Bir düğümün sol alt ağacında, ana düğümün anahtarından küçük veya ona eşit bir anahtara sahiptir. Bir düğümün sağ alt ağacı, üst düğümün anahtarından daha büyük bir anahtara sahiptir. Böylece, BST tüm alt ağaçlarını iki bölüme ayırır; sol alt ağaç ve sağ alt ağaç ve şu şekilde tanımlanabilir -
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
B ağacında bir değer arayın
Bir ağaçta bir değerin aranması, gelen değeri çıkış düğümlerinden çıkan değerle karşılaştırmayı içerir. Burada ayrıca düğümleri soldan sağa ve son olarak ebeveyn ile birlikte geçiyoruz. Aranan değer herhangi bir çıkış işareti değeriyle eşleşmiyorsa, o zaman bulunamadı mesajı döndürürüz, aksi takdirde bulunan mesaj döndürülür.
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))
Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -
7 Not Found
14 is found