Bir BST'deki tüm düğümleri ziyaret etmenin birden fazla yolu vardır.
İkili ağaçlar, programlamada en çok kullanılan veri yapılarından biridir. Bir ikili arama ağacı (BST), verilerin düğümler (ana düğüm ve alt düğüm) biçiminde depolanmasına izin verir. düğüm) öyle ki sol alt düğüm üst düğümden daha küçük ve sağ alt düğüm daha büyük.
İkili arama ağaçları verimli geçiş, arama, silme ve ekleme işlemlerine izin verir. Bu makalede, bir ikili arama ağacında gezinmenin üç yolunu öğreneceksiniz: ön sipariş geçişi, sıra dışı geçiş ve sıra sonrası geçiş.
Sıra Geçişi
Sıra dışı geçiş, bir düğümün çapraz geçiş işlemidir. ikili arama ağacı sol alt ağacı yinelemeli olarak işleyerek, ardından kök düğümü işleyerek ve son olarak sağ alt ağacı yinelemeli olarak işleyerek. Düğümleri artan değer düzeninde işlediğinden, tekniğe sıra içi geçiş adı verilir.
Geçiş, bir ağaç veri yapısındaki her düğümü tam olarak bir kez ziyaret etme işlemidir.
Inorder Traversal Algoritması
BST'nin tüm düğümlerini geçmek için tekrarlayın:
- Sol alt ağacı yinelemeli olarak çaprazlayın.
- Kök düğümü ziyaret edin.
- Sağ alt ağacı yinelemeli olarak çaprazlayın.
Inorder Traversal'ın Görselleştirilmesi
Görsel bir örnek, ikili arama ağacı geçişini açıklamaya yardımcı olabilir. Bu şekil, örnek bir ikili arama ağacının sıra dışı geçişini gösterir:
Bu ikili arama ağacında 56, kök düğümdür. İlk olarak, sol alt ağaç 32'yi, ardından kök düğüm 56'yı ve ardından sağ alt ağaç 62'yi geçmeniz gerekir.
Alt ağaç 32 için, önce sol alt ağaç 28'i çaprazlayın. Bu alt ağacın hiç çocuğu yok, bu yüzden 32. düğümü çaprazlayın. Sonra, yine çocuğu olmayan sağ alt ağaç olan 44'ü çaprazlayın. Bu nedenle, 32'de köklenen alt ağaç için geçiş sırası 28 -> 32 -> 44'tür.
Ardından, 56 numaralı kök düğümü ziyaret edin.
Ardından, 62'de köklenmiş sağ alt ağacı çaprazlayın. Kökü 58 olan sol alt ağacını çaprazlayarak başlayın. Hiç çocuğu yok, bu yüzden sonraki 62 düğümünü ziyaret edin. Son olarak, yine çocuğu olmayan sağ alt ağaç olan 88'i çaprazlayın.
Böylece algoritma, ağacın düğümlerini aşağıdaki sırayla ziyaret eder:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Inorder Traversal Uygulaması
Düğüm öğelerinin değerlerini artan düzende almak için sıra dışı geçişi kullanabilirsiniz. Değerleri azalan düzende almak için işlemi tersine çevirin: sağ alt ağacı, ardından kök düğümü ve ardından sol alt ağacı ziyaret edin. Bir ifade ağacının önek ifadesini bulmak için algoritmayı kullanabilirsiniz.
Ön Sipariş Geçişi
Ön sipariş geçişi inorder'a benzer, ancak sol alt ağacı, ardından sağ alt ağacı yinelemeli olarak işlemeden önce kök düğümü işler.
Ön Sipariş Geçiş Algoritması
BST'nin tüm düğümlerini geçmek için tekrarlayın:
- Kök düğümü ziyaret edin.
- Sol alt ağacı yinelemeli olarak çaprazlayın.
- Sağ alt ağacı yinelemeli olarak çaprazlayın.
Ön Sipariş Geçişinin Görselleştirilmesi
Aşağıdaki şekil, ikili arama ağacının ön sipariş geçişini göstermektedir:
Bu ikili arama ağacında, kök düğüm 56'yı işleyerek başlayın. Ardından sol alt ağacı (32) ve ardından sağ alt ağacı (62) çaprazlayın.
Sol alt ağaç için, kök düğüm olan 32'deki değeri işleyin. Ardından, sol alt ağacı (28) ve son olarak sağ alt ağacı (44) çaprazlayın. Bu, 32'de köklenen sol alt ağacın geçişini tamamlar. Geçiş şu sırada gerçekleşir: 56 -> 32 -> 28 -> 44.
Sağ alt ağaç için, kök düğüm olan 62'deki değeri işleyin. Ardından, sol alt ağacı (58) ve son olarak sağ alt ağacı (88) çaprazlayın. Yine, hiçbir düğümün alt öğesi yoktur, dolayısıyla geçiş bu noktada tamamlanmıştır.
Ağacın tamamını aşağıdaki sırayla geçtiniz:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Ön Sipariş Geçişi Uygulaması
Ağacın bir kopyasını en kolay şekilde oluşturmak için ön sipariş geçişini kullanabilirsiniz.
Sipariş Sonrası Geçiş
Postorder traversal, bir ikili arama ağacının düğümlerini yinelemeli olarak çaprazlama işlemidir. sol alt ağacı işlemek, ardından sağ alt ağacı yinelemeli olarak işlemek ve son olarak kök düğüm Kök düğümü her iki alt ağaçtan sonra işlediği için bu yönteme postorder traversal adı verilir.
Sipariş Sonrası Geçiş Algoritması
BST'nin tüm düğümlerini geçmek için tekrarlayın:
- Sol alt ağacı yinelemeli olarak çaprazlayın.
- Sağ alt ağacı yinelemeli olarak çaprazlayın.
- Kök düğümü ziyaret edin.
Sipariş Sonrası Geçişin Görselleştirilmesi
Aşağıdaki şekil, ikili arama ağacının sıra sonrası geçişini göstermektedir:
Sol alt ağaç 32'yi, ardından sağ alt ağaç 62'yi çaprazlayarak başlayın. 56 numaralı kök düğümü işleyerek bitirin.
Kökü 32 olan alt ağacı işlemek için sol alt ağacı 28'i çaprazlayın. 28'in hiç çocuğu olmadığından, sağ alt ağaca, 44'e gidin. İşlem 44 çünkü onun da çocuğu yok. Son olarak, 32 numaralı kök düğümü işleyin. Bu alt ağacı 28 -> 44 -> 32 sırasıyla geçtiniz.
58 -> 88 → 62 sırasındaki düğümleri ziyaret etmek için aynı yaklaşımı kullanarak doğru alt ağacı işleyin.
Son olarak, 56 numaralı kök düğümü işleyin. Tüm ağacı şu sırayla geçeceksiniz:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Sipariş Sonrası Geçiş Uygulaması
Bir ağacı yapraktan köke silmek için sipariş sonrası geçişi kullanabilirsiniz. Bir ifade ağacının sonek ifadesini bulmak için de kullanabilirsiniz.
Düğümün kendisini ziyaret etmeden önce belirli bir düğümün tüm yaprak düğümlerini ziyaret etmek için sipariş sonrası geçiş tekniğini kullanabilirsiniz.
İkili Arama Ağacı Geçişlerinin Zaman ve Mekan Karmaşıklığı
Her üç geçiş tekniğinin zaman karmaşıklığı, Açık), Neresi N boyutu ikili ağaç. Tüm geçiş tekniklerinin uzay karmaşıklığı, Ah), Neresi H ikili ağacın yüksekliğidir.
İkili ağacın boyutu, o ağaçtaki düğüm sayısına eşittir. İkili ağacın yüksekliği, ağacın kök düğümü ile en uzak yaprak düğümü arasındaki kenarların sayısıdır.
İkili Arama Ağacı Geçişi için Python Kodu
Aşağıda, üç ikili arama ağacı geçişini de gerçekleştiren bir Python programı bulunmaktadır:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(root):
if root:
# Traverse left subtree
inorder(root.left)# Traverse root
print(str(root.value) + ", ", end='')# Traverse right subtree
inorder(root.right)# Function to perform the postorder tree traversal
defpostorder(root):
if root:
# Traverse left subtree
postorder(root.left)# Traverse right subtree
postorder(root.right)# Traverse root
print(str(root.value) + ", ", end='')# Function to perform the preorder tree traversal
defpreorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')# Traverse left subtree
preorder(root.left)# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Bu program aşağıdaki çıktıyı üretmelidir:
Programcılar İçin Bilmeniz Gereken Algoritmalar
Algoritmalar, her programcının yolculuğunun önemli bir parçasıdır. Bir programcının algoritmalar konusunda bilgili olması çok önemlidir. Birleştirme sıralaması, hızlı sıralama, ikili arama, doğrusal arama, ilk önce derinlik araması vb. gibi bazı algoritmalara aşina olmalısınız.
