:::: MENU ::::
INFIX

İ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:


INFIX, PREFIX VE POSTFIX NOTASYONLARI

Bilgisayarlarda infix yazım türünün çözümlenmesi zordur. Acaba x=a/b−c+d*e−a*c şeklindeki bir ifadeyi çözümlerken, ((4/2)−2)+(3*3)−(4*2) gibi bir ifadenin değerini hesaplarken ya da a/(b−c)+d*(e−a)*c gibi parantezli bir ifadeyi işlerken derleyiciler sorunun üstesinden nasıl geliyor? 32*(55-32-(11-4)+(533-(533-(533+(533-(533+212)))*21-2))) gibi birçok operatör(+, -, /, *, ^) ve operand(A, B, C… gibi isimler ya da sayılar) içeren bir işlemde nasıl operatör önceliklerine göre işlem sıralarını doğru belirleyip sonuç üretebiliyorlar?

Bir ifadede farklı önceliklere sahip operatörler yazılma sırasıyla işlenirse ifade yanlış sonuçlandırılabilir. Örneğin 3+4*2 ifadesi 7*2=14 ile sonuçlandırılabileceği gibi 3+8=11 ile de sonuçlandırılabilir.

Bilgisayarlarda infix yazım türünün çözümlenmesi zordur. Bu yüzden ifadelerin operatör önceliklerine göre ayrıştırılması, ayrılan parçaların sıralanması ve bu sıralamaya uyularak işlem yapılması gerekir. Bu işlemler için prefix ya da postfix notasyonu kullanılır.

Çoğu derleyici, kaynak kod içerisinde infix notasyonunu kullanmaktadır ve daha sonra stack veri yapısını kullanarak prefix veya postfix notasyonuna çevirir.

Infix notasyonu: Alışa geldiğimiz ifadeler infix şeklindedir. Operatörlerin işlenecek operandlar arasına yerleştirildiği gösterim biçimidir. Bu gösterimde operatör önceliklerinin değiştirilebilmesi için parantez kullanılması şarttır. Örneğin infix notasyonundaki 2+4*6 ifadesi 2+24=26 ile sonuçlanır. Aynı ifadede + operatörüne öncelik verilmesi istenirse parantezler kullanılır; (2+4)*6. Böylece ifade 36 ile sonuçlandırılır.

Prefix notasyonu: Prefix notasyonunda (PN, polish notation) operatörler, operandlarından önce yazılır. Örneğin 2+4*6 ifadesi infix notasyonundadır ve prefix notasyonunda +2*46 şeklinde gösterilir.
Benzer biçimde (2+4)*6 ifadesi *+246 şeklinde gösterilir. Görüldüğü gibi prefix notasyonunda işlem önceliklerinin sağlanması için parantezlere ihtiyaç duyulmamaktadır.

Postfix notasyonu: Postfix notasyonunda (RPN, reverse polish notation) ise önce operandlar ve ardından operatör yerleştirilir. Aynı örnek üzerinden devam edersek; infix notasyonundaki 2+4*6 ifadesi prefix notasyonunda 2 4 6 * + şeklinde, benzer biçimde (2+4)*6 ifadesi de 2 4 + 6 * şeklinde gösterilir. Yine prefix’te olduğu gibi bu gösterimde de parantezlere ihtiyaç duyulmamaktadır.

Bazı bilgisayarlar matematiksel ifadeleri postfix olarak daha iyi saklayabilmektedir.

Tüm aritmetik ifadeler bu gösterimlerden birini kullanarak yazılabilir. Ancak, bir yazmaç (register) yığını ile birleştirilmiş postfix gösterimi, aritmetik ifadelerin hesaplanmasında en verimli yoldur.

İşlem önceliği;
1- Parantez içi
2- Üs alma
3- Çarpma/Bölme
4- Toplama Çıkarma
Aynı önceliğe sahip işlemlerde sıra soldan sağa (→) doğrudur. Yalnız üs almada sağdan sola doğru işlem yapılır.

infix-prefix-postfix

Kaynak: Hakan KUTUCU, Veri Yapıları