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]