lisp programlama dili

Lisp Dili Ağaç İşlemleri 2

Merhaba arkadaşlar önceki yazımın devamı olacak bu yazımızda ağaç üzerindeki düğüm sayısını, ağaç üzerinde DFS ve BFS algoritmaları ile dolaşmayı yazarak anlatmaya çalışacağım.

Ağaç Üzerindeki Düğüm Sayısını Bulma

Yine aynı önceki yazımızda yazdığımız kodlar üzerine ekleme yapar şekilde gideceğiz.

Ağaçta DFS ile Dolaşma

DFS Nedir?

Öncelikle DFS nedir ona bakalım. DFS ağaçlar ve Graflar üzerinde çalışan bir tür arama algoritmasıdır. Açılımı Derin Öncelikli Arama yani Depth First Search’dir.

Önce sol sonra sağ ve en son kök dolaşılır. Graflar da ise önce düğümün komşusuna ve onun da komşusu varsa o komşuya gidilir. Yani önce derine bakılır.

veri yapıları binary tree örnek ağaç

Üstteki ağacımızı inceler isek; DFS algoritması ile dolaştığımızda 9-4-3-7-1-8-2 şeklinde dolaşacaktır. Burada kökü en sona yazmak daha uygundur. Çünkü öncelik gidilen düğümün alt düğümlerindedir.

Şimdi gelelim bunun kodunu DrRacket ile yazalım.

Ağaçta BFS ile Dolaşma

BFS Nedir?

Aynı DFS gibi bu da bir arama algoritmasıdır. Bunun da açılımı Breadth First Search’dür ve Türkçe karşılığı ise geniş öncelikli arama olarak çevirilebilir.

veri yapıları binary tree örnek ağaç

Bu ağacımızı BFS algoritması ile dolaştığımızda 2-3-8-9-4-7-1 çıkmaktadır. Kısaca ağaç genişlemesine dolaşılır.

 

Bu arama ağacını DrRacket de yazalım şimdi

Ağacımızın bir seviyesi var. Biz bu seviyede kaç düğüm olduğunu bulalım. Örnek vermek gerekirse yukarıdaki ağaçta 2.seviyeye kadar 3 düğüm bulunuyor. 3.seviyeye kadar ise 7 düğüm bulunuyor. Bize bunu veren kodu ekliyorum.

Bir de aranan düğümün hangi seviyede olduğunu bulan fonksiyonumuza bakarsak

Drracket seviye bulan kod

Şimdi gelelim son aşamaya BFS algoritmasını yazmaya…

Bu yazdığımız iki kodun birleşimi aslında bize BFS’yi vermektedir.

(define (BFS agac dugum)  (dugum-say agac (seviye agac dugum)))

Son olarak tüm kodu yazacak olursak..

DrRacket BFS

Eklentideki kısıtlamadan dolayı görsel olarak vermek zorunda kalıyorum. Umarım faydalı olmuştur.

 

Bir cevap yazın