Python - Ağaç Geçiş Algoritmaları
Geçiş, bir ağacın tüm düğümlerini ziyaret etme işlemidir ve değerlerini de yazdırabilir. Çünkü, tüm düğümler kenarlar (bağlantılar) yoluyla birbirine bağlı olduğundan, her zaman kök (baş) düğümden başlıyoruz. Yani, bir ağaçtaki bir düğüme rastgele erişemeyiz. Bir ağacı geçmek için kullandığımız üç yol vardır -
- Sıralı Geçiş
- Geçiş Ön Siparişi Ver
- Sipariş Sonrası Geçiş
Sıralı Geçiş
Bu geçiş yönteminde önce sol alt ağaç, ardından kök ve daha sonra sağ alt ağaç ziyaret edilir. Her düğümün bir alt ağacın kendisini temsil edebileceğini her zaman hatırlamalıyız.
Aşağıdaki python programında, sol ve sağ düğümlerin yanı sıra kök düğüm için yer tutucular oluşturmak için Node sınıfını kullanıyoruz. Ardından ağaca veri eklemek için bir ekleme işlevi oluşturuyoruz. Son olarak, sıralı geçiş mantığı boş bir liste oluşturarak ve önce sol düğümü ve ardından kök veya ana düğümü ekleyerek uygulanır. Son olarak, Inorder geçişini tamamlamak için sol düğüm eklenir. Lütfen bu işlemin tüm düğümler geçilene kadar her bir alt ağaç için tekrarlandığına dikkat edin.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
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
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -
[10, 14, 19, 27, 31, 35, 42]Geçiş Ön Siparişi Ver
Bu geçiş yönteminde, önce kök düğüm, ardından sol alt ağaç ve son olarak sağ alt ağaç ziyaret edilir.
Aşağıdaki python programında, sol ve sağ düğümlerin yanı sıra kök düğüm için yer tutucular oluşturmak için Node sınıfını kullanıyoruz. Ardından ağaca veri eklemek için bir ekleme işlevi oluşturuyoruz. Son olarak, ön sipariş geçiş mantığı, boş bir liste oluşturarak ve önce kök düğümü ve ardından sol düğümü ekleyerek gerçekleştirilir. Son olarak Ön sipariş geçişini tamamlamak için doğru düğüm eklenir. Lütfen bu işlemin tüm düğümler geçilene kadar her bir alt ağaç için tekrarlandığına dikkat edin.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
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
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -
[27, 14, 10, 19, 35, 31, 42]Sipariş Sonrası Geçiş
Bu çapraz geçiş yönteminde, en son kök düğüm, dolayısıyla adı ziyaret edilir. Önce soldaki alt ağaçtan, sonra sağ alt ağaçtan ve son olarak da kök düğümü geçiyoruz.
Aşağıdaki python programında, sol ve sağ düğümlerin yanı sıra kök düğüm için yer tutucular oluşturmak için Node sınıfını kullanıyoruz. Ardından ağaca veri eklemek için bir ekleme işlevi oluşturuyoruz. Son olarak, sipariş sonrası geçiş mantığı, boş bir liste oluşturarak ve önce sol düğümü ve ardından sağ düğümü ekleyerek gerçekleştirilir. Son olarak, sipariş sonrası geçişi tamamlamak için kök veya ana düğüm eklenir. Lütfen bu işlemin tüm düğümler geçilene kadar her bir alt ağaç için tekrarlandığına dikkat edin.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
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
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -
[10, 19, 14, 31, 42, 35, 27]