4. Tree (Ağaç)

Ağaçlar yani tree’ler önemli veri yapılarındandır. LinkedList, Stack, Queue gibi linear veri değil non linear veri depolarlar.

Yukarıdaki resim üzerinden biraz Tree’nin yapısından bahsedelim. Yukarıdaki bir tree’dir. Görüldüğü gibi hiyerarşik bir yapısı vardır. VP Finance, CIO, VP Sales –> CEO’ya bağlıdır. Development Manager, Operational Manager –> CIO ‘ ya bağlıdır gibi bir hiyerarşi vardır. Ve Ceo seviyesini 0. level sayarsak derinliği 3 olan bir tree’dir.

Tree’lerde bazı özel terimler vardır.
 Root node  : İlk eleman yani parentı olmayan node root node’dur ve her tree’de olması gerekir. Yukarıdaki resimde CEO.
 Parent node : Bir node’un üst node’u o node’un parent’ıdır. CIO’nun parent’i CEO , Development managerin parent’i CIO’dur gibi.
 Child node :  Bir node’un alt node’u o node’un child’ıdır. Ceo’nun child’ları , VP Finance , CIO , VP Salest’dır gibi.
 Sibling node : Aynı parent’tan gelen node’lar sibling node’dur. VP Finance , CIO ve VP Sales siblingtir gibi.

  • Bir graf’ın tree olabilmesi için 2 özelliğe sahip olması gerekir.
    – Devre içermemelidir.
    – Kopuk (discreate) bir node bulunmamalıdır.

 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.

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.

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  14 13  ş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 preorder 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 13 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.