İkili Arama Ağaçları ( Binary Search Tree)

İspanya ‘dan selamlar 🙂 Bu yazıda Binary Search Tree de dolaşma (traversal) , arama (search) ve ekleme(insert) yapılarına bakacağız. Bunlara bakmadan önce eğer bilmiyorsanız özyineli (recursive) fonksiyonları incelemenizi tavsiye ederim.

Binary Search Tree lerin normal treelerden farkı:

  • bir node un en fazla 2 child ı olması ,
  • her bir node için node un değerinden küçük değerde olanlar  node un soluna, node un değerinden büyük değerde olanlar node un sağına yerleştirilir.

Ekleme (Insert)

Arama (Search)

Dolaşma (Traversal)

Aslında burda biraz Derin Önceklikli Arama (Deep First Search) yöntemlerinden bazılarını vermiş oluyoruz

PreOrder

PreOrder dolaşma mantığı ilk önce root sonra left sonra da right ‘ a bakarak dolaşmadır. Şayet left in de kendi içinde left ve right ı varsa onu da bir root gibi değerlendirecektir.

Yukarıda ki gibi bir Binary Search Tree olduğunu düşünün. Bu tree üzerinde preOrder şekilde dolaşırsak çıktımız şu şekilde olacaktır.

30 – 10 – 7 – 15 – 32 – 43 – 45 

PostOrder

PostOrder da ise ilk önce left sonra right sonra root kontrol edilecektir.

Demin örnek verdiğim tree üzerinde bu yöntemle dolaşılınırsa sonuç:

7 – 15 – 10 – 45 – 43 – 32 – 30

olur.

InOrder

Bu yöntemde ise ilk önce left sonra root sonra right bakılacaktır.

Deminki örneğe göre bu yöntem ile tree üzerinde dolaşılınırsa sonuç

7 – 10 – 15 – 30 – 32 – 43 – 45 

olur. Görüldüğü gibi InOrder da küçükten büyüğe doğru dolaşılmış olunur.

Min value ve Max value bulma fonksiyonlarını ve kodun tamamına buradan ulaşabilirsiniz.