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.

(define Agac(list 12
 
      (list 13 (list 19 '() '() ) (list 14 '() '()) )
 
      (list 81 (list 71 '() '() ) (list 12 '() '()) )
))

(define (kok agac) (car agac))
(define (sol agac) (car (cdr agac)))
(define (sag agac) (car (cdr (cdr agac))))

;Bir ağaçdaki düğüm sayısını bulma
(define (dugumSay agac)(if (empty? agac)0
                           (+ (dugumSay (sol agac )) (dugumSay (sag agac)) 1)
                           )
  )
(dugumSay Agac)

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.

(define Agac(list 12
 
      (list 13 (list 19 '() '() ) (list 14 '() '()) )
 
      (list 81 (list 71 '() '() ) (list 18 '() '()) );12 değerini 18 olarak değiştirdim.
))

(define (kok agac) (car agac))
(define (sol agac) (car (cdr agac)))
(define (sag agac) (car (cdr (cdr agac))))

;Bir ağaçdaki düğüm sayısını bulma
(define (dugumSay agac)(if (empty? agac)0
                           (+ (dugumSay (sol agac )) (dugumSay (sag agac)) 1)
                           )
  )
(dugumSay Agac)


;DFS Algoritması ile Ağaç üzerinde dolaşma

(define (DFS agac aranan) (if (empty? agac)0
                              (if(> (DFS (sol agac) aranan)0)
                                    (DFS (sol agac) aranan)
                                    (if (> (DFS (sag agac) aranan)0)
                                           (DFS (sag agac)aranan)
                                           (if (= aranan (kok agac))
                                               (dugumSay agac)
                                               0)
                                           )
                                        )
                                    )
                                 )
                              
(DFS Agac 14)

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.

(define Agac(list 12
 
      (list 13 (list 19 '() '() ) (list 14 '() '()) )
 
      (list 81 (list 71 '() '() ) (list 18 '() '()) )
))

(define (kok agac) (car agac))
(define (sol agac) (car (cdr agac)))
(define (sag agac) (car (cdr (cdr agac))))

(define (dugum-say agac seviye)(if (empty? agac)0
                                   (if (= seviye 0)0
                                       (+ 1 (dugum-say (sol agac)(- seviye 1))
                                          (dugum-say (sag agac) (- seviye 1))
                                          )
                                       )
                                   )
  )

(dugum-say Agac 1)

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.

 

Bunlara Göz Atmak İsteyebilirsiniz

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir