İkili Ağaçlar(Binary Tree)

Öncelikle bazı terimlerden bahsetmek istiyorum.

bmn9m

Kök- Yukarıdaki resimde görüldüğü gibi ağaç yapımızda tüm elemanlar aslında tek bir yere bağlı. Buna kök diyoruz.

Çocuk ve ebeveyn- Kök hariç her düğümün bir ebeveyni vardır.

Yaprak-Çocuğu olmaya düğümlere denir. 3-7-10 gibi

Kardeş-Ebeveyni aynı olan düğümlerdir.

İkili Ağaçların özellikleri

  • Hiçbir düğümün ikiden fazla çocuğu olamaz.
  • Ortalama bir ağacın derinliği(kökten düğüme olan yolun uzunluğu) N’den küçüktür. En kötü durumda N-1 olur.

 

Ağaç Gezme

Önce kök gezme(pre-order traversar)

  • Kökteki veriyi yaz
  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz

preorder

 Çıktı: ++a*bc*+*defg

Sonra kök gezme(post-order traversar)

  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz
  • Kökteki veriyi yaz

Çıktı: abc*+de*f+g*+

İç kök gezme(in-order traversar)

  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Kökteki veriyi yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz

Çıktı: a+b*c+d*e+f*g

Ayrıca iç kök gezme işlemi ile sayıları da sıralamış oluruz.

 

 

Çıktı:

screenshot

Bir Cevap Yazın

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