Merhaba algoritma severler. Bugün bahsetmek istediğim konu Morris Traversal Algoritması.

Morris Traversal Algoritması Amacı Nedir?

Algoritmanın amacı bir Binary Tree'de inorder şekilde traversal yapmamıza yarayan bir algoritmadır.

Binary Tree Nedir?

Binary Tree, bir veri yapısıdır. Bu veri yapısının yapı taşı köklerdir ve bu kökler ağaç şeklini alır. Her kökün en fazla 2 alt kökü vardır. Bu alt kökler sağ ve solda olmak üzere dallanırlar.

Inorder Nedir?

Inorder, kısaca toplu bir nesneyi, diziyi sırasına veya uygun şekilde düzenlemek, sıralamak demektir. Burada kullanacağımız anlamı soldan sağa doğru (left, root, right) sıralama gibi düşünebilirsiniz.

Traversal Nedir?

Traversal, geçiş veya geçmek demektir. Konumuzda kullanacağımız anlamı ise Binary Tree'de kökler arasında geçişidir.

Morris Traversal Algoritması Nasıl İşler?

Şimdi geldik asıl konumuz olan algoritmaya. Konuya dalmadan önce Binary Tree 3 şekilde order edilebilir. Bunlar şöyledir:

Inorder: Sol aşağı kökten başlar. Sol, kök, sağ sıralamasıyla geçiş yapar.

Preorder:En üst kökten başlar. Kök, sol, sağ sıralamasıyla geçiş yapar.

Postorder:Sol aşağı kökün sol kökünden başlar. Sol, sağ, kök sıralamasıyla geçiş yapar.

Morris Algoritmasında Inorder şekilde sıralar. Özyineleme veya stack kullanmaz. Algoritmayı anlatırken aşağıdaki Java kodunu kullanacağım.

Öncelikle Binary Tree yapımızı oluşturmak için bir Node class'ı oluşturduk. Bu class sayesinde Main metodumuz içerisinde ilk olarak Tree class'ında oluşturduğumuz Node nesnesinin rootunu ve alt rootlarını initalize ettik.

Ardından initalize ettiğimiz bu Binary Tree yapısını asıl konumuz olan Morris metoduna gönderiyoruz. Ardından aşamalar şöyle gerçekleşir:

• Anlık olarak hangi rootda olduğunu tutması için gönderdiğimiz yapımızı curr adında bir Node nesnesine tanımlıyoruz.
• Tanımımızdan sonra curr nesnesinin null olmaması şartını sağlayan, her şeyin olup bittiği döngüye giriyoruz.
• Döngümüzde ilk olarak curr nesnemizin solunda kök olup olmadığını kontrol ediyoruz. Eğer curr'un solunda nesne yoksa yani curr.left_node null olursa şu anki kökü print metodumuzla yazdırırız ve curr nesnemizi sağındaki kökü işaret edecek şekilde güncelleriz.
• Eğer curr'un solunda nesne varsa yani curr.left_node null değil ise curr'u curr'un sol alt ağacındaki en sağdaki düğümün sağ çocuğu yapar.
• Ve curr bu sol alt düğüm olur.

{4}'e girdik. Sol altını kontrol ettik. Baktık ki var. O zaman sağ alt düğümün en sağındaki düğüme, yani {3}'e sağ alt düğümü olacak şekilde {4}'ü yerleştirdik. Curr nesnesini de {2} yaptık.

Aynı işlemleri {2} için uyguladık ve kökümüz aşağıdaki şekli aldı.

Output Süreci

İstediğimiz şekil oluştu. Şimdi sıra geldi bu sırayı programa okutmak. Başladı 1 den yazdırmaya. Sıra geldi 2'ye. Eyvah solunda düğüm var demeden önce rahat olun. Döngümüzdeki prev nesnesi sayesinde sol alt düğümden geçildiğini anlar ve kendini yazdırdıktan sonra sağ alt düğüme devam eder. Böylece {5}'e kadar yazdırılır. Bu yazdırma sonucunda şöyle bir sıralama döner: [1,2,3,4,5]. Yani istediğimiz Inorder sonuç.

Kaynakça:

What is Morris traversal? (Educative)