1. BINARY TREE
Bir node’u n 2 child’ı olabiliyorsa bu ağaç binary tree olarak adlandırılır. Aşağıdaki ağaç bir binary tree’dir.
2. BINARY SEARCH TREE (BST)
BST’nin Binary tree’ye göre farkı elemanların diziliş kuralıdır. BST’ye eleman eklerken izlenmesi gereken bir yol vardır.
* Eklenecek eleman parent’lardan küçükse sola yazılır.
* Eklenecek eleman parent’lardan büyükse sağa yazılır.
BST ELEMAN EKLEME
Aşağıdaki BST’de ilk olarak 8in root olarak yerleştirildiğini varsayalım.
3 eklenmek istendiği zaman -> 8’den büyük mü küçük mü? küçük -> sola ekle.
10 eklenmek istendiği zaman-> 8’den büyük mü küçük mü? büyük -> sağa ekle.
* Bu aşamada rootun alabileceği child node sayısı max olan 2ye ulaşmıştır. Bu sebeple ;
1 eklenmek istendiği zaman -> 8’den büyük mü küçük mü? küçük -> sağa yönel -> 3’ten büyük mü küçük mü? küçük -> sağa ekle
6 eklenmek istendiği zaman -> 8’den büyük mü küçük mü? küçük -> sağa yönel -> 3’ten büyük mü küçük mü? büyük -> sola ekle
Bir ağacın sahip olabileceği maximum node sayısı : ( 2 ^(Depth + 1 ) ) -1 ; yani yukarıdaki ağacın depth’inin 3 olduğunu düşünürsek 2^4 -1 den maximum sahip olabileceği node sayısı 15tir.
BST MAXIMUM ve MİNİMUM ELEMAN BULMA
Maksimum elemanı bulma : Her seferinde büyük elemanı sağa eklediğimizi varsayarsak en büyük eleman sağ en derindeki elemandır.
Minimum elemanı bulma : Her seferinde büyük elemanı sağa eklediğimizi varsayarsak en büyük eleman sağ en derindeki elemandır.
3. TREE TRAVELSAL ALGORITMALARI – AĞAÇ ÜZERİNDE GEZİNME ALGORİTMALARI
Traversal algoritmaları bir sıralı köklü ağacın tüm düğümlerini sistematik bir şekilde ziyaret etmeye yarayan algoritmalardır. 3 temel traversal algoritması vardır.
1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal
1. Preorder Traversal
Bir tree’yi pre order sıralarken izlenecek yol sırası kökten başlanıp her seferinde o kökün çocukları kendi soylarıyla beraber kökten koparılıp kökün sağına yazılır. Daha sonra soyu olan kökler için her seferinde aynı işlem yapılır ta ki tüm node’lar single olanakadar.
Yukarıdaki tree için preorder traversal yapmak istersek ;
- 8 kökünün iki child’ı onun sağına yazılır : 8 3 10 (3 ve 10 un soylarının hala altında olduğunu varsayınız.)
- 3 ve 10un childl’arı kendilerinin sağına yazılır : 8 3 1 6 10 14 ( 1 , 6, ve 14ün soylarının hala altında olduğunu varsayınız.)
- 6’nın child’larını 6nın sağına , 14ün child’ı 14ün sağına yazılır : 8 3 1 6 4 7 10 14 13
Ağacın üzerinde preorder traversal olarak gezilmiş hali : 8 3 1 6 4 7 10 13 14 şeklindedir.
2. Inorder Traversal
Bir tree’yi ınorder traversal olarak gezerken izlenecek yol sırası kökten başlayarak en soldaki child’ı kökün soluna diğer tüm child’ları sağına yollamaktır.
Yukarıdaki tree için inorder traversal yapmak istersek ;
- 8’in en solundaki child’ı ağaç yapısına dokunulmadan soluna diğerleri sağına yazılır : 3 8 10
- Aynı işlem 3 ve 10 için de uygulanır : 1 3 6 8 10 14
- Aynı işlem 1 6 ve 14 için de uygulanır : 1 3 4 6 7 8 10 13 14
Ağacın üzerinde inorder traversal olarak gezilmiş hali : 1 3 4 6 7 8 10 14 10 şeklindedir.
public void InOrder(Node theRoot) { if (!(theRoot == null)) { InOrder(theRoot.Left); theRoot.DisplayNode(); InOrder(theRoot.Right); } }
3. Postorder Traversal
Postorder traversal , preorder traversalın tersidir. Burada ise childlar soylarıyla tree yapısı bozulmadan parentlarının soluna atılır.
- Birinci adımda 8’in child’ları sol tarafa atılır : 3 10 8
- İkinci adımda 3 ve 10’un çocukları sol tarafa atılır : 1 6 3 14 10 8
- Üçüncü adımda 1,6 ve 14ün cocukları sol tarafa atılır ve tüm node’lar leaf halini alır : 1 4 7 6 3 13 14 10 8
POSTFIX and PREFIX GÖSTERİMİ
İşlemlerin tree’ler ile temsili
( ( x + y ) ^ 2 ) + ( ( x – 4 ) / 3 ) işlemini tree yapısıyla temsil ediniz.
Tree’ler üzerindeki işlemlerin sonuçlandırılması
Ağaç halinde temsil edilen bir işlemi çözümlemek için üzerinde preorder veya postorder olarak dolaşmamız gerekmektedir.
Eğer preorder olarak dolaşmışsak ortaya çıkan gösterime prefix
postorder olarak dolaşmışsak ortaya çıkan gösterime postfix denir.
+ – * 2 3 5 / ^ 2 3 4 prefix gösterimini çözünüz.
prefix olduğu için sağdan sola giderek, her bir işlem operatörüyle karşılaşıldığında sağındaki iki sayı o işlem operatörüyle işlenir.
7 2 3 * – 4 ^ 9 3 / + postfix gösterimini çözünüz.
postfix olduğu için soldan sağa giderek, her bir işlem operatörüyle karşılaştığında solundaki iki sayı o işlem operatörüyle işlenir.