:::: MENU ::::
İkili ağaç

İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme Nasıl Yapılır?

İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme Nasıl Yapılır?

İkili ağaç, her düğümünde en fazla iki düğüm bağlı olan ağaç yapısıdır. İkili arama ağacı ise kök düğümün solunda kökten küçük değerlerin, sağında ise kökten büyük değerlerin sıralandığı araçtır.

İkili ağaç, rekürsif(özyineli) bir yapıdadır. İkili ağaçlara Directed Acyclic Graph(DAG) ismi de verilmektedir.

Aynı sayıları farklı sıralarda eklersek farklı ikili arama ağaçları oluşur.

Ağaçta dolaşmak için infix, prefix ve postfix stratejileri bulunur.

infix-> LNR, RNL -> Sol-Kök-Sağ veya Sağ-Kök-Sol
prefix -> NLR, NRL -> Kök-Sol-Sağ veya Kök-Sağ-Sol
postfix -> LRN, RLN -> Sol-Sağ-Kök veya Sağ-Sol-Kök

Şadi Evren ŞEKER’in anlatımındaki İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme yapan kod aşağıdadır:


İkili Ağaçlar Üzerinde Dolaşma Nasıl Yapılır?

İkili ağaç üzerinde dolaşma birçok şekilde yapılabilir Ancak, rastgele dolaşmak yerine, önceden belirlenmiş bir
yönteme, bir kurala uyulması algoritmik ifadeyi kolaylaştırır. Üstelik rekürsif fonksiyon yapısı kullanılırsa ağaç üzerinde işlem yapan algoritmaların tasarımı kolaylaşır. Önce-kök (preorder), kök-ortada (inorder), sonra-kök (postorder) olarak adlandırılan üç değişik dolaşma şekli çeşitli uygulamalara çözüm olmaktadır.

1- Preorder (Önce Kök) Dolaşma: Önce kök yaklaşımında ilk olarak root(kök), sonra left (sol alt ağaç) ve ardından right (sağ alt ağaç) dolaşılır.

2- Inorder (Kök Ortada) Dolaşma: Inorder dolaşmada önce left (sol alt ağaç), sonra root (kök) ve right(sağ alt ağaç) dolaşılır.

3- Postorder (Kök Sonda) Dolaşma: Postorder yaklaşımında ise, önce left (sol alt ağaç), sonra right (sağ alt ağaç) ve root (kök) dolaşılır.

Örnek: “25, 14, 23, 40, 24, 23, 48, 7, 5, 34, 10, 7, 17, 36” değerlerine sahip düğümler için ikili ağaç gösterimini oluşturunuz ve üç farklı preorder, inorder ve postorder sıralama yöntemine göre yazınız.

ikili-agac

Preorder : 25-14-7-5-10-7-23-17-24-23-40-34-36-48
Inorder : 5-7-7-10-14-17-23-23-24-25-34-36-40-48
Postorder : 5-7-10-7-17-23-24-23-14-36-34-48-40-25

Örnek: Aşağıda görülen bağıntı ağacındaki verileri preorder, inorder ve postorder sıralama yöntemine göre yazınız.

binary-tree

Preorder : + / 1 3 / x 6 7 4
Inorder : 1 / 3 + 6 x 7 / 4
Postorder : 1 3 / 6 7 x 4 / +

Kaynak: Hakan KUTUCU, Veri Yapıları