Soru: Bir adet ikili arama ağacı (binary search tree) oluşturunuz ve bu ağaç üzerinde ssn numarası ve bir isim tutunuz. Bu bilgileri ssn numarasına göre ağaca yerleştirin ve yerleşen bu verileri içsıraya göre (inorder) dolaşan bir kod yazınız. Bu kodu kullanarak ağaçta arama yapan bir fonksiyon yazınız.

Çözen : Şadi Evren ŞEKER

Çözüm :

Bu tip bir soruda verilerin tutulması ve işlenmesi önemli bir yer tutar. Verilerin tutulması için scheme dilinde bulunan struct özelliğinden faydalanacağız. Öncelikle verimizi tanımlayalım:

(define-struct tree (ssn label left right))

Yukarıdaki bu tanımda ağacın bir düğümü (node) için kullanılacak yapı verilmiştir. Bu yapıda bir düğümde ssn, label ve ağacın solunu gösteren left, sağını gösteren right değişkenleri bulunmaktadır. Yani solu ve sağı yine kendi yapısından birer üye olacaktır.

(define tree-1 (make-tree 1 ‘x null null))

(define tree-2 (make-tree 3 ‘y null null))

(define tree-3 (make-tree 2 ‘z tree-1 tree-2))

(define tree-4 (make-tree 5 ‘p null null))

(define tree-5 (make-tree 4 ‘q tree-3 tree-4))

Yukarıda örnek ağaç tanımları verilmiştir. Buna göre yukarıdaki ağacı çizecek olursak:

Yukarıdaki şekilde bir ağaç elde ederiz. Bu ağaçta en tepede tree-5 ile tanımlanan ve içerisinde 4,q bulunan düğüm bulunmaktadır. Bu düğümün solunda tree-3 yani 3,y ve sağında ise tree-4 yani 5,p bulunmaktadır ve ağaç bu şekilde birbirine düğümler eklenerek devam etmektedir.

Şimdi ağacı dolaşan fonksiyonumuzu yazalım:

(define (inorder bt) ( cond[(null? bt) null][else (cond[(and (null? (tree-left bt ))(null? (tree-right bt))) (list(tree-label bt) (tree-ssn bt))][else (append (inorder (tree-left bt)) (list(tree-label bt) (tree-ssn bt)) (inorder (tree-right bt)))])]))

Fonksiyon basitçe ağacın önce sol, sonra düğüm sonra sağ değerini ekrana bastırmaktadır. Yani gidebildiği kadar sola gidip en sondaki elemanı basıp bir yukarı çıkmakta ve sonra sağa gitmektedir. Bunu sağlayan sadece yukarıdaki fonksiyonda bulunan dolaşma sırasıdır. Fonksiyonu çalıştırmak için aşağıdaki komut verilebilir.

(inorder tree-5)

Kodun çalışması sonucunda yukarıdaki ekranda görüldüğü üzere ağacın sol-orta-sağ sırasıyla dolaşılmış hali ekrana basılmaktadır:

(x 1 z 2 y 3 q 4 p 5)

Şimdi sorunun ikinci kısmına yani ağaçta arama yapan kısma geçebiliriz:

(define (search bt n)(cond [(eq? (tree-ssn bt) n) (tree-label bt)][(and (null? (tree-left bt)) (null? (tree-right bt))) false]

[else (cond [(eq? (tree-ssn bt) n) (tree-name bt)]

[else (cond [(> (tree-ssn bt) n) (search (tree-left bt) n)][else (search (tree-right bt) n)])

])]))

Yukarıdaki kodu çalıştırmak için aşağıdaki komut verilebilir:

(search tree-5 4)

Yukarıda dikkat edilirse inorder fonksiyonunun aynısı kullanılmıştır. Tek farkı arama işlemi sırasında eşitlik durumu kontrol edilmiş ve bu sayede şayet aranan elemana ulaşıldıysa aram işlemi bitirilmiştir.

Bu kodun çalışan hali ise yukarıdaki şekildedir. Yani aranan değer 4 olarak verildiğinde, 4 ssn değerine sahip q label’ı döndürülmüştür.

Yorumlar

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


− dokuz = 0